Linked Lists in DSA: Introduction

A linked list is a sequence of values where each value lives in its own little box called a node, and each node holds a reference to the next one. There is no shared block of contiguous memory the way an array has — the nodes can be scattered anywhere, stitched together by pointers. That single design decision changes almost everything about how the structure behaves.

The node

A node holds two things: a value, and a reference to the next node.

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

That’s it. The next attribute is either another Node instance or None, which marks the end of the list.

┌─────┐    ┌─────┐    ┌─────┐
│  1  │───►│  2  │───►│  3  │───► None
└─────┘    └─────┘    └─────┘
head                  tail

We almost always keep a reference to the first node (head). Some implementations also track the last node (tail) so appending stays O(1) instead of walking the whole list.

Singly vs doubly linked

A singly linked list points forward only — each node knows its next. A doubly linked list also points backward — each node knows its prev. Doubly linked nodes cost a little more memory and a little more bookkeeping, but they let you walk in either direction and delete a known node in O(1).

┌─────┐      ┌─────┐      ┌─────┐
None ◄─│  1  │◄────►│  2  │◄────►│  3  │─► None
└─────┘      └─────┘      └─────┘
head                      tail

For interview-style problems you will spend most of your time on singly linked lists, so that is what we will build.

Arrays vs linked lists

The Python list is a dynamic array — a block of contiguous slots that grows as you append. A linked list is the opposite shape. The two have very different cost profiles:

Linked lists shine when you mostly insert and delete in the middle and rarely random-access. Arrays win at almost everything else, which is why they are the default in practice. The reason linked lists still matter is that they are the building block for stacks, queues, hash-map buckets, adjacency lists, and many tree/graph structures — and they are a favourite of interviewers.

Memory layout

The difference is easiest to see in pictures.

Array (contiguous):
┌────┬────┬────┬────┬────┐
│ 10 │ 20 │ 30 │ 40 │ 50 │   one allocation
└────┴────┴────┴────┴────┘
0    1    2    3    4
Linked list (scattered, joined by pointers):
addr 0x10            addr 0x84            addr 0x2c
┌────┬─────┐         ┌────┬─────┐         ┌────┬──────┐
│ 10 │0x84 │────────►│ 20 │0x2c │────────►│ 30 │ None │
└────┴─────┘         └────┴─────┘         └────┴──────┘
head

The cache loves arrays — fetching arr[0] pulls arr[1], arr[2], and a few neighbours into the CPU cache for free. Linked-list nodes have no such locality. Two adjacent values in the list may live a megabyte apart in RAM. This is why, in practice, an array with O(n) operations often beats a linked list with O(1) operations on small sizes.

A singly linked list in Python

A LinkedList class that wraps the chain of nodes and gives it a nice API:

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 __len__(self):
        return self.size

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

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

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

    def __repr__(self):
        return " -> ".join(str(v) for v in self) + " -> None"

Now we can use it like a regular Python container:

ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.prepend(0)
print(ll)         # 0 -> 1 -> 2 -> 3 -> None
print(len(ll))    # 4

The __iter__ method is what lets for value in ll: work, and what gives __repr__ its nice format.

Why head is everything

You only really need the head pointer. From it you can reach every node by walking next references. Lose the head and you have lost the list — Python’s garbage collector will sweep all the nodes away. This is also why so many linked-list bugs come from accidentally reassigning head: one wrong line and your list disappears.

Traversal — the one pattern you will use forever

Almost every linked-list operation begins with the same three lines: start at the head, walk forward until you find what you want or hit None.

def find(ll, target):
    current = ll.head
    while current is not None:
        if current.value == target:
            return current
        current = current.next
    return None

Learn this shape until it’s automatic. You will write it dozens of times.

Searching is linear

There is no ll[3] shortcut. To access the fourth element you must walk three next hops. So even though linked lists have nice insert/delete behaviour, every “access by position” is O(n):

def get(ll, index):
    current = ll.head
    for _ in range(index):
        if current is None:
            raise IndexError("out of range")
        current = current.next
    if current is None:
        raise IndexError("out of range")
    return current.value

If you find yourself indexing a linked list, you probably want an array instead.

When to choose a linked list

In real Python code, almost never directly — the built-in list and collections.deque cover the common needs. You reach for a custom linked list when:

• You are implementing a more complex structure (LRU cache, adjacency list, custom queue) where O(1) splice in the middle matters.
• You are working in a language without a built-in growable array.
• You are sitting in front of an interviewer who asked you to reverse one.

That last reason is not a joke. Linked-list problems are interview classics because they force you to think carefully about pointer manipulation, and the bugs are usually one missing line away.

A small worked example

Build a list, walk it, find a value, print it:

ll = LinkedList()
for word in ["apple", "banana", "cherry", "date"]:
    ll.append(word)

print(ll)                         # apple -> banana -> cherry -> date -> None
print("found:", any(v == "cherry" for v in ll))   # found: True
print("count:", len(ll))          # count: 4

Nothing fancy — but every method we used is one we wrote ourselves on top of a next pointer. That’s the whole story of linked lists.

Practice problems

Solve each before reading the solution.

1. Build from a Python list

def from_list(values):
    ll = LinkedList()
    for v in values:
        ll.append(v)
    return ll

print(from_list([1, 2, 3]))    # 1 -> 2 -> 3 -> None

2. Count nodes without using size

def count(ll):
    n = 0
    current = ll.head
    while current is not None:
        n += 1
        current = current.next
    return n

print(count(from_list([5, 6, 7])))    # 3

3. Sum all values

def total(ll):
    s = 0
    current = ll.head
    while current is not None:
        s += current.value
        current = current.next
    return s

print(total(from_list([1, 2, 3, 4])))    # 10

4. Find the maximum

def maximum(ll):
    if ll.head is None:
        raise ValueError("empty list")
    best = ll.head.value
    current = ll.head.next
    while current is not None:
        if current.value > best:
            best = current.value
        current = current.next
    return best

print(maximum(from_list([3, 9, 2, 7])))    # 9

5. Convert to a Python list

def to_list(ll):
    result = []
    current = ll.head
    while current is not None:
        result.append(current.value)
        current = current.next
    return result

print(to_list(from_list([10, 20, 30])))    # [10, 20, 30]

6. Append vs prepend timing

import time

ll = LinkedList()
start = time.time()
for i in range(100_000):
    ll.append(i)
print("append 100k:", round(time.time() - start, 3), "s")

ll = LinkedList()
start = time.time()
for i in range(100_000):
    ll.prepend(i)
print("prepend 100k:", round(time.time() - start, 3), "s")

Both should be quick — O(1) per call thanks to the tail and head pointers.

Recap

You now know:

• A node is a value plus a reference to the next node
• Singly linked lists go forward; doubly linked lists go both ways
• head (and often tail) anchor the structure
• Arrays win at access; linked lists win at insert/delete with a known node
• Traversal is the one pattern at the heart of every operation
• Python’s built-in list and deque cover almost all real needs

Next steps

Now that the structure is in place, the next post drills the core operations — insert, delete, reverse, find the middle, and detect a cycle. These are the building blocks for every linked-list interview problem.

→ Next: Linked List Operations: Insert, Delete, Reverse

Questions or feedback? Email codeloomdevv@gmail.com.