Creating Doubly Linked Lists
00:00 Up until now, we’ve talked about the most basic type of linked list, called the singly linked list. But there are more types of linked lists that can be used for slightly different purposes. If you remember from earlier in the course, we created a method for removing a node from a linked list.
00:19 This worked by finding the node to remove then linking the node before it and after it. The tricky thing about this was that our nodes only stored references to the next node in the sequence, and so we had to use a local variable to store the previously visited node.
Then, we could link the previous node with the node in the current node’s
.next attribute. This becomes much easier with a doubly linked list.
00:47 A doubly linked list contains nodes that reference both the next and previous node in the link. That looks something like this: a pointer to the previous node, the data at this node, and a pointer to the next node. Modifying our linked list
to support this is pretty straightforward. All we have to do is add another instance attribute called
previous to our
Now, you can use
.next to traverse forward and
.previous to traverse backwards.
You can use this new feature to rewrite your existing
LinkedList methods. You’ll find that some operations—like node removal—are easier with a previous node reference in each node.
This doubly linked list is what
collections.deque uses under the hood.
Become a Member to join the conversation.