Python Linked Lists

Introduction

A linked list is one of the most common data structures used in computer science. It is also one of the simplest ones too, and is as well as fundamental to higher level structures like stacks, circular buffers, and queues.

Generally speaking, a list is a collection of single data elements that are connected via references. C programmers know this as pointers. For example, a data element can consist of address data, geographical data, geometric data, routing information, or transaction details. Usually, each element of the linked list has the same data type that is specific to the list.

A single list element is called a node. The nodes are not like arrays which are stored sequentially in memory. Instead, it is likely to find them at different memory segments, which you can find by following the pointers from one node to the next. It is common to mark the end of the list with a NIL element:

Illustration: Single-linked list

There exist two kinds of lists - single and double-linked lists. A node in a single-linked list only points to the next element in the list, whereas a node in a double-linked list points to the previous node, too. The data structure occupies more space because you will need an additional variable to store the further reference:

Illustration: Double-linked list

A single-linked list can be traversed from head to tail whereas traversing backwards is not as easy as that. In contrast, a double-linked list allows traversing the nodes in both directions at the same cost, no matter which node you start with. Also, adding and deleting nodes as well as splitting single-linked lists is done in not more than two steps. In a double-linked list, four pointers have to be changed.

The Python language does not contain a pre-defined datatype for linked lists. To cope with this situation we either have to create our own data type or have to make use of additional Python modules that provide an implementation of such a data type.

In this article, we'll go through the steps to create our own linked list data structure. First, we create a corresponding data structure for the node. Second, you will learn how to implement and use both a single-linked list, and finally a double-linked list. Please note that the point of this article isn't to create a production-ready linked list class. We'd like to explain to novice programmers what linked lists are, how to implement one, and how to use one.

Defining a Node as a Data Structure

To have a data structure we can work with, we define a node. We'll implement a node as a class named ListNode. The class contains the definition to create an object instance, in this case, with two variables - data to keep the node value, and next to store the reference to the next node in the list. Furthermore, a node has the following methods and properties:

• __init_() - initialize the node with the data
• self.data - the value stored in the node
• self.next - the reference pointer to the next node
• has_value() - compare a value with the node value

These methods ensure that we can initialize a node properly with our data (__init__()), and cover both the data extraction and storage (via the self.data property) as well as getting the reference to the connected node (via the self.next property). The method has_value() allows us to compare the node value with the value of a different node:

class ListNode:
    def __init__(self, data):
        "constructor to initiate this object"
        
        # store data
        self.data = data
        
        # store reference (next item)
        self.next = None
    
    def has_value(self, value):
        "method to compare the value with the node data"
        if self.data == value:
            return True
        else:
            return False

Now that we have our ListNode class, creating a node is as simple as instantiating an object of our node class :

node1 = ListNode(15)
node2 = ListNode(8.2)
node3 = ListNode("Berlin")

Having done that we have available three instances of the ListNode class. These instances represent three independent nodes that contain the values 15 (integer), 8.2 (float), and "Berlin" (string).

Creating a Class for a Single-Linked List

As the second step, we define a class named SingleLinkedList that covers the methods needed to manage our list of nodes. It contains these methods:

• __init__() - initiate an object
• list_length() - return the number of nodes
• output_list() - outputs the node values
• add_list_item() - add a node at the end of the list
• unordered_search() - search the list for the nodes with a specified value
• remove_list_item_by_id() - remove the node according to its id

We will go through each of these methods step by step.

The __init__() method defines two internal class variables named head and tail. They represent the beginning and the end nodes of the list. Initially, both head and tail have the value None as long as the list is empty:

class SingleLinkedList:
    def __init__(self):
        "constructor to initiate this object"
        
        self.head = None
        self.tail = None

Adding Nodes to a Single-Linked List

Adding items to the list is done via add_list_item(). This method requires a node as an additional parameter. To make sure it is a proper node (an instance of class ListNode) the parameter is first verified using the built-in Python function isinstance(). If successful, the node will be added at the end of the list. If item is not a ListNode, then one is created.

In case the list is (still) empty the new node becomes the head of the list. If a node is already in the list, then the value of the tail is adjusted accordingly:

def add_list_item(self, item):
    "add an item at the end of the list"

    if not isinstance(item, ListNode):
        item = ListNode(item)

    if self.head is None:
        self.head = item
    else:
        self.tail.next = item

    self.tail = item

