Skip to content
Tutorials Center
My learning

Topics

Lesson 36 of 225 ยท Linked Lists

Linked Lists

Learn what a linked list is: nodes, pointers, head and tail. Build one by hand in Python, compare it with arrays and see when each structure is faster.

An array keeps its items side by side in one block of memory. That makes a[500] instant, but inserting at the front means shoving every other item one place over. A linked list takes the opposite approach: each item lives in its own small object called a node, and the nodes are tied together by pointers (references). To insert at the front you create one node and point it at the old first node. No shoving.

Linked lists are the simplest dynamic, pointer-based data structure, and mastering them is the foundation for trees, graphs, hash-table chains and many interview questions. In this lesson you learn the vocabulary, build a tiny list by hand, see the memory picture, and compare linked lists with arrays honestly. The next lessons then build complete singly and doubly linked lists.

Nodes and pointers

A node holds two things: a value (the data) and a next reference to the following node. The last node's next is None (null), which marks the end.

TEXT
head
  |
  v
+----+---+    +----+---+    +----+------+
| 10 | o----> | 20 | o----> | 30 | None |
+----+---+    +----+---+    +----+------+
 value next    value next    value next
  • head is a variable that refers to the first node. Lose the head and you lose the list (nothing else points at the first node).
  • tail is the last node. Keeping a tail reference as well lets you append in O(1).
  • length (size) can be stored in a counter so that len is O(1).

In Python a node is a tiny class. The reference is just an attribute that points at another object.

Python Nodes tied together by hand

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.

Traversal always follows the same pattern: start at head, process the node, move to next, stop when you reach None. You will write this loop hundreds of times.

The memory picture

Python's list stores references in a contiguous block (an array of pointers). A linked list's nodes can be anywhere in memory; only the next references connect them.

TEXT
array:        [ 10 | 20 | 30 | 40 ]            neighbours side by side
                 index 0 1 2 3                 a[i] = base + i * item_size

linked list:   node A           node C            node B
              [10|*]--------->  [30|None]  <-----[20|*]
                  \________________________________/
              nodes live in unrelated places; only pointers connect them

This has three practical consequences:

  1. No random access. To reach the k-th node you must follow k pointers from the head: O(k), not O(1).
  2. Cheap rearrangement. Inserting or removing next to a node you already hold changes a pointer or two: O(1), with no shifting of other items.
  3. Overhead and cache misses. Each node carries the value and a pointer (plus object overhead in Python), and scattered nodes are slower for the CPU cache than a contiguous array. In practice arrays win more often than the textbook costs suggest.

See Memory and Data Layout for why contiguous memory is so fast on real hardware.

Reaching the k-th element

An array finds a[k] with one calculation. A linked list has to count. Let's measure the work in steps, not time:

Python Index access: array versus 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.

Notice that build constructs the list from the back: starting with the last value and repeatedly pointing a new node at the current head. It is a compact way to build in O(n).

Inserting at the front

Putting a new value at the front of a Python list shifts every existing item. For a linked list it is a constant number of steps:

TEXT
before:   head -> [10] -> [20] -> None
new = Node(5);   new.next = head;   head = new
after:    head -> [5] -> [10] -> [20] -> None
Python Front insertion: shifts versus pointer changes

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.

Both end up with [5, 4, 3, 2, 1], but the array did 0 + 1 + 2 + 3 + 4 = 10 item moves while the linked list touched no existing nodes. (Python's own list.insert(0, x) is a fast C memmove, so for small lists it still wins in real time, but its growth is O(n) per insertion.)

Removing a node

To delete a node, make its predecessor skip over it. In a singly linked list you must have the previous node, which usually means walking to find it:

TEXT
delete 20:     [10] -> [20] -> [30]
               [10] ---------> [30]      (prev.next = prev.next.next)

If you already hold the predecessor, the deletion is O(1). Finding the predecessor is the O(n) part. This is the main reason for the doubly linked list, where every node also remembers its previous node.

Python Delete by relinking

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.

Python's garbage collector reclaims the removed node when nothing refers to it any more. In C or C++ you must free that node yourself.

Kinds of linked lists

Kind Each node has Notes
Singly linked value, next one direction only
Doubly linked value, prev, next walk both ways; O(1) delete given a node
Circular last node points back to the first round-robin scheduling, ring buffers

Linked list or array?

Operation Array (Python list) Singly linked list
Access by index O(1) O(n)
Search by value O(n) O(n)
Insert/delete at front O(n) O(1)
Insert/delete at end O(1) amortized append, O(1) pop O(1) append with a tail; O(n) delete last
Insert/delete in the middle, node known O(n) (shifting) O(1) after the previous node
Memory per item one pointer slot a whole node object
Cache behavior excellent poor

The honest summary: linked lists beat arrays in a narrow set of cases (frequent insertions/removals at known positions, no need for indexing, or when you cannot move items because other structures point at them). That is why queues, LRU caches and hash-table chains use them, while everyday code uses list and collections.deque.

Python has no built-in linked list. collections.deque is a doubly-ended queue implemented as a linked list of small blocks, and it gives O(1) appends and pops at both ends. You write your own nodes mainly to learn the ideas and to answer interview questions, where Node classes are given.

Common mistakes

  • Losing the head. Moving head = head.next without saving the old node can leave a section unreachable. Use a separate current variable to walk the list.
  • Dereferencing None. node.next.next fails if node.next is None. Check before you follow a pointer.
  • Forgetting the empty-list and single-node cases. Many bugs hide there; test them first.
  • Updating pointers in the wrong order. When inserting, set the new node's next before changing the previous node's next, or you lose the rest of the list.
  • Assuming O(1) append without a tail. Without a tail reference you must walk the whole list to append.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does a node in a singly linked list contain?

    The next reference is what links nodes together; the last node's next is None.
  2. 2. What is the cost of accessing the k-th element of a singly linked list?

    There is no index arithmetic. You must follow next references k times starting from the head.
  3. 3. Which operation is O(1) for a singly linked list with only a head reference?

    Inserting at the front creates one node and points it at the old head. Appending needs a tail pointer, and deleting the last node requires finding the previous node.
  4. 4. When inserting a new node after node p, which order is correct?

    First point the new node at the rest of the list, then link p to the new node. In the other order p.next already points to the new node, so you lose the rest.
  5. 5. Why are arrays often faster than linked lists in practice even for some operations with equal Big O?

    Contiguous memory means neighbouring items are loaded together. Linked nodes are scattered, causing more cache misses.

Summary

  • A linked list is a chain of nodes; each node holds a value and a reference to the next node, and head points at the first one.
  • There is no index arithmetic, so reaching the k-th item takes O(k).
  • Inserting or removing next to a node you already hold is O(1): only pointers change.
  • Singly, doubly and circular lists differ in which pointers each node keeps.
  • Arrays win on access and cache behavior; linked lists win on cheap insertion and deletion at known positions.
  • Always guard against None, empty lists and lost heads.

Next: Singly Linked List, where you build a complete class with append, insert, delete, search and iteration.