Linked List

A linked list stores values in nodes. Each node points to the next node, so the sequence is formed by references rather than by contiguous indexes.

Linked lists are useful for understanding pointer-like structure, even though Python algorithm solutions often use lists unless the problem specifically gives linked-list nodes.

Core Idea

The central operation is following links. To reach the third node, the algorithm starts at the head and moves through next references.

This makes access by position slower than an array, but insertion or removal can be efficient when the algorithm already has the relevant node reference.

The important difference from an array is that a linked list does not provide direct index access. The list is known by its first node, usually called the head. Every later node is reached by following links.

Function Contract

The examples use head to mean the first node of a chain. A missing list is represented by None, and the final node has next == None.

reverse(head) accepts either None or the head of a linked list. It returns the new head after reversing the links. It changes node links in place rather than creating a Python list of values.

Python Example

class Node:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node
 
 
head = Node(1, Node(2, Node(3)))
 
current = head
while current is not None:
    print(current.value)
    current = current.next

The loop does not use indexes. It walks from node to node.

Step-by-Step Traversal

For the chain:

1 -> 2 -> 3 -> None

current first points to the node containing 1. After current = current.next, it points to the node containing 2. After another step, it points to 3. After the final step, it becomes None, so the traversal stops.

This is why linked-list loops usually have the condition:

while current is not None:

Common Operations

Reversing a linked list changes links one at a time:

def reverse(head):
    previous = None
    current = head
 
    while current is not None:
        next_node = current.next
        current.next = previous
        previous = current
        current = next_node
 
    return previous

The temporary next_node is necessary because changing current.next would otherwise lose the rest of the original list.

Complexity

Traversing a linked list of n nodes is O(n). Finding the node at position i is also O(i) because the algorithm must walk there.

Inserting after a known node is O(1), because only links change. Finding the insertion point may still cost O(n).

Common Confusions

A linked list is not just a Python list with different operations. A Python list stores elements in an indexable sequence. A linked list stores nodes connected by references.

Another common mistake is losing the rest of the list when changing links. If node.next is overwritten before the old next node is saved, the remaining chain may become unreachable.

Another common mistake is comparing node values when the problem asks about node identity. Two different nodes can contain the same value.

When To Use It

Use linked-list reasoning when the input is explicitly a linked list, when practicing pointer manipulation, or when a problem asks for operations such as reversing links, detecting cycles, or merging sorted node chains.

Do not choose a linked list just because the data is sequential. In Python algorithm practice, a normal list is usually simpler unless the problem specifically gives node links or asks for link manipulation.

The Main Point

A linked list is a chain of nodes reached by following references. It is useful for learning link manipulation, but position lookup requires walking from the head.