Skip to content
wannacode

Linked list

In short: A linked list is a chain of nodes, each pointing to the next: with head and tail, adding at either end and removing from the front are O(1), while access by index is O(n).

Problem

The queue that stops the sending

The server sends emails from a queue. New ones go in at the back, urgent ones (a password reset) at the front, and the worker always takes the first. The code uses the ordinary list:

emails = []
emails.append("invoice")
emails.append("newsletter")
emails.append("report")
emails.insert(0, "password")
next_email = emails.pop(0)
print("Sending: " + next_email)
print("Left: " + ", ".join(emails))
Output
Sending: password
Left: invoice, newsletter, report

On Monday morning the newsletter to all customers fills the queue with 100,000 emails. The worker sends slower than usual, then almost stops, and the password reset emails are minutes late.

The reason: the list is a dynamic array. Taking the first one moves all the others one place forward, and an urgent one at the front moves all of them back. Sending 100,000 emails one after another is 99,999 + 99,998 + … + 1 = 4,999,950,000 moves, just to take the first one.

The idea

Nodes, head and tail

You already saw the node and inserting at the front in the lesson "Stack, queue and linked list": every element is a separate object with a value and an arrow next to the following one. Here you write the whole class and work out what every operation costs.

The list keeps three things:

  • head: the first node. Every walk starts there.
  • tail: the last node. With it adding at the end does not go through the whole list.
  • the size, so it is not counted every time.

Both ends have to be right after every operation. The empty list has head and tail None. A list with one node has head and tail that point to the same node. Almost every bug in a linked list is a forgotten end: you remove the last one, and tail still points to it.

See it

Your own linked list

Here is the whole class. The nodes never move: every operation changes only arrows.

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




class SimpleLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0


    def __len__(self):
        return self.size


    def add_first(self, value):
        node = Node(value)
        node.next = self.head
        self.head = node
        if self.tail is None:
            self.tail = node
        self.size += 1


    def add_last(self, value):
        node = Node(value)
        if self.tail is None:
            self.head = node
        else:
            self.tail.next = node
        self.tail = node
        self.size += 1


    def remove_first(self):
        if self.head is None:
            raise IndexError("the list is empty")
        value = self.head.value
        self.head = self.head.next
        if self.head is None:
            self.tail = None
        self.size -= 1
        return value


    def remove(self, value):
        prev = None
        n = self.head
        while n is not None and n.value != value:
            prev = n
            n = n.next
        if n is None:
            return False
        if prev is None:
            self.head = n.next
        else:
            prev.next = n.next
        if n is self.tail:
            self.tail = prev
        self.size -= 1
        return True


    def find(self, value):
        index = 0
        n = self.head
        while n is not None:
            if n.value == value:
                return index
            index += 1
            n = n.next
        return -1


    def get(self, index):
        if index < 0 or index >= self.size:
            raise IndexError(f"index {index}, size {self.size}")
        n = self.head
        for _ in range(index):
            n = n.next
        return n.value


    def __str__(self):
        values = []
        n = self.head
        while n is not None:
            values.append(n.value)
            n = n.next
        return " → ".join(values)

Watch which arrows change on every operation:

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




def __init__(self):
    self.head = None
    self.tail = None
    self.size = 0
Step by step, in words
  1. Three emails, each in its own node: the value and next, the arrow to the following one. head points to the first, tail to the last.
  2. add_first("password"): a new node, its next points to the old first, and head moves to it. Two arrows, nothing moves: O(1).
  3. add_last("invite"): tail already knows the last, so nothing is walked. Its next points to the new node, and tail moves: O(1).
  4. remove_first(): head moves to the next node. Nothing points to "password" any more, and its memory is freed by itself.
  5. remove("newsletter"): nodes have no index. n starts at head and walks until it finds it; prev stays one node behind. That is O(n).
  6. prev.next = n.next: one arrow goes around "newsletter". "report" and "invite" do not move.
  7. At the ends: two arrows, O(1). In the middle: one arrow, but you reach the place step by step, O(n).
emails = SimpleLinkedList()
emails.add_last("invoice")
emails.add_last("newsletter")
emails.add_last("report")
emails.add_first("password")
emails.add_last("invite")
print(emails)
print("Sending: " + str(emails.remove_first()))
emails.remove("newsletter")
print(emails)
print("Position of report: " + str(emails.find("report")))
print("Emails: " + str(len(emails)))
Output
password → invoice → newsletter → report → invite
Sending: password
invoice → report → invite
Position of report: 1
Emails: 3
remove_first on an empty list raises IndexError, as deque.popleft does. __str__ is what print(emails) prints. get is a method, not [i]: that way you see it reaches the element step by step.