The list_length() method counts the number of nodes and returns the length of the list. To get from one node to the next in the list the node property self.next comes into play, and returns the link to the next node. Counting the nodes is done in a while loop as long as we do not reach the end of the list, which is represented by a None link to the next node:

def list_length(self):
    "returns the number of list items"

    count = 0
    current_node = self.head

    while current_node is not None:
        # increase counter by one
        count = count + 1

        # jump to the linked node
        current_node = current_node.next

    return count

The method output_list() outputs the node values using the node property data. Again, to get from one node to the next the link is used that is provided via the next property:

def output_list(self):
    "outputs the list (the value of the node, actually)"

     current_node = self.head

    while current_node is not None:
        print(current_node.data)

        # jump to the linked node
        current_node = current_node.next

Based on the class SingleLinkedList we can create a proper list named track, and play with its methods as already described above. Therefore, let's create four list nodes, evaluate them in a for loop, and output the list content:

# create four single nodes
node1 = ListNode(15)
node2 = ListNode(8.2)
item3 = "Berlin"
node4 = ListNode(15)

track = SingleLinkedList()
print("track length: %i" % track.list_length())

for current_item in [node1, node2, item3, node4]:
    track.add_list_item(current_item)
    print("track length: %i" % track.list_length())
    track.output_list()

The output is as follows, and shows how the list grows:

track length: 0
track length: 1
15
track length: 2
15
8.2
track length: 3
15
8.2
Berlin
track length: 4
15
8.2
Berlin
15

Searching the Linked List

Searching the entire list is done using the method unordered_search(). It requires an additional parameter for the value to be searched. The head of the list is the starting point.

While searching we count the nodes. To indicate a match we use the corresponding node number. The method unordered_search() returns a list of node numbers that represent the matches:

def unordered_search (self, value):
    "search the linked list for the node that has this value"

    # define current_node
    current_node = self.head

    # define position
    node_id = 1

    # define list of results
    results = []

    while current_node is not None:
        if current_node.has_value(value):
            results.append(node_id)

        # jump to the linked node
        current_node = current_node.next
        node_id = node_id + 1

    return results

In the previous example, both the first and fourth node contain the value 15. Let's try searching for a 15 in a track linked list from the previous example:

search_result = track.unordered_search(15)
print(search_result)

This will result in:

[1, 4]

As expected, right? Since the track linked list contains 15 as the first and the fourth element.

Removing an Item from the Linked List

Removing a node from the list requires adjusting just one reference - the one pointing to the node to be removed must now point to the next one. This reference is kept by the node to be removed and must be replaced.

The following method is named remove_list_item_by_id(). As a parameter, it refers to the number of nodes similar to the value returned by unordered_search():

def remove_list_item_by_id(self, item_id):
    "remove the list item with the item id"

    current_id = 1
    current_node = self.head
    previous_node = None

    while current_node is not None:
        if current_id == item_id:
            # if this is the first node (head)
            if previous_node is not None:
                previous_node.next = current_node.next
            else:
                self.head = current_node.next
                # we don't have to look any further
                return

        # needed for the next iteration
        previous_node = current_node
        current_node = current_node.next
        current_id = current_id + 1

To remove, say, the fourth element from a track list you just need to call:

track.remove_list_item_by_id(4)

Creating a Double-Linked List

To create a double-linked list it feels natural just to extend the ListNode class by creating an additional reference to the previous node.

This affects the methods for adding, removing, and sorting nodes.

Let's add a new property named previous to store the reference pointer to the previous node in the list. We'll change our methods to use this property for tracking and traversing nodes as well:

class ListNode:
    def __init__(self, data):
        "constructor class to initiate this object"

        # store data
        self.data = data
        
        # store reference (next item)
        self.next = None

        # store reference (previous item)
        self.previous = None

    def has_value(self, value):
        "method to compare the value with the node data"
        if self.data == value:
            return True
        else:
            return False

Now we are able to define a double-linked list:

