vizlearn
Home / Algorithms

Linked Lists

Algorithms & Data StructuresBy Updated

Nodes scattered in memory, held together by pointers. Insertion costs nothing once you are there — but getting there costs everything, and that trade-off defines when to use one.

Controls

valueposition

Nodes and Pointers

step 0
Cost of the last operation

Insight

Each node stores a value and a pointer to the next node. There is no index arithmetic — the only way to reach position k is to follow k pointers from the head.

Used for

  • • Queue & stack implementations
  • • Hash table collision chains
  • • LRU caches (doubly linked)
  • • Undo histories

Complexity

Insert / delete at head O(1)
Access by index O(n)
Search O(n)

Overview

A singly linked list stores a value and a pointer to the next node. The head points to the first node; the last node points to None. Unlike an array, nodes do not need to occupy adjacent memory locations.

Nodes and pointers

In the visualizer, choose List type and compare Insert at position, Delete at position, and Search for value. Operations at the front need no traversal; an operation at a later position must walk through the preceding nodes first.

Worked example: insert after a node

Suppose P points to the node before the insertion location and N is the new node. First set N.next to the node that followed P; then set P.next to N:

new_node.next = previous.next
previous.next = new_node

If the order is reversed, the original remainder of the list can become unreachable. The operation is constant time once previous is known; finding that node by position still takes time proportional to the number of nodes traversed.

Singly linked, doubly linked, or array

  • Singly linked: one next pointer per node; simple and lower in pointer overhead, but backward movement requires another traversal.
  • Doubly linked: each node has next and prev; supports backward traversal and deletion when the node is already known, at the cost of more memory and pointer updates.
  • Dynamic array: fast indexed access and good cache locality; inserting near the front shifts later elements, while append is amortized constant time.
OperationLinked list by indexDynamic array
Read item at index iO(n)O(1)
Insert at frontO(1)O(n)
Insert after a known nodeO(1)O(n) in general
Search by valueO(n)O(n)

The table separates locating a position from changing pointers. Inserting at an arbitrary index in a linked list is not O(1) if the list must first be traversed to find it.

When linked lists are useful

Use them when code already holds node references and needs frequent splicing, or when implementing structures that need predictable local insertion and deletion. A doubly linked list paired with a hash map is a common design for an LRU cache: the map finds a node and the list moves it to the most-recently-used position.

For general application data, a dynamic array is often simpler and faster because contiguous memory is cache-friendly. Big-O counts operations but not the cost of pointer chasing or memory allocation.

Common mistakes with Linked Lists

  • Expecting random access: index lookup still walks the list.
  • Losing the next pointer: save it before rewiring links.
  • Ignoring the predecessor: singly linked deletion usually needs the node before the one being removed.
  • Forgetting edge cases: empty list, head deletion, tail updates, and a one-node list need explicit handling.

Sources and next steps

Run it in Python

A singly linked list with insert, delete, search and an in-place reversal — the operation that is genuinely hard to get right and the reason this structure keeps appearing in interviews.

linked_list.pyPython 3
Output
How the code works
  1. self.head = Node(value, self.head)Inserting at the front is O(1) and involves no movement at all — the new node simply points at the old head. The same insert into a Python list costs O(n).
  2. while node: ... node = node.nextThere is no arithmetic that jumps to element 5. Every access starts at the head and hops, which is why linked lists lose to arrays on almost every read-heavy workload despite the better insert.
  3. dummy = Node(None, self.head)The sentinel trick. Without it, deleting the first node needs its own branch because there is no previous node to re-point — and that branch is where the bug always is.
  4. prev.next = prev.next.nextDeletion is one assignment. Nothing is shifted and no memory is moved, which is the operation linked lists exist for.
  5. nxt = node.next; node.next = prevThe order is the whole exercise. Overwrite node.next before saving it and the rest of the list is unreachable — not corrupted, just gone.
Change one thing
  • Delete the nxt = node.next line in reverse and print the result. The list is one node long, and the other three are lost.
  • Build a list of 100,000 nodes and time find on the last value against the same lookup on a Python list. Both are O(n), and the linked version is far slower — cache locality, not complexity.
  • Add a prev pointer to make it doubly linked. Deletion no longer needs the node before it, which is exactly what collections.deque buys with the extra memory.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.




Predict, then reveal
About to run: set List type to 10. Before it does — what happens to the readout?
Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.
Check yourself
0 of 3
Answer without scrolling back up.
  1. In reverse(), why is 'nxt = node.next' saved before 'node.next = prev'?
  2. What is the dummy head in delete() for?
  3. Compared with a Python list, a linked list is better at:





 Cheat sheet
Linked Lists
Store elements in nodes linked by pointers and trade O(1) random access for O(1) insertion at any known position.
ALGORITHMS · vizlearn.in/dsa/linked_lists.html
More in Algorithms
AlgorithmsHash Tables and HashingAlgorithmsBinary Search TreesAlgorithmsHeaps and Priority QueuesAlgorithmsHeap Sort
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact