Python Linked List

Copy Link LinkedIn Message Facebook Email X

It's time to take a look at a basic linked list implementation and explore some of the basic operations of Linked Lists in Python.

Python Linked List Example

First, look at a possible Node class implementation in Python:

class Node:
    """
    Defines a Node for a Linked List
    Accepts any data item
    """

    def __init__(self, data):
		"""
		Construct a new node

		:param data The data item to store in this node
		"""
		self.data = data
		self.next = None

Notice how the Node class contains an instance variable called next -- this is how one Node object links to another Node object. The next instance variable holds the reference to the next item in the list.

Because of this, you can now do something like this, assuming you have a Person class defined:

# Create a node with a new Person object
person1 = Node(Person("Test", "User1", "[email protected]"))

# Set the next variable to reference a new Node object
person1.next = Node(Person("Test", "User2", "[email protected]"))

This ability to chain Node objects together using the next variable is what defines the linked list. This is where the dynamic nature of the linked list comes from -- you can link more and more Node objects onto each other, effectively changing the size of the linked list as the program runs.

Of course, in the real world, you don't have to manipulate and manage Node objects directly. You create a LinkedList class, which will manage the Node objects. Here's what a linked list might look like implemented in Python:

import Node

class LinkedList:

    def __init__(self, node=None):
        """
        Construct a new Linked List
        """
        self.head = node

The LinkedList class uses the Node class internally, so to recreate the code from above, you can use the following:

people = LinkedList()