class DoubleLinkedList:
    def __init__(self):
        "constructor to initiate this object"

        self.head = None
        self.tail = None

    def list_length(self):
        "returns the number of list items"
        
        count = 0
        current_node = self.head

        while current_node is not None:
            # increase counter by one
            count = count + 1
            
            # jump to the linked node
            current_node = current_node.next
        
        return count

    def output_list(self):
        "outputs the list (the value of the node, actually)"
        current_node = self.head

        while current_node is not None:
            print(current_node.data)

            # jump to the linked node
            current_node = current_node.next
        
    def unordered_search (self, value):
        "search the linked list for the node that has this value"

        # define current_node
        current_node = self.head

        # define position
        node_id = 1

        # define list of results
        results = []

        while current_node is not None:
            if current_node.has_value(value):
                results.append(node_id)
            
            # jump to the linked node
            current_node = current_node.next
            node_id = node_id + 1
        
        return results

As described earlier, adding nodes requires a bit more action. Let's take a look at how we could implement it:

def add_list_item(self, item):
    "add an item at the end of the list"

    if isinstance(item, ListNode):
        if self.head is None:
            self.head = item
            item.previous = None
            item.next = None
            self.tail = item
        else:
            self.tail.next = item
            item.previous = self.tail
            self.tail = item

Removing an item from the list of similar costs has to be taken into account:

def remove_list_item_by_id(self, item_id):
    "remove the list item with the item id"

    current_id = 1
    current_node = self.head

    while current_node is not None:
        previous_node = current_node.previous
        next_node = current_node.next

        if current_id == item_id:
            # if this is the first node (head)
            if previous_node is not None:
                previous_node.next = next_node
                if next_node is not None:
                    next_node.previous = previous_node
            else:
                self.head = next_node
                if next_node is not None:
                    next_node.previous = None
            # we don't have to look any further
            return

        # needed for the next iteration
        current_node = next_node
        current_id = current_id + 1

Now, let's put all that into action and use the class in a Python program:

# create three single nodes
node1 = ListNode(15)
node2 = ListNode(8.2)
node3 = ListNode("Berlin")
node4 = ListNode(15)

track = DoubleLinkedList()
print("track length: %i" % track.list_length())

for current_node in [node1, node2, node3, node4]:
    track.add_list_item(current_node)
    print("track length: %i" % track.list_length())
    track.output_list()

results = track.unordered_search(15)
print(results)

track.remove_list_item_by_id(4)
track.output_list()

As you can see, we can use the class exactly as before when it was just a single-linked list.

The only change is the internal data structure!

Creating Double-Linked Lists with deque Object

Since other engineers have faced the same issue, we can simplify things for ourselves and use one of the few existing implementations available. In Python, we can use the deque object from the collections module.

For example, this object contains the following methods:

• append(): add an item to the right side of the list (end)
• append_left(): add an item to the left side of the list (head)
• clear(): remove all items from the list
• count(): count the number of items with a certain value
• index(): find the first occurrence of a value in the list
• insert(): insert an item in the list
• pop(): remove an item from the right side of a list (end)
• popleft(): remove an item from the left side of a list (head)
• remove(): remove an item from the list
• reverse(): reverse the list

The underlying data structure of deque is a Python list which is double-linked. The first list node has the index 0. Using deque leads to a significant simplification of the ListNode class. The only thing we keep is the class variable data to store the node value:

from collections import deque

class ListNode:
    def __init__(self, data):
        "constructor class to initiate this object"
        
        # store data
        self.data = data

The definition of nodes does not change and is similar to what we've been working with before. With this knowledge in mind, we create a list of nodes using the dequeue constructor:

track = deque([node1, node2, node3])
print("three items (initial list):")
for item in track:
    print(item.data)

Adding an item at the beginning of the list works with the append_left() method:

# add an item at the beginning
node4 = ListNode(15)
track.append_left(node4)
print("four items (added as the head):")
for item in track:
    print(item.data)

Similarly, append() adds a node at the end of the list:

# add an item at the end
node5 = ListNode("Moscow")
print("five items (added at the end):")
track.append(node5)
for item in track:
    print(item.data)

Conclusion

Linked lists as data structures are easy to implement and offer great usage flexibility. It is done with a few lines of code. As an improvement, you could add a node counter - a class variable that simply holds the number of nodes in the list. This reduces the determination of the list length to a single operation with O(1), and you do not have to traverse the entire list.

Also, please note that the purpose of this article was not to give you perfect, Pythonic, production-ready code, but to illustrate to you how things are implemented and how they work without too much of an overhead. But still, you could surely try rewriting this codebase to make it more compliant with the Python best practices.