Python Program to Implement a Linked List

A singly linked list of Node objects that adds values at the end, deletes a value, reverses itself and prints as 1 -> 2 -> 3.

A linked list keeps its values in separate objects called nodes. Each node holds a value and a link to the next node, and the list itself remembers only the first one, the head. The program builds 1 -> 2 -> 3 -> 4: to reach the 3, it starts at the head and follows two links.

A Python list is different: its items sit side by side in memory, so numbers[2] goes straight to the third one. A linked list can't do that, but adding or removing a node changes a link or two and never moves the other values. It's a favourite exam and interview topic, and the same idea of nodes and links is behind trees and graphs.

Program

class Node:
    """A value and a link to the next node."""

    def __init__(self, value):
        self.value = value
        self.next = None


class LinkedList:
    def __init__(self):
        self.head = None  # the first node (None if empty)

    def append(self, value):
        """Add value at the end."""
        node = Node(value)
        if self.head is None:
            self.head = node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = node

    def delete(self, value):
        """Remove the first node holding value."""
        previous, current = None, self.head
        while current and current.value != value:
            previous, current = current, current.next
        if current is None:
            return  # value isn't in the list
        if previous is None:
            self.head = current.next  # it was the head
        else:
            previous.next = current.next  # link round it

    def reverse(self):
        """Point every link the other way."""
        previous, current = None, self.head
        while current:
            following = current.next
            current.next = previous
            previous, current = current, following
        self.head = previous

    def __str__(self):
        values, current = [], self.head
        while current:
            values.append(str(current.value))
            current = current.next
        return " -> ".join(values)


numbers = LinkedList()
for value in [1, 2, 3, 4]:
    numbers.append(value)
print("List:", numbers)
numbers.delete(3)
print("Without 3:", numbers)
numbers.reverse()
print("Reversed:", numbers)

Open in the editor Download linked_list.py

Output

List: 1 -> 2 -> 3 -> 4
Without 3: 1 -> 2 -> 4
Reversed: 4 -> 2 -> 1

How it works

Visualize Step through the program line by line: each step below shows up as its line runs.

1. A Node (classes and objects) holds a value and next, the node after it. A new node has no next node yet, so next is None.
2. A new LinkedList has no nodes, so its head is None.
3. append() makes a node for the value. In an empty list, that node becomes the head.
4. Otherwise it starts at the head and follows the links to the last node, the one whose next is None, and links the new node after it.
5. delete() walks the list until current is the node holding the value, keeping previous, the node before it.
6. If it walked off the end, the value isn't in the list, and nothing changes.
7. Otherwise it unlinks the node. If it was the head, the head moves on to the next node; if not, the node before it now links to the node after it. Nothing points to the deleted node any more, so Python frees its memory.
8. reverse() walks the list once and turns each link round to point at the node before. following keeps hold of the rest of the list, which would be lost once current.next changes. When the walk ends, previous is the old last node, and it becomes the head.
9. __str__ is what print() uses to show the list (special methods). It collects the values from the head to the end and joins them with arrows.
10. The program builds 1 -> 2 -> 3 -> 4 and prints it.
11. It deletes 3, prints the list, then reverses it and prints it again.

Reversing 1 -> 2 -> 4, one row per pass of the while loop:

Then current is None, the loop stops, and the head becomes 4.

Time and space complexity

Every operation here walks the list, so each one is O(n) for n nodes. Apart from printing, which builds a list of the values, each needs O(1) extra space: a couple of variables. The list itself takes O(n) space, one node per value.

Adding at the front would be O(1): the new node only has to link to the old head. And a tail attribute, a link to the last node, would make append() O(1) too. What a linked list can't do quickly is reach an item by its position: numbers[2] on a Python list is O(1), but here it means following links from the head.

Other ways to write it

Reversing with recursion

Reverse the rest of the list first, then hang the current node on its end (recursion). It's short, but every node waits in a call of its own, so it needs O(n) space, and a list of a few thousand nodes goes past Python's recursion limit.

class Node:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node

def reverse(node):
    """Reverse the list starting at node; return its new head."""
    if node is None or node.next is None:
        return node
    head = reverse(node.next)
    node.next.next = node  # the next node now links back here
    node.next = None
    return head

head = reverse(Node(1, Node(2, Node(4))))
print(head.value, head.next.value, head.next.next.value)

With collections.deque

Python has no linked list type of its own, but collections.deque is built from linked blocks of items, and it has the operations this program needs.

from collections import deque

numbers = deque([1, 2, 3, 4])
numbers.remove(3)
numbers.reverse()
print(" -> ".join(str(value) for value in numbers))

Try it yourself

• Delete 1 (the head), 4 (the last node) and 7 (not in the list), and print the list after each.
• Add a prepend(value) method that puts a new node at the front. It needs no loop.
• Add a __len__ method that counts the nodes, so that len(numbers) works.
• Keep a tail attribute that always points at the last node, and use it in append() instead of walking the list. delete() and reverse() can change the last node, so they have to update it too.

More data structures programs

• Python Program to Check Balanced Parentheses Beginner
• Python Program to Implement a Queue Beginner
• Python Program to Implement a Binary Search Tree Intermediate
• Python Program for Inorder, Preorder and Postorder Traversal Intermediate
• Python Program for Prefix Sums and Range Sum Queries Intermediate
• Python Program to Find the Maximum Sum of K Consecutive Elements Intermediate
• Python Program to Find the K Largest Elements Using a Heap Intermediate