Try it

Predict the output

Seven operations in a row. Watch which one is the last after the remove:

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




class SimpleLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0


    def __len__(self):
        return self.size


    def add_first(self, value):
        node = Node(value)
        node.next = self.head
        self.head = node
        if self.tail is None:
            self.tail = node
        self.size += 1


    def add_last(self, value):
        node = Node(value)
        if self.tail is None:
            self.head = node
        else:
            self.tail.next = node
        self.tail = node
        self.size += 1


    def remove_first(self):
        if self.head is None:
            raise IndexError("the list is empty")
        value = self.head.value
        self.head = self.head.next
        if self.head is None:
            self.tail = None
        self.size -= 1
        return value


    def remove(self, value):
        prev = None
        n = self.head
        while n is not None and n.value != value:
            prev = n
            n = n.next
        if n is None:
            return False
        if prev is None:
            self.head = n.next
        else:
            prev.next = n.next
        if n is self.tail:
            self.tail = prev
        self.size -= 1
        return True


    def find(self, value):
        index = 0
        n = self.head
        while n is not None:
            if n.value == value:
                return index
            index += 1
            n = n.next
        return -1


    def get(self, index):
        if index < 0 or index >= self.size:
            raise IndexError(f"index {index}, size {self.size}")
        n = self.head
        for _ in range(index):
            n = n.next
        return n.value


    def __str__(self):
        values = []
        n = self.head
        while n is not None:
            values.append(n.value)
            n = n.next
        return " → ".join(values)




emails = SimpleLinkedList()
emails.add_first("report")
emails.add_first("invoice")
emails.add_last("invite")
emails.remove_first()
emails.add_first("password")
emails.remove("invite")
emails.add_last("newsletter")
print(emails)
print("Emails: " + str(len(emails)))
Answer

The idea

What costs what: array against linked list

Operation Dynamic array Linked list
read by index O(1) O(n)
add at the front O(n) O(1)
add at the back O(1) amortized O(1) with tail
remove the first O(n) O(1)
remove the last O(1) O(n), doubly linked: O(1)
in the middle O(n): moving O(n): walking to the place

The last row is the trap. The relinking in the middle is O(1) by itself, but you reach the place from head, step by step. The linked list wins in the middle only if you already hold the node, for example because you just found it with a hash table.

There is a cost in memory too. The array keeps the values (or the references) next to each other. Every node is a separate object: the value, the arrow and the header the runtime keeps for every object. With small values a node takes several times more memory than a place in the array.

See it

Measure it

Inserting at the front: the dynamic array from the previous lesson against the linked list. We count the writes of elements: for the array the new one and every move, for the list only the new node. The arrows that change are two for every insert and do not grow with n.

  • Insert at the front O(n²)
  • Linked list: at the front O(n)
Algorithmn = 10n = 1,000n = 10,000n = 100,000
Insert at the front63501,51650,021,376≈ 5,002,137,600
Linked list: at the front101,00010,000100,000
The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.
class Node:
    def __init__(self, value):
        self.value = value
        self.next = None




class SimpleLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0


    def __len__(self):
        return self.size


    def add_first(self, value):
        node = Node(value)
        node.next = self.head
        self.head = node
        if self.tail is None:
            self.tail = node
        self.size += 1


    def add_last(self, value):
        node = Node(value)
        if self.tail is None:
            self.head = node
        else:
            self.tail.next = node
        self.tail = node
        self.size += 1


    def remove_first(self):
        if self.head is None:
            raise IndexError("the list is empty")
        value = self.head.value
        self.head = self.head.next
        if self.head is None:
            self.tail = None
        self.size -= 1
        return value


    def remove(self, value):
        prev = None
        n = self.head
        while n is not None and n.value != value:
            prev = n
            n = n.next
        if n is None:
            return False
        if prev is None:
            self.head = n.next
        else:
            prev.next = n.next
        if n is self.tail:
            self.tail = prev
        self.size -= 1
        return True


    def find(self, value):
        index = 0
        n = self.head
        while n is not None:
            if n.value == value:
                return index
            index += 1
            n = n.next
        return -1


    def get(self, index):
        if index < 0 or index >= self.size:
            raise IndexError(f"index {index}, size {self.size}")
        n = self.head
        for _ in range(index):
            n = n.next
        return n.value


    def __str__(self):
        values = []
        n = self.head
        while n is not None:
            values.append(n.value)
            n = n.next
        return " → ".join(values)

