Shankar L

Posted on Sep 1

Linked Lists

#beginners #tutorial #architecture #programming

Why should you care?

Arrays are excellent when you need fast access by index, but they become inconvenient when data needs to be frequently inserted or removed.

Linked lists solve a different problem: they allow elements to be connected through references, so elements don't necessarily need to sit next to each other in memory.

Linked lists are important because they introduce ideas that appear throughout computer science:

Dynamic data structures
Pointers and references
Nodes and connections
Memory allocation
Stacks and queues
Graphs and trees
Linked data structures

Understanding linked lists also makes concepts like pointers, references, and memory management much easier to understand.

The Problem

Consider an array:

10  20  30  40  50

Suppose we want to insert 25 between 20 and 30.

The array may need to move several elements:

Before:
10  20  30  40  50

After:
10  20  25  30  40  50

This shifting becomes expensive when the collection is large.

We need a structure where we can:

Add or remove elements without having to shift an entire sequence of elements.

That's where linked lists become useful.

The Concept

A linked list is a sequence of nodes, where each node stores:

A value
A reference to another node

A simple singly linked list looks like this:

┌───────┬────────┐
│ Value │  Next  │
└───────┴────────┘
    │        │
    10       ──────────┐
                       ↓
                  ┌───────┬────────┐
                  │ Value │  Next  │
                  └───────┴────────┘
                      │        │
                      20       ──────────┐
                                         ↓
                                    ┌───────┬────────┐
                                    │ Value │  Next  │
                                    └───────┴────────┘
                                        │
                                        30

Or more simply:

HEAD
 ↓
[10 | •] → [20 | •] → [30 | null]

The important difference from an array is that the nodes are connected using references, rather than relying on indexes.

Simple Explanation

Imagine three people standing in different locations.

The first person knows:

"The next person is John."

John knows:

"The next person is Alex."

Alex knows:

"There is nobody after me."

That's essentially a linked list.

Person 1 → Person 2 → Person 3 → Nothing

Each node contains information about where the next node is.

A linked list therefore doesn't need to know where every element is.

It only needs to know:

Where is the first node?
        ↓
Where is the next node?
        ↓
Where is the next node?
        ↓
...

This first node is usually called the head.

Real-world Analogy

Imagine a treasure hunt.

You find the first clue:

Clue 1
"Go to the tree."

At the tree, you find:

Clue 2
"Go to the old bridge."

At the bridge:

Clue 3
"Go to the house."

You don't have a complete map of all locations.

Each clue simply tells you where to find the next clue.

That's how a linked list works:

Node 1 → Node 2 → Node 3 → Node 4

Each node contains the information needed to reach the next node.

Code Example

Here's a simple singly linked list in Java:

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
    }
}

We can create nodes:

Node first = new Node(10);
Node second = new Node(20);
Node third = new Node(30);

Then connect them:

first.next = second;
second.next = third;

Now we have:

first
  ↓
[10] → [20] → [30] → null

We can traverse the list using a loop:

Node current = first;

while (current != null) {
    System.out.println(current.data);
    current = current.next;
}

Output:

10
20
30

Notice this line:

current = current.next;

This is the fundamental operation of linked-list traversal.

We're saying:

"Move from the current node to the node that it points to."

Inserting a node

Suppose we want:

10 → 20 → 30

and want to insert 15 between 10 and 20.

We can change the links:

Before:

10 → 20 → 30


After:

10 → 15 → 20 → 30

Conceptually:

Node newNode = new Node(15);

newNode.next = first.next;
first.next = newNode;

The important part is that we don't need to move 20 or 30.

We simply change the references.

Common Mistakes

Mistake 1: Thinking linked-list nodes must be next to each other in memory

They don't.

An array generally stores elements sequentially:

Memory:

[10][20][30][40]

Linked-list nodes can be scattered:

Memory:

[10]       [30]
   [20]              [40]

The links connect them logically:

[10] → [20] → [30] → [40]

The physical memory locations don't have to be adjacent.

Mistake 2: Thinking linked lists provide fast indexing

Consider:

