What is a Linked List?

The Problem with Arrays

You have a playlist with 100 songs. You want to add a new song at position 10. With an array, you must shift 90 songs one position to the right to make room. That's 90 copy operations just to insert one item. Arrays store elements in contiguous memory, so inserting in the middle requires moving everything after it.

Linked lists solve this problem by storing elements differently. Instead of keeping everything in one continuous block, linked lists scatter elements throughout memory and connect them with pointers.

Nodes Store Data and Pointer

A linked list stores elements in nodes. Each node contains two parts: the data itself and a pointer to the next node.

Node Structure

Think of a treasure hunt where each clue tells you where to find the next clue. The clue itself is the data, and the directions to the next clue are the pointer. You can't jump directly to the fifth clue - you must follow the chain from the first clue to the second, then to the third, and so on.

Following the Chain

A linked list starts with a head pointer that points to the first node. Each node points to the next node in the sequence. The last node points to nothing, which we represent as null (or None in Python). This null pointer marks the end of the list.

Linked List Chain

To access any element, you start at the head and follow the pointers. Want the third element? Start at the head, follow its pointer to the second node, then follow that pointer to the third node.

Scattered in Memory

Arrays store elements in contiguous memory addresses. If the first element is at address 1000, the second is at 1004, the third at 1008, and so on. Everything sits next to each other.

Linked lists scatter nodes wherever memory is available. The first node might be at address 1000, the second at address 5000, the third at address 2000. The nodes don't need to be next to each other because the pointers connect them.

Memory Layout Comparison

Why This Structure Helps

Inserting a new node between two existing nodes becomes simple. Create the new node, point it to the node that should come after it, then change the previous node's pointer to point to the new node. You've inserted an element by changing two pointers. No shifting required.

The same applies to deletion. To remove a node, change the previous node's pointer to skip over the node you want to remove and point directly to the node after it. The removed node is now disconnected from the chain.

The Null Terminator

The last node in a linked list always has its next pointer set to null. This tells you there are no more nodes to visit. When traversing a linked list, you keep following pointers until you reach null, which signals the end.

Without this null terminator, you wouldn't know when to stop. The list would appear infinite, and your code would try to follow a pointer that doesn't point anywhere valid, causing crashes.

A Simple Linked List Example

1class Node:
2    def __init__(self, data):
3        self.data = data
4        self.next = None
5
6# Creating three nodes
7head = Node(1)
8second = Node(2)
9third = Node(3)
10
11# Linking them together
12head.next = second
13second.next = third
14# third.next is None (null) by default
15
16# This creates: 1 -> 2 -> 3 -> None

Python doesn't have a built-in linked list, so we create a simple Node class.

Linked List vs Array Preview

Arrays give you direct access to any element. Want element 50? Just use arr[50] and you get it instantly. Linked lists require traversal. To reach the 50th node, you must follow 49 pointers starting from the head.

But linked lists excel at insertion and deletion at the beginning. Adding to the front of an array means shifting every element. Adding to the front of a linked list means creating one node and updating two pointers. The trade-off becomes clear: arrays optimize for access speed, linked lists optimize for modification flexibility.

The next article explores nodes and pointers in detail, showing exactly how to create, link, and manipulate them.