Now that we’ve learned about doubly linked lists, let’s implement one in Python.
As a reminder, a doubly linked list is a sequential chain of nodes, just like a singly linked list. The nodes we used for our singly linked lists contained two elements:
- A value
- A link to the next node
The difference between a doubly linked list and a singly linked list is that in a doubly linked list, the nodes have pointers to the previous node as well as the next node. This means that the doubly linked list data structure has a tail property in addition to a head property, which allows for traversal in both directions.
So the nodes we will use for our doubly linked list contain three elements:
- A value
- A pointer to the previous node
- A pointer to the next node
Depending on the end-use of the doubly linked list, there are a variety of methods that we can define.
For our use, we want to be able to:
- Add a new node to the head (beginning) of the list
- Add a new node to the tail (end) of the list
- Remove a node from the head of the list
- Remove a node from the tail of the list
- Find and remove a specific node by its value
- Print out the nodes in the list in order from head to tail
To start, we are going to look at the updated
Node class and create the constructor.
Ready? Let’s go!
Note: We will reuse the
.stringify_list() method from our
LinkedList class, but we’re going to create the rest of the methods ourselves.
We are going to use a provided
Node class, which you can find at the top of script.py. We’ve added a
prev_node property to the class, as well as
Take a look to see the changes.
DoublyLinkedList class at the bottom of script.py, create an
__init__() method (constructor) that only has
self as a parameter, since each list will be empty when it’s created.
__init__() method create
tail_node instance variables. The nodes have no value yet, so set them to
Before moving on, take a moment to think about doubly linked lists. What do you think are some possible real-life uses?
(Take a look at the hint for some answers.)