Linked Lists with Tail Pointer

A linked list with tail pointer is a linked list with one additional pointer that points to the last node in the list.
- The name of the class is LinkedListwTail.
- One additional data member
  - LinkedListNode* tail - A pointer to the last node in the list.
Implement LinkedListwTail as a subclass of LinkedList.
- Re-implement only those functions that involve the tail pointer.
- PushBack() becomes much more efficient.
Use a linked list with tail pointer in applications that make extensive use of PushBack().
Validity Requirements
- size >= 0.
- If size == 0, then
  - head == NULL.
  - tail == NULL.
- If size == 1, then head == tail.
- If size >= 1, then
  - head != NULL.
  - tail != NULL.
  - The next pointer in node size is NULL.
- If size >= 2, then
  - For every i from 1 to size - 1, the next pointer in node i is not NULL.
  - The next pointer in node size - 1 equals tail.

This page was last modified on Feb 28, 2001

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