10 → 20 → 30 → 40 → 50

If you want the fifth element, you cannot simply do the equivalent of:

list[4]

You have to start from the head:

10 → 20 → 30 → 40 → 50
↑                   ↑
Start              Target

You must follow each link until you reach the target.

Therefore, accessing the element at position n takes O(n) time.

Mistake 3: Losing the reference to the list

Consider:

Node head = new Node(10);
head.next = new Node(20);

If you overwrite head incorrectly:

head = new Node(50);

you may lose your reference to the original list:

10 → 20

because nothing points to its first node anymore.

This is why maintaining the head reference is critical.

Advanced Notes

1. Time complexity

For a typical singly linked list:

Operation	Complexity
Access by index	O(n)
Search	O(n)
Insert at beginning	O(1)
Delete from beginning	O(1)
Insert after known node	O(1)
Delete after known node	O(1)
Insert at end	O(n)*

Unless the list maintains a **tail pointer*, in which case insertion at the end can be O(1).

Compare this with an array:

Operation	Array	Linked List
Access by index	O(1)	O(n)
Search	O(n)	O(n)
Insert at beginning	O(n)	O(1)
Delete at beginning	O(n)	O(1)

This reveals an important principle:

There is no universally "better" data structure. The right structure depends on the operations you perform most often.

2. Singly linked list

Each node points only forward:

[10] → [20] → [30] → null

You can move:

10 → 20 → 30

but not backward.

3. Doubly linked list

A doubly linked list stores two references:

┌────────┬───────┬────────┐
│  Prev  │ Data  │  Next  │
└────────┴───────┴────────┘

So the structure becomes:

null ← [10] ⇄ [20] ⇄ [30] → null

Now you can traverse in both directions.

The trade-off is additional memory for the prev reference.

4. Circular linked list

A circular linked list connects the final node back to the first:

      ┌─────────────────────┐
      ↓                     │
[10] → [20] → [30] → [40] ─┘

There is no null at the end.

Circular lists can be useful for problems involving repeated cycles, such as round-robin scheduling.

5. Memory overhead

An array containing integers might conceptually look like:

[10][20][30][40]

A linked list node contains additional information:

[10 | next]
[20 | next]
[30 | next]
[40 | null]

That next reference consumes memory.

Therefore, linked lists trade additional memory overhead for flexibility in inserting and removing nodes.

The Bigger Picture

Linked lists are an important step toward understanding more complex data structures.

The progression looks something like:

Arrays
   ↓
References / Pointers
   ↓
Linked Lists
   ↓
Stacks & Queues
   ↓
Trees
   ↓
Graphs

The idea of:

Node → Node → Node

is fundamental.

A tree can be thought of as nodes connected in a hierarchy:

A graph generalizes the idea even further:

A ─── B
│   / │
│  /  │
C ─── D

So learning linked lists isn't just learning one data structure.

You're learning how references can be used to construct structures in memory.

The Most Important Mental Model

A linked list is not a row of values. It is a chain of nodes connected by references.

Remember:

HEAD
 ↓
┌──────┬──────┐
│  10  │  ──────────┐
└──────┴──────┘      ↓
                ┌──────┬──────┐
                │  20  │  ──────────┐
                └──────┴──────┘      ↓
                                ┌──────┬──────┐
                                │  30  │ null │
                                └──────┴──────┘

The data is one part of the node.

The reference to the next node is the other important part.

That reference is what creates the chain.

Summary

A linked list is a collection of nodes where each node stores data and a reference to another node.

The key ideas are:

A linked list is built from nodes.
Each node contains data and one or more references.
The first node is called the head.
Nodes don't need to be contiguous in memory.
Traversal happens by following references.
Accessing an arbitrary position takes O(n).
Insertion and deletion can be O(1) when the relevant node/reference is already known.
Singly, doubly, and circular linked lists are common variants.
Linked lists demonstrate how references can create complex structures from independently allocated memory.

An array teaches you how to find data by position; a linked list teaches you how data can find its next piece of data—and that shift in thinking is fundamental to understanding dynamic data structures.

DEV Community