Other Kinds of Linked Lists#

More kinds of data structures can be built using the idea of a next node or link field. Two such are circularly linked lists and doubly linked lists.

Circularly Linked Lists#

Linked lists may be connected into a circle so that the tail points to the head. These are called circularly linked lists. Often the head field is omitted since we have access as tail.getNext(), so instead of using the word tail we might use the word entry instead as it represents our single access point into the list.

A circularly linked list

Doubly Linked Lists#

Linked lists may have nodes with two link fields, one to the next node and one to the previous node. This makes a doubly linked list, and we can travel in both directions. Many access algorithms for doubly linked lists are still in \(\theta (n)\), but now the list requires extra memory for the extra link.

When we make a doubly linked list, we usually place two almost empty nodes at the beginning and end of the list, for the head and tail, respectively. Doing this makes our algorithms more simple. The head is a node with the next pointer set to enter the list and the remaining fields null. The tail is a node with the previous pointer set to enter the list and the remaining fields null. Our data is stored between the head and the tail, and may look similar to this:

A doubly linked list

Notice how insertion at the end of a doubly linked list is much faster, in time \(\theta(1)\), than the same operation on a singly linked list which is in time \(\theta(n)\).

Practice Questions#

  1. Write the node class for a doubly linked list.

  2. Write a method to insert a node into the beginning of a circularly linked list, just clockwise to entry. entry becomes the new node.

  3. Write a method to insert a node into the end of a doubly linked list.

  4. What is the complexity of inserting at the end of a doubly linked list? a singly linked list? Use order notation. Do not find the complexities exactly.

  5. What is the complexity of inserting into the middle of a doubly linked list? Use order notation.

  6. Draw a doubly linked circular list. Is there any advantage to having such a list? Any disadvantage?

To Solutions