This article will explain in simple terms what linked lists are, why they’re useful, and how to use them in the Python programming language.

Lists

In Python, a list is an array of data – a simple list of values where each item has a value and a position in the list.

Lists are indexed (so the positions start counting at position 0, not 1).

For more information on lists in Python, check out these LinuxScrew articles:

A list, and all values in it, are stored together in your computer’s memory as one big value.

Linked Lists

Linked lists are just like lists – every item in them has a value and a position.

However, in linked lists, the values are not stored together in memory – the elements in the list are stored separately. This has implications for simplicity and performance.

Rather than storing each item sequentially (with a simple index and value for each item), each entry in a linked list stores the value of the item and a pointer to the next item in the list.

Storing the address of the next item in memory is important so that it can be found in the computer’s memory – remember, unlike lists, the values aren’t stored together.

Why Linked Lists?

Why is this advantageous? It makes reorganizing or modifying the list a lot less intensive for the computer. With a list, the whole array of values in it has to be reindexed if an item is added or removed, but with a linked list, the pointer for the value preceding the newly added or removed item just needs to be updated to point to the new next item in the list.

This is great for performance – but a bit more complex, so lists are still used instead of linked lists when the data isn’t expected to be changing.

How to Create a Linked List

Python doesn’t have a built-in Linked List class – but building your own is easy and is also a good demonstration of how classes can be used in Object-Oriented Programming.

Implementing a Node Class

The below code example implements a Python class. A class is a definition we can use to create variables of that class.

In this case, a Node class is defined, which will accept and store a data value and a nextNode value for an item in a linked list.

The __init__ method of the class will accept the value for the node and a location for the next node so that they can be stored when a variable of the Node class is being created:

# Define Node Class
class Node(object):

    # Initialise a new Node object with given data and nextNode
    def __init__(self, data=None, nextNode=None):
        self.data = data # self is a reference to the variable of the class Node we are working within - it's an internal reference to itself
        self.nextNode = nextNode

    # Return the value of the data in the Node
    def __repr__(self):
        return self.data

The __repr__ method is another special Python method – it returns the value of the variable as a string. One has been added to the Node class to override the default, as we only want the node to represent the data it contains when we retrieve the node’s value.

Implementing a Linked List Class

Now that we have a class for items (nodes) in a linked list, we can define a linked list class to hold them.

A linked list only really needs one piece of information when initialized using the init method – the head – or the first item in the list. The rest of the items in the list will be found using nextNode address in each node:

# Define LinkedList Class
class LinkedList(object):

    # Initialise a new LinkedList with an optional first Node
    def __init__(self, head=None):
        self.head = head

    # Return the value of all of the nodes in the list, comma separated
    def __repr__(self):
        currentNode = self.head
        nodes = []
        while currentNode is not None: # While there is a nextNode present, keep adding their values to the return value
            nodes.append(currentNode.data)
            currentNode = currentNode.nextNode
        return ", ".join(nodes) # Return the value of all of the nodes separated by commas

    # Make the linked list iterable, so it can be looped over
    def __iter__(self):
        node = self.head
        while node is not None:
            yield node
            node = node.nextNode

    # Calculate the size of the list by reading each node's nextNode value and incrementing the count for each Node that exists in the LinkedList
    def size(self):
        currentNode = self.head
        count = 0
        while currentNode is not None:
            count += 1
            currentNode = currentNode.nextNode
        return count

    # Insert a new value at the top of the linked list (first or head value) - a new Node is created containing data, it's nextNode value is set to the previous head of the linked list, and the head is then replaced with the new Node
    def insertHead(self, data):
        newNode = Node(data,  self.head)
        self.head = newNode

    # Insert a new value at the end of the Linked List - this involves traversing the whole linked list until the last node is found, then setting its nextNode value to the new node
    def insertLast(self, data):
        if self.head is None:
            self.head = Node(data)
            return
        for currentNode in self: # self can be iterated due to the above __iter__ method which returns an iterable copy of the linked list
            pass
        currentNode.nextNode =  Node(data)

The LinkedList class also contains a __repr__ method for reading the value of the whole list. In this case, it’s been overridden to return the values in the list by looping through them using each node’s value and the pointer to the next node, joining the values with commas separating them.

The __iter__ method presents an iterable interpretation of the linked list so that its values can be looped through.

Additional methods have been added for adding items to the linked list and calculating the size of the list. These could all be done outside of the class just as easily, but defining these functions as class methods means they’re reusable – you only have to write the code once, and it can be called from any variable of that class.

How to Use a Linked List

OK! There’s a bit of code above. Hopefully, it all makes sense, and the comments clear up any confusion. Here’s an example using the above-defined classes, creating and modifying a simple linked list:

# Create a new variable with the class LinkedList
myLinkedList = LinkedList() 

# Add some values to the list
myLinkedList.insertHead("cat")
myLinkedList.insertHead("dog")
myLinkedList.insertLast("bird")

# Print details about the list
print(myLinkedList.size())
print(myLinkedList)

As you can see, the new linked list works as intended and provides a flexible list that can grow to any size. The LinkedList class can be added to at any time to add functionality to the linked list, depending on what you need to do. For example, you could add your own sorting or formatting methods or add the ability to insert list items before or after other items in the list.

SHARE:

Related Articles

Linked Lists in Python – How to Use Them, With Examples