Linked Lists (DSA Tutorial)

A linked list stores items in separate nodes. Each node holds a value and a reference (a link) to the next node, like the coaches of a train coupled one behind another. Nothing has to sit side by side in memory, so adding or removing a node never shifts the others.

In this lesson you will build a singly linked list, learn its costs compared with an array, solve two classic interview problems (reversing a list and finding its middle or a cycle), and then build a doubly linked list with sentinel nodes.

Nodes and links

A node is a tiny object with two fields: value and next. The list itself only remembers the first node, called the head. The last node's next is None, which marks the end.

PythonRun it yourself

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

# Build a train: Engine -> S1 -> S2 -> B1
head = Node("Engine", Node("S1", Node("S2", Node("B1"))))

# Traverse: follow the links until you reach None
current = head
while current is not None:
    print(current.value, end=" -> ")
    current = current.next
print("None")

# Add a coach at the front in O(1): no shifting needed
head = Node("Guard", head)
print(head.value, head.next.value)

Output

Engine -> S1 -> S2 -> B1 -> None
Guard Engine

Adding at the front only creates one node and changes one link, so it is O(1) however long the list is. Compare that with list.insert(0, x), which shifts every item. The price you pay is that there is no items[i]: to reach the fifth node you must walk from the head through four links, which is O(n).

Operation	Array (Python list)	Singly linked list
Read item i	O(1)	O(i)
Insert or remove at the front	O(n)	O(1)
Insert or remove at the end	O(1) amortised	Insert O(1) with a tail reference; remove O(n)
Insert after a node you already have	O(n)	O(1)
Search for a value	O(n)	O(n)
Extra memory	Small	One extra reference per node

A linked list class

In practice you wrap the nodes in a class that keeps both a head and a tail, so adding at either end is O(1). Removing a value needs a previous reference, because you must change the link of the node before the one you delete.

PythonRun it yourself

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

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

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

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

    def remove(self, value):
        previous, current = None, self.head
        while current is not None and current.value != value:
            previous, current = current, current.next
        if current is None:
            return False                      # not found
        if previous is None:
            self.head = current.next          # removing the head
        else:
            previous.next = current.next      # skip over the node
        if current is self.tail:
            self.tail = previous
        self.size -= 1
        return True

    def __iter__(self):
        current = self.head
        while current:
            yield current.value
            current = current.next

orders = LinkedList()
for item in ["Masala Dosa", "Idli", "Vada"]:
    orders.append(item)
orders.push_front("Filter Coffee")
print(list(orders), orders.size)
print(orders.remove("Idli"), orders.remove("Pizza"))
print(list(orders), "tail:", orders.tail.value)

Output

['Filter Coffee', 'Masala Dosa', 'Idli', 'Vada'] 4
True False
['Filter Coffee', 'Masala Dosa', 'Vada'] tail: Vada

Notice how many special cases appear in remove(): an empty list, removing the head, removing the tail. Most linked list bugs hide in these edges, so test each one.

Reversing a linked list

Reversing a linked list in place is one of the most asked interview questions. Walk through the list once and turn each next arrow around. You need three references: the node before, the current node and the node after (saved before you break its link).

PythonRun it yourself

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

def build(values):
    head = None
    for v in reversed(values):
        head = Node(v, head)
    return head

def to_list(head):
    out = []
    while head:
        out.append(head.value)
        head = head.next
    return out

def reverse(head):
    previous = None
    current = head
    while current:
        after = current.next        # 1. remember the rest of the list
        current.next = previous     # 2. turn the arrow around
        previous = current          # 3. move both references one step
        current = after
    return previous                 # the old tail is the new head

stops = build(["Delhi", "Agra", "Gwalior", "Jhansi", "Bhopal"])
print(to_list(reverse(stops)))
print(to_list(reverse(None)))

Output

['Bhopal', 'Jhansi', 'Gwalior', 'Agra', 'Delhi']
[]

The time is O(n) and the extra space is O(1). Draw three boxes on paper and move the arrows by hand once; after that, the code is easy to remember.

Fast and slow pointers

Two references that move at different speeds solve several linked list problems in one pass. The slow pointer moves one node at a time and the fast pointer moves two.

When fast reaches the end, slow is at the middle.
If the list has a cycle (the last node links back to an earlier node, so the list never ends), fast will eventually lap slow and they will meet. This is called Floyd's cycle detection.

PythonRun it yourself

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

def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow.value

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

nodes = [Node(n) for n in ["A", "B", "C", "D", "E"]]
for a, b in zip(nodes, nodes[1:]):
    a.next = b
head = nodes[0]
print("Middle:", middle(head), "| cycle:", has_cycle(head))

nodes[-1].next = nodes[2]          # E links back to C: a loop
print("Cycle after the bad link:", has_cycle(head))

Output

Middle: C | cycle: False
Cycle after the bad link: True

Both functions use O(1) extra space. A simpler cycle check stores every visited node in a set, but that uses O(n) memory, and interviewers often ask for the O(1) version.

