Skip to content
Tutorials Center
My learning

Topics

Lesson 37 of 225 ยท Linked Lists

Singly Linked List

Implement a singly linked list in Python from scratch: append, prepend, insert, delete, find, length and iteration, with traces, complexity and common bugs.

In the previous lesson you met nodes and pointers. Now you will build a complete, reusable singly linked list class: a container that owns the head, keeps a tail and a size, and offers the operations you expect: append, prepend, insert, delete, find, len() and iteration with a for loop.

Writing it carefully is the best exercise in pointer thinking you can do. Each method has the same few edge cases (empty list, one node, first node, last node), and handling them cleanly is a skill that carries into doubly linked lists, trees and graphs. We build the class step by step, then analyze the costs.

The design

Our list stores three things:

  • head: the first node (or None when the list is empty).
  • tail: the last node (or None), so that append is O(1).
  • size: the number of nodes, so that len() is O(1).
TEXT
head                          tail
  |                             |
  v                             v
[ 4 | o-]--> [ 8 | o-]--> [ 15 | o-]--> [ 16 | None ]      size = 4

The three invariants to maintain after every operation:

  1. If size == 0, then head and tail are both None.
  2. Otherwise tail.next is None and following next from head reaches tail after exactly size - 1 hops.
  3. size equals the number of nodes.

Most bugs in linked-list code are an operation that forgets to update tail or size.

Step 1: node, append, prepend and iteration

Python Class skeleton: append, prepend, iteration

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Defining __iter__ as a generator is a big win: list(items), sum(items), max(items) and the in operator all work for free, because Python knows how to loop over anything iterable. (in falls back on iteration when __contains__ is missing.)

Note how append and prepend each handle the empty case explicitly. In an empty list the new node is both the first and the last node.

Step 2: find and insert at an index

Searching walks the nodes and compares values, so it is O(n) in the worst case. Inserting at index i needs the node before position i; we walk i - 1 hops to reach it.

TEXT
insert 99 at index 2 in  [4] -> [8] -> [15] -> [16]

walk to index 1 (the node before):      prev = [8]
new.next = prev.next                    [99] -> [15]
prev.next = new                         [8]  -> [99]

result:  [4] -> [8] -> [99] -> [15] -> [16]

Two special cases: i == 0 is just prepend, and i == size is just append (so the tail stays correct).

Python find and insert

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Step 3: delete

To delete the first node holding value we need its predecessor, because the predecessor's next must skip the victim. Cases:

  1. Empty list: nothing to do.
  2. Victim is the head: move head forward. If the list becomes empty, tail must become None too.
  3. Victim is somewhere later: relink prev.next = victim.next. If the victim was the tail, tail must move back to prev.
TEXT
delete 15 from  [4] -> [8] -> [15] -> [16]
prev = [8], victim = [15]
prev.next = victim.next        [8] -> [16]

A common trick avoids the special case for the head: put a dummy node (a sentinel that holds no real data) in front of the list so that every real node has a predecessor. We use it in Linked List Techniques; here we handle the head explicitly to see why the trick helps.

Python delete and pop

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Pay attention to the line if node is self.tail: self.tail = prev. When you delete the only node, prev is None, which correctly resets the tail. This is exactly the kind of invariant that gets forgotten.

pop_back is O(n) even with a tail pointer, because to make the previous node the new tail you must find it by walking from the head. That asymmetry (cheap at the front, expensive at the back) is the main weakness of the singly linked list and the reason for doubly linked lists.

Counting the work

Let's count pointer hops to see the costs in numbers rather than trust a table.

Python Counting hops per operation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Finding the last element and popping from the back take n - 1 and n - 2 hops respectively: linear growth. Finding the first element takes 0 hops, and appending with a tail reference takes none at all.

Using it for real: a stack

Because front insertion and front removal are both O(1), a singly linked list is a natural way to implement a stack (last in, first out): push is prepend, pop is pop_front.

Python A stack on top of a linked list

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Complexity

Operation Time Notes
prepend O(1)
append O(1) needs tail
insert(i, x) O(i) walk to node i - 1; O(1) at either end
find(x) / x in list O(n)
delete(x) O(n) search, then O(1) relink
pop_front O(1)
pop_back O(n) must find the previous node
len O(1) stored counter
iteration O(n)
Space O(n) one node per item; O(1) extra per operation

Common mistakes

  • Not updating tail after deleting the last node or after removing the only node.
  • Not updating size in one of several code paths. Add a test that compares the stored size with the number of nodes you actually reach by iterating.
  • Walking one hop too far in insert: you need the node before the position, so loop index - 1 times.
  • Using == where you mean is. To check whether a node is the tail, compare identity (node is self.tail), not values; two different nodes can hold equal values.
  • Using the list while changing it. Deleting nodes inside a for value in list loop gives surprising results. Collect first, then delete.
  • Forgetting that index == size is a valid insertion point.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does our SinglyLinkedList keep a tail reference?

    With a tail, append links the new node directly after the last node. Without it, you would walk the whole list first.
  2. 2. Which operation is O(n) even though we have both head and tail references?

    To make the previous node the new tail you have to find it by walking from the head, because nodes only point forward.
  3. 3. When deleting the only node of a list, what must happen to head, tail and size?

    An empty list is represented by head == tail == None and size == 0. Forgetting the tail leaves a stale reference.
  4. 4. To insert a node at index i (0 < i < size), which node do we need to reach?

    We relink the previous node, so we walk i - 1 hops from the head.
  5. 5. What does defining iter as a generator give us?

    Python's built-ins accept any iterable, and a class with iter is iterable. The cost is still O(n) for a full traversal.

Summary

  • A singly linked list class owns head, tail and size; keep the three consistent after every operation.
  • prepend, append (with a tail) and pop_front are O(1); find, delete, insert in the middle and pop_back are O(n).
  • Always handle: empty list, single node, head, tail and middle.
  • Insert by pointing the new node at the rest of the list first, then linking the predecessor.
  • __iter__ as a generator makes the structure work with every Python built-in that accepts an iterable.
  • Cheap at the front and awkward at the back: a doubly linked list fixes that.

Next: Doubly Linked List, with prev pointers and sentinel nodes for O(1) deletion given a node.