Doubly Linked Lists

A doubly linked list is a linked list in which each node has two links: one to its successor and one to its predecessor.
A DoublyLinkedList object has three data members:
- int size - Number of elements in the list.
- DoublyLinkedListNode* head - Pointer to the first node.
- DoublyLinkedListNode* tail - Pointer to the last node.
A DoublyLinkedListNode has three data members:
- T data - Value stored in the node.
- DoublyLinkedListNode* prev - Pointer to the previous node.
- DoublyLinkedListNode* next - Pointer to the next node.
We can move both forwards and backwards in the list.
- When chasing pointers, it is not necessary to save a pointer to the previous node.
Validity Requirements
- size >= 0.
- If size == 0, then head == NULL and tail == NULL.
- If size >= 1, then head != NULL and tail != NULL.
- If size == 1, then head == tail.
- If size >= 1, then
  - The next pointer in node size is NULL.
  - The prev pointer in node 1 is NULL.
- If size >= 2, then
  - For every i from 1 to size - 1, the next pointer in node i is not NULL.
  - For every i from 2 to size, the prev pointer in node i is not NULL.
  - The prev pointer of node 2 equals head.
  - The next pointer of node size - 1 equals tail
- If size >= 3, then
  - For every i from 2 to size - 1, the next pointer of node i - 1 equals the prev pointer of node i + 1.
Example - doublylinkedlist.h (original), doublylinkedlist.h (copy), doublylinkedlistnode.h (original), doublylinkedlistnode.h (copy), ListTest.cpp.

Return to Lectures page

This page was last modified on Feb 28, 2001

URL: http://people.hsc.edu/faculty-staff/robbk/Coms262/Lectures/DoublyLinkedLists.html