Doubly Linked Lists
With singly linked lists, each node in the list had a pointer to the next node in the list. This structure allowed us to grow and shrink the list as needed and gave us the ability to insert and delete nodes at the front, middle, or end of the list. However, we often had to use two pointers when manipulating the list to allow us to access the previous node in the list as well as the current node. One way to solve this problem and make our list even more flexible is to allow a node to point at both the previous node in the list as well as the next node in the list. We call this a doubly linked list.
The concept of a doubly linked list is shown below. Here, each node in the list has a link to the next node and a link to the previous node. If there is no previous or next node, we set the pointers to null.
Doubly Linked Node
A doubly linked list node is the same as a singly linked list node with the addition of the
previous attribute that points to the previous node in the list as shown below.
The class representation of a doubly linked list
Node is shown below. As discussed above, we have three attributes:
data, which holds the data of the node,
next, which is a pointer to the next node, and
previous, which is a pointer to the previous node.
We also use a constructor and the standard
toString operation to create a string for the data stored in the node.
Doubly Linked List
As with our singly linked list, we start off a doubly linked list with a pointer to the first node in the list, which we call
head. However, if we also store the pointer to the last node in the list, we can simplify some of our insertion and removal operations as well as reduce the time complexity of operations that insert, remove, or peek at the last node in the list.
The figure below shows a doubly linked list with five nodes. The variable
head points to the first node in the list, while the variable
tail points to the last node in the list. Each node in the list now has two pointers,
previous, which point to the appropriate node in the list. Notice that the first node’s
previous pointer is null, while the last node’s
next pointer is also null.
Doubly Linked List Class
Like we did for our singly linked list, we capture the necessary details for our doubly linked list in a class. The doubly linked list class has four attributes:
head—the pointer to the first node in the list,
tail—the pointer to the last node in the list,
current—the pointer to the current node used by the iterator, and
size—an integer to keep track of the number of items in the list.
Class DoubleLinkedList Node head Node tail Node current Integer size = 0