With 10,000 emails the array makes 50,021,376 writes, and the linked list 10,000.

Now the other way round: reading every element by index, get(0), get(1) and so on to the end. We count the places you reach: in the array get(i) is one jump, and in the list it passes i + 1 nodes.

  • Array: get(i) for every i O(n)
  • Linked list: get(i) for every i O(n²)
Algorithmn = 10n = 1,000n = 10,000n = 100,000
Array: get(i) for every i101,00010,000100,000
Linked list: get(i) for every i55500,50050,005,000≈ 5,000,500,000
The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.
class Node:
    def __init__(self, value):
        self.value = value
        self.next = None




class SimpleLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0


    def __len__(self):
        return self.size


    def add_first(self, value):
        node = Node(value)
        node.next = self.head
        self.head = node
        if self.tail is None:
            self.tail = node
        self.size += 1


    def add_last(self, value):
        node = Node(value)
        if self.tail is None:
            self.head = node
        else:
            self.tail.next = node
        self.tail = node
        self.size += 1


    def remove_first(self):
        if self.head is None:
            raise IndexError("the list is empty")
        value = self.head.value
        self.head = self.head.next
        if self.head is None:
            self.tail = None
        self.size -= 1
        return value


    def remove(self, value):
        prev = None
        n = self.head
        while n is not None and n.value != value:
            prev = n
            n = n.next
        if n is None:
            return False
        if prev is None:
            self.head = n.next
        else:
            prev.next = n.next
        if n is self.tail:
            self.tail = prev
        self.size -= 1
        return True


    def find(self, value):
        index = 0
        n = self.head
        while n is not None:
            if n.value == value:
                return index
            index += 1
            n = n.next
        return -1


    def get(self, index):
        if index < 0 or index >= self.size:
            raise IndexError(f"index {index}, size {self.size}")
        n = self.head
        for _ in range(index):
            n = n.next
        return n.value


    def __str__(self):
        values = []
        n = self.head
        while n is not None:
            values.append(n.value)
            n = n.next
        return " → ".join(values)

With 10,000 elements the array makes 10,000 jumps, and the linked list 50,005,000 steps. A loop by index over a linked list is O(n²). Walk it with the loop along the arrows (or with for-each), as __str__ does: that is O(n).

More precisely, if you are curious

The same numbers in your language, with counters in the class:

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




class SimpleLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0
        self.writes = 0
        self.steps = 0


    def __len__(self):
        return self.size


    def add_first(self, value):
        node = Node(value)
        self.writes += 1
        node.next = self.head
        self.head = node
        if self.tail is None:
            self.tail = node
        self.size += 1


    def add_last(self, value):
        node = Node(value)
        if self.tail is None:
            self.head = node
        else:
            self.tail.next = node
        self.tail = node
        self.size += 1


    def remove_first(self):
        if self.head is None:
            raise IndexError("the list is empty")
        value = self.head.value
        self.head = self.head.next
        if self.head is None:
            self.tail = None
        self.size -= 1
        return value


    def remove(self, value):
        prev = None
        n = self.head
        while n is not None and n.value != value:
            prev = n
            n = n.next
        if n is None:
            return False
        if prev is None:
            self.head = n.next
        else:
            prev.next = n.next
        if n is self.tail:
            self.tail = prev
        self.size -= 1
        return True


    def find(self, value):
        index = 0
        n = self.head
        while n is not None:
            if n.value == value:
                return index
            index += 1
            n = n.next
        return -1


    def get(self, index):
        if index < 0 or index >= self.size:
            raise IndexError(f"index {index}, size {self.size}")
        n = self.head
        self.steps += 1
        for _ in range(index):
            n = n.next
            self.steps += 1
        return n.value


    def __str__(self):
        values = []
        n = self.head
        while n is not None:
            values.append(n.value)
            n = n.next
        return " → ".join(values)




for n in [10, 1000, 100000]:
    list_ = SimpleLinkedList()
    for i in range(n):
        list_.add_first(str(1001 + i))
    print(f"at the front, n = {n}: {list_.writes} writes")
for n in [10, 1000]:
    list_ = SimpleLinkedList()
    for i in range(n):
        list_.add_last(str(1001 + i))
    for i in range(n):
        list_.get(i)
    print(f"get(i) for every i, n = {n}: {list_.steps} steps")
Output
at the front, n = 10: 10 writes
at the front, n = 1000: 1000 writes
at the front, n = 100000: 100000 writes
get(i) for every i, n = 10: 55 steps
get(i) for every i, n = 1000: 500500 steps

