We wrap up our lesson on linked lists by covering doubly linked lists.
A doubly linked list is a linked list where nodes contain a reference to both the next and previous node in the list.
Why is this helpful? Well, we don't need to iterate through a list anymore to know what node is previous to some target node. Considering the small cost of including it, most linked lists will actually be doubly linked lists.
To include this reference in node creation, we need to update how we define a node. Notice how this is very similar to a node from previous lessons, it simply contains one more parameter.
Let's include some helper functions to create these nodes, and to print an iteration or neighbors of a specific node.
Great! Now lets see how we may include this when inserting at a specific node. Other functions such as inserting at head or tail follow similar structure.
When making a node for insertion, we already have everything we need when creating it. We only need to update references to the next and previous of neighboring nodes, while considering an edge case that the insertion might occur at the tail.
One major step left, we should be able to delete a node as well. We no longer need to iterate to know what the previous is anymore, we may simply update references.
Can you spot where this might have trouble? What might occur when the node is head? Well, we see references are updated correctly, however after the function is called, our reference to head remains the same! To correct this, we can either specify this function is only used for any node except head, and have another function for deleting at head, or we may update this function in a way similar to the practice question at the end of this lesson.
Please write a function that can delete a node anywhere in a linked list. If the head is the one deleted, then the return value should point to the new head.