Doubly linked lists

In a doubly linked list, each node also has a prev reference to the node before it. That costs one more reference per node, but it gives two new powers: you can walk backwards, and you can remove a node in O(1) when you already hold a reference to it, because the node knows its own neighbours.

A clean way to write one is with two sentinel nodes: a dummy head and a dummy tail that hold no data. Every real node then sits between two other nodes, so the special cases for an empty list or the first and last node disappear.

PythonRun it yourself

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

class DoublyLinkedList:
    def __init__(self):
        self.head = DNode()            # sentinel
        self.tail = DNode()            # sentinel
        self.head.next = self.tail
        self.tail.prev = self.head

    def insert_before(self, node, value):
        new = DNode(value)
        new.prev, new.next = node.prev, node
        node.prev.next = new
        node.prev = new
        return new

    def append(self, value):
        return self.insert_before(self.tail, value)

    def unlink(self, node):            # O(1): the node knows its neighbours
        node.prev.next = node.next
        node.next.prev = node.prev

    def forward(self):
        out, n = [], self.head.next
        while n is not self.tail:
            out.append(n.value)
            n = n.next
        return out

    def backward(self):
        out, n = [], self.tail.prev
        while n is not self.head:
            out.append(n.value)
            n = n.prev
        return out

playlist = DoublyLinkedList()
songs = {name: playlist.append(name) for name in ["Kesariya", "Jhoome Jo Pathaan", "Naatu Naatu", "Apna Bana Le"]}
playlist.unlink(songs["Naatu Naatu"])
print(playlist.forward())
print(playlist.backward())

Output

['Kesariya', 'Jhoome Jo Pathaan', 'Apna Bana Le']
['Apna Bana Le', 'Jhoome Jo Pathaan', 'Kesariya']

The dictionary songs maps each name to its node, so finding a node is O(1) and unlinking it is O(1). This exact pairing of a hash table with a doubly linked list is how a least recently used (LRU) cache works: on every use, unlink the item and append it at the end, and when the cache is full, remove the node right after the head sentinel.

Common mistakes

Losing the rest of the list. Changing current.next before saving it cuts the list in two. Save after = current.next first.
Forgetting to update tail when you remove the last node or add to an empty list.
Checking fast.next.next without checking fast.next. On a short list this raises AttributeError: 'NoneType' object has no attribute 'next'.
Using a linked list for random access. If you need items[i] often, an array is the right choice.

Key points

A linked list is a chain of nodes; each node stores a value and a reference to the next node.
Insert and remove at the head are O(1); reaching position i is O(i).
Reverse a list in place by turning each next around while remembering the next node.
Fast and slow pointers find the middle and detect cycles with O(1) extra space.
A doubly linked list adds prev, allowing O(1) removal of a known node; sentinels remove edge cases.
A hash table plus a doubly linked list gives an LRU cache.

Exercise

Write a function remove_nth_from_end(head, n) that removes the n-th node from the end of a singly linked list in one pass and returns the new head. Test it on the stations ["Pune", "Lonavala", "Karjat", "Kalyan", "Dadar"] with n = 2 (which removes Kalyan) and with n = 5 (which removes the head). Hint: move a fast pointer n nodes ahead first, then move both pointers together.

Show solution

Python

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

def build(values):
    head = None
    for v in reversed(values):
        head = Node(v, head)
    return head

def to_list(head):
    out = []
    while head:
        out.append(head.value)
        head = head.next
    return out

def remove_nth_from_end(head, n):
    dummy = Node(None, head)        # a sentinel makes removing the head easy
    fast = slow = dummy
    for _ in range(n):
        fast = fast.next
    while fast.next:
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next      # slow is just before the target
    return dummy.next

stations = ["Pune", "Lonavala", "Karjat", "Kalyan", "Dadar"]
print(to_list(remove_nth_from_end(build(stations), 2)))
print(to_list(remove_nth_from_end(build(stations), 5)))

Output

['Pune', 'Lonavala', 'Karjat', 'Dadar']
['Lonavala', 'Karjat', 'Kalyan', 'Dadar']

The gap of n nodes between fast and slow stays fixed, so when fast reaches the last node, slow stands just before the node to remove. The dummy node handles the head case without an extra if.

Quick Quiz

1. What is the cost of inserting a new node at the head of a singly linked list?

2. Why do you save after = current.next before reversing the link?

3. In Floyd's cycle detection, what happens if the list has a cycle?

4. What extra ability does a doubly linked list give you?

The prev reference lets a node unlink itself from both neighbours directly.

Web Development

Programming Languages

Databases

Data Science & AI

Cloud & DevOps

Security & Systems

Office & Productivity

Linked Lists

Nodes and links

A linked list class

Reversing a linked list

Fast and slow pointers

Doubly linked lists

Common mistakes

Key points

Exercise

Quick Quiz

Learn DSA with a mentor