In a doubly linked list, each node contains pointers to both the next and the previous nodes in the list. This allows traversal in both directions and makes certain operations, like removing the last element, more efficient. A doubly linked list node might be defined like this:
This allows us to go backwards in the list, but also increases the complexity. Now we have to manage two pointers for each node instead of one. This means that insertion and deletion operations require updating more pointers to maintain the integrity of the list.
You can click and drag on the animation area to pan around. Use the Ctrl + mouse wheel (or touchpad scroll gesture) while over the animation area to zoom in and out.
Note that the order of these operations is important. When we start the process, the only name we have for the node that will come after the new node is current->next. If we change current->next before connecting the new node to that one, we will lose track of the rest of the list.
We could start the process by making another temporary pointer to hold the oldNext and set it to current->next. Then, it would be harder to lose track of. And we could use oldNext->prev instead of newNode->next->prev to make that node point back at our new node.
ListNode* oldNext = current->next; // Save the old next node
ListNode* newNode = new ListNode(value); // Create the new node
newNode->next = oldNext; // Point new node to the old next node
newNode->prev = current; // Point new node back to current
// If there is an old next node, update its prev pointer
if (oldNext != nullptr) {
oldNext->prev = newNode;
}
size++; // Update the size of the list
When removing a node from a doubly linked list, we also have to update two pointers. We need to make the previous and next nodes point to each other, skipping over the node being removed. This requires updating the next pointer of the previous node and the prev pointer of the next node.
You can click and drag on the animation area to pan around. Use the Ctrl + mouse wheel (or touchpad scroll gesture) while over the animation area to zoom in and out.
You may have noticed that the animation shows two extra nodes in the list. The list starts with a node labeled H and ends with one labeled T. These are called dummy nodes. Dummy nodes are special nodes that do not hold any data, and are not considered part of the data in the list (notice they do not count towards the size of the list). Instead, they just help to simplify working with the start and end of the list.
Normally, the first node in a linked list is special in that it is tracked by the head pointer. Every other node is tracked by some other node’s next pointer. So we need special logic when working with the first node.
When using dummy nodes, the head always points at the start dummy node. So the first real node is now tracked by the start dummy node’s next pointer, making it more like any other node in the list.
The start dummy node is essentially index -1. So, if we want to access the value at location 0, we can do so by looking at the node after the start dummy node. If we want to look at index 2, we can advance two times from that location.
Using dummy nodes help avoid special cases in insertion and removal operations. But they do add their own complications. The constructor needs to make sure to allocate the dummy nodes and have them point at each other correctly. (An empty list will have the start dummy node’s next pointer point to the end dummy node, and the end dummy node’s previous pointer point to the start dummy node.) And the destructor needs to properly deallocate these dummy nodes to avoid memory leaks.
None of this would change the fundamental nature of a linked list. All the operations that were \(O(n)\) remain \(O(n)\) with dummy nodes. And no new operations are made possible by them. They just serve as a way to simplify parts of the implementation at the cost of a small, constant amount of memory and a little extra work in the constructor and destructor.
Although we are discussing them in the context of doubly linked lists, we could also use them with singly linked lists. In that structure, we would likely have just a single dummy node at the start of the list
Arrange the blocks to implement the removeAt method for a doubly linked list with dummy nodes. We will assume the index is valid. You will not use all the blocks