people.add(Person(Person("Test", "User1", "[email protected]"))
people.add(Person(Person("Test", "User2", "[email protected]"))

Great, but where does the .add() method come from? It's time to explore how to add, remove, and find information in a linked list.

Add Data to a Linked List

Adding data to a linked list can be done in one of three ways:

1. Add new data at the head of the list.
2. Add new data at the tail of the list.
3. Add new data somewhere in the middle of the list.

It's time to look at the code for each of these.

1. Add Data at the Head of a List

Adding data to the head of the list occurs quickly because you already know where the head of the list is. Here's how this looks in code:

def add_head(self, data):
    """
    Add a new piece of data to the head of the list

    :param data The data item to be added
    """

    # Create a new node with the new data item
    new_node = self.Node(data)

    # Make this node the head by:
    # - Pointing its next reference to the old head.
    # - Making it the new head.
    new_node.next = self.head
    self.head = new_node

So what's going on here? Conceptually, you:

1. Create a new node with the new data to be added.
2. Set the next reference of the new node to be the head of the list.
3. Set the head of the list to be the new node.

This works even if the list is empty since head == None in that case.

Graphically, here's what those steps look like: Adding data to a linked list

2. Add Data at the Tail of a List

Of course, if you can add to the head of a list, you can also add it to the tail. However, this is a little more involved, as you need to find the tail before you can add data to it. If the list is long, this can be time-consuming. It's time to take a look at the code:

def add_tail(self, data):
    """
    Add a new piece of data to the tail of the list

    :param data The data item to be added
    """

    # Create a new node with the new data item
    new_node = self.Node(data)

    # Is the list empty?
    if not self.head:
        # Make the new node the head
        head = new_node
        return

    # Find the tail of the list
    current_node = self.head
    while current_node.next:
        current_node = current_node.next

    # Point the old tail's next reference to the new node
    current_node.next = new_node

You can see this is a little more involved than simply adding something at the head of the list. In this case, you need to:

1. Create a new node with the new data to be added.
2. Check to see if the list is empty. a. If it is, set the new node as the sole item in the list
3. Otherwise: a. Check that current_node.next is not None b. If it is, set current_node = current_node.next and keep checking. c. Otherwise, set current_node.next to be the new node.

The while loop (described in steps 3a and 3b) demonstrates a technique called traversing or walking the list. A Node variable (in this case, current_node) is used to check each link in the list, using the .next references to visit each link. Traversing is a common technique used in many linked list operations and algorithms, and you'll see more of that later in this unit.

Graphically, this is what a list traversal to add data to the tail looks like: Adding data to the tail of a linked list

3. Add Data in the Middle of a List

Of course, you can add data at any point in a linked list. You just need to know where in the list to put the new node. This is normally done when trying to keep a list of items in a specific order.

It's time to assume you want to insert your data before another piece of data. Here's what that code might look like:

def add_before(self, data, compare):
    """
    Add a new piece of data before another piece of data

    :param data The data item to add
    :param compare The data item that should appear after the new data item
    """

    # Create a new node with the new data item
    new_node = self.Node(data)

    # Is the list empty
    if not self.head:
        self.head = new_node
        return

    # Is the head the data item you want to follow your new node?
    if self.head.data == compare:
        new_node.next = self.head
        self.head = new_node
        return

    # Find the node you want to follow the new node
    # This uses a trailing reference traversal
    compare_node = this.head
    trailing_node = None

    while compare_node and compare_node.data != compare:
        trailing_node = compare_node
        compare_node = compare_node.next

    # You are either at the end of the list, or you found the data
    # In either case, you can insert new_node between trailing_node and compare_node
    trailing_node.next = new_node
    new_node.next = compare_node

As with the .add_tail() method, you first check if the list is empty before doing any work. However, you can also check if the head contains the data for which you are searching. If so, then you can add the new node to the head of the list.

Otherwise, you have to search for the data in the list using a traversal technique called a trailing reference. With the trailing reference technique, you have to use Node variables to walk the list. The compare_node variable refers to the node you want to check for the data to compare. The trailing_node variable refers to the previous node in the list. Graphically, this looks like this:

#TBD: Need picture of trailing reference here.

Using a trailing reference provides you references to two adjacent Node objects. You can then insert your new node between them. Once the while loop is done, compare_node is either pointing to the node you want to follow your new data or has walked off the end of the list and is None. In either case, you can insert new_node between them by making trailing_node.next point to new_node, and new_node.next point tocompare_node.

Of course, you can also add data after another node in the list -- that is left as part of a lab.

Remove Data from a Linked List

As with adding data, you can remove data from a list in three ways:

1. Remove data from the head of the list.
2. Remove data from the tail of the list.
3. Remove data from the middle of the list.

It's time to take a look at all three techniques.

1. Remove the Head of a List

Removing the head of the list, like adding a new head, is quick. Conceptually, after checking for an empty list, you assign head to be head.next. This removes the first node from the list. If you wish, you can save the data in that node first, perhaps to be used as a return value as seen in the code below:

def remove_head(self):
    """
    Remove the item at the head of the list and return it

    :return The data item of the removed node
    """

    # If the list is empty, return nothing
    if not self.head:
        return None

    # Save the head so you can return its data item
    return_node = self.head

    # Move the head to the next node in the list
    self.head = self.head.next

    # Return the data in the old head
    return return_node.data

#TBD Image of removing the head of a list

As you can see, this example saves the old self.head to return its data value.

2. Remove the Tail of a List

Removing data from the tail of the list requires that you not only find the tail but also the node just before the tail. The trailing reference technique can be used here as it was earlier, as it will allow you to find both references. All you need to do is make sure there are at least two items in the list to make use of the technique:

def remove_tail(self):
    """
    Remove the item at the tail of the list and return it

    :return The data item of the remove node
    """

    # If the list is empty, return nothing
    if not self.head:
        return None

    # If this is the only node in the list, just return it
    if not self.head.next:
        return_node = self.head
        self.head = None
        return return_node.data

    # Use a trailing reference to find the tail of the list
    return_node = self.head
    trailing_node = return_node

    # Find the tail of the list
    while return_node.next:
        trailing_node = return_node
        return_node = return_node.next

    # Make the next to last node point to nothing to remove the tail
    trailing_node.next = None
    return return_node.data

#TBD Image of removing the tail of a list

Search for data in a Linked List

Finding a piece of data in a linked list requires you to traverse the list and inspect each item, looking for the data you want to find. Conceptually, this is like flipping through the pages of a book from start to finish:

def find(self, data):
    """
    Find a piece of data in the list

    :param data The data item to look for
    :return True if you found it, False otherwise
    """
    current_node = self.head

    # As long as you haven't:

    # - Reached the end of the list, and
    # - Found the data item
    # Keep walking the list
    while current_node and current_node.data != data:
        current_node = current_node.next


    # If the current_node is None, this will return False
    return bool(current_node)

You can also traverse a list to output the items in a list, which is left as a lab exercise.

If you'd like to continue learning about Linked Lists in Python, check out the following resource in the Python 301 course:

• Python Queue & Python Stack

Summary: Linked Lists in Python

Implementing a linked list in Python requires two classes -- one for the node in which data is stored and another for the list structure itself. Adding, removing, and finding data in the list is possible using a technique called traversing the list.

In general, you do not need to implement your own Linked List, but understanding its structure and how it operates will give you insight into how the linked lists work and how you can use them when necessary.