Bench counts operations, not time. On the clock the difference when walking is even bigger in favour of the array because of the cache: the array is one block, and the nodes are scattered and every next one may not be in the cache. That is not measured here, only explained in the lesson on the dynamic array.

Try it

Find the bug

A colleague has written add_last. Three emails at the back, and the list comes out like this:

emails = SimpleLinkedList()
emails.add_last("invoice")
emails.add_last("newsletter")
emails.add_last("report")
print(emails)
print("Emails: " + str(len(emails)))
Output
invoice → report
Emails: 3

The size is 3, and the emails are two. Which line is the bug on?

Pick the line with the bug.

Try it

Fill in

remove has found the node n and the one before it, prev. Where does prev have to point now?

def remove(self, value):
    prev = None
    n = self.head
    while n is not None and n.value != value:
        prev = n
        n = n.next
    if n is None:
        return False
    if prev is None:
        self.head = n.next
    else:
        prev.next = 
    if n is self.tail:
        self.tail = prev
    self.size -= 1
    return True

The idea

The doubly linked list

A singly linked list cannot remove the last one fast: it needs the one before the last, and nothing points back to it. A doubly linked list keeps two arrows in every node, next and prev. Then both ends are O(1), and a node you already hold is removed with four arrows, without searching for the previous one.

The cost is one more arrow in every node and more to relink on every operation.

collections.deque in Python is doubly linked, but every node is a block of 64 elements. So it is fast at both ends, and there is less memory for arrows.

The idea

Where the linked list really wins

For an ordinary queue the built-in one is better. deque keeps blocks of 64 elements and moves nothing. How it works is in the lesson Stack and queue. The linked list wins when you already hold the node and have to take it out or move it:

  • An LRU cache. The shop keeps the last opened products in memory and throws out the one opened longest ago. A hash table finds the node of the product in O(1), and a doubly linked list moves it to the back. The oldest is always at the front.
  • History with back and forward. The browser and the editor keep the steps in a doubly linked list: back and forward are one arrow.
  • The lists in the operating system kernel. Processes and buffers carry their own arrows and are taken out of the list in O(1).

Here is an LRU with the built-in tools, the last three opened products:

from collections import OrderedDict




class Recent:
    def __init__(self, limit):
        self.limit = limit
        self.items = OrderedDict()


    def open(self, product):
        if product in self.items:
            self.items.move_to_end(product)
        else:
            if len(self.items) == self.limit:
                self.items.popitem(last=False)
            self.items[product] = True


    def __str__(self):
        return ", ".join(self.items)




recent = Recent(3)
for product in ["laptop", "mouse", "monitor", "laptop", "keyboard"]:
    recent.open(product)
    print(recent)
Output
laptop
laptop, mouse
laptop, mouse, monitor
mouse, monitor, laptop
monitor, laptop, keyboard
OrderedDict keeps the keys in a doubly linked list. move_to_end moves the product to the back, and popitem(last=False) throws out the oldest.

Exercise

A doubly linked list

Solve it in your editor.

Removing from both ends. Make a DoublyLinkedList: the node has prev too. Write add_first, add_last, remove_first and remove_last, all in O(1). Keep both ends right: when the list becomes empty, both head and tail are None.

Add the three emails at the back and the password one at the front. Print the list, remove the last and the first, print it again. Remove two more from the back, print the size, then add the invite at the back:

Output
password → invoice → newsletter → report
Last: report
First: password
invoice → newsletter
Emails: 0
invite

More tasks

  • The middle with two pointers. Find the middle node in one pass: one pointer goes one step at a time, the other two. When the fast one reaches the end, the slow one is in the middle.
  • A cycle in the list. A bug has attached the last node to one of the previous ones. Detect it with the same two pointers: if there is a cycle, the fast one catches up with the slow one.
  • Remove all occurrences. remove_all(self, value) removes every node with that value in one pass and returns how many it removed. Do not forget tail.
  • LRU by hand. Make the LRU cache from the card above with your own doubly linked list and a dict from product to node.

Test

Check yourself

1. A linked list has 1000 nodes, and you keep only head. How many nodes do you pass to read the element at index 999?
2. Why is tail needed if head already holds the whole list?
3. In a singly linked list with head and tail, what does removing the last one cost?
4. Bench shows that inserting at the front makes n operations in a linked list and about n²/2 in a dynamic array. Why is the array still often faster when walking?
5. An LRU cache keeps the last 1000 opened products and throws out the one opened longest ago. What makes every open O(1)?

Made by Ivo Gergov as part of Evo Tech's campaign for accessible programming education ·