Linked list in Python (append, display, delete)

A linked list stores items in nodes. Each node holds one value and a link to the next node. The list itself only needs to know the first node, called the head.

The program

python

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


class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        node = Node(data)
        if self.head is None:
            self.head = node
            return
        current = self.head
        while current.next is not None:
            current = current.next
        current.next = node

    def prepend(self, data):
        node = Node(data)
        node.next = self.head
        self.head = node

    def remove(self, data):
        if self.head is None:
            return False
        if self.head.data == data:
            self.head = self.head.next
            return True
        current = self.head
        while current.next is not None:
            if current.next.data == data:
                current.next = current.next.next   # skip over the removed node
                return True
            current = current.next
        return False

    def display(self):
        values = []
        current = self.head
        while current is not None:
            values.append(str(current.data))
            current = current.next
        print(" -> ".join(values) or "(empty)")


numbers = LinkedList()
numbers.display()
for value in [10, 20, 30, 40]:
    numbers.append(value)
numbers.display()

numbers.prepend(5)
numbers.display()

print(numbers.remove(30))
print(numbers.remove(99))
numbers.display()

output

(empty)
10 -> 20 -> 30 -> 40
5 -> 10 -> 20 -> 30 -> 40
True
False
5 -> 10 -> 20 -> 40

How it works

Every loop follows the links: current = current.next moves to the next node, and None marks the end of the list.
append must walk to the last node before it can attach the new one, so it takes longer as the list grows. prepend only changes the head, so it is always fast.
remove does not delete the node directly. It changes the link of the node before it, so that the link points past the removed node. The head is a special case, because no node comes before it.
" -> ".join(values) or "(empty)" prints (empty) when the list has no items, because an empty string counts as False.

In everyday Python, a list or a collections.deque is the better choice. Linked lists are worth building once because they show how links between objects work, and they appear often in interview questions.

Related programs: Check if a linked list is a palindrome.