Learn

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.

Instructions

1.

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 .set_prev_node() and .get_prev_node() methods.

Take a look to see the changes.

2.

In our 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.

Inside your __init__() method create head_node and tail_node instance variables. The nodes have no value yet, so set them to None.

Then delete pass.

3.

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.)

Sign up to start coding

By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.
Already have an account?