Circularly Linked Lists

A circularly linked list is a doubly linked list in which one additional node is allocated. Its next and prev pointers are the head and tail pointers of the list. Its data member is not used.
A CircularlyLinkedList object has two data members:
- int size - Number of elements in the list.
- DoublyLinkedListNode* list - Pointer to the extra (dummy) node.
A CircularlyLinkedList uses DoublyLinkedListNodes.
The dummy node is always allocated -- even in an empty list.
None of the pointers is null.
- The next pointer of the last node points to the dummy node.
- The prev pointer of the first node points to the dummy node.
Since there are no null pointers, the code in the member functions contains no special cases.
Validity Requirements
- size >= 0.
- list != NULL.
- Count the dummy node (*list) as node 0 and count node size as node -1.
  - For every i from 0 to size,
    - The next pointer of node i is not NULL.
    - The prev pointer of node i is not NULL.
    - The next pointer of node i - 1 equals the prev pointer of node i + 1.
  - For every i from 1 to size - 1 (if size >= 2),
    - The next pointer of node i does not equal list.
  - For every i from 2 to size (if size >= 2),
    - The prev pointer of node i does not equal list.
  - The prev pointer of node 1 equals list.
  - The next pointer of node size equals list.
Example - circlinkedlist.h (original), circlinkedlist.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/CircularlyLinkedLists.html