Linked List

So far, we've seen arrays, where elements are stored in a fixed-size sequence and we can access them directly using an index.

But arrays have one major limitation: their size is fixed.

What if we don't know how many elements we will need? Or what if we frequently need to insert and remove elements?

This is where a linked list becomes useful.

A linked list is a data structure where elements are stored in separate objects called nodes, and each node contains the data along with a reference to the next node.

What is a Node?

Before understanding a linked list, let's understand a node.

A node usually contains two things:

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

The data stores the actual value.

The next reference points to the next node.

For example:

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

Here, 10 is connected to 20, and 20 is connected to 30.

The last node points to null, which means there is no next node.

Creating a Node in Java

We can create a simple node class:

class Node {
    int data;
    Node next;

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

Now we can create nodes:

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

But right now, they are separate objects.

We need to connect them:

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

Now we have:

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

This is a simple linked list.

Head of a Linked List

We usually keep track of the first node using a variable called head.

Node head = first;

Now:

head
  ↓
10 → 20 → 30 → null

The head is very important because it gives us access to the entire linked list.

If we lose the head, we may lose our way to the rest of the nodes.

Traversing a Linked List

Unlike an array, we don't have indexes that allow us to directly access elements.

Instead, we start from the head and follow the next references.

Node current = head;

while (current != null) {

    System.out.println(current.data);

    current = current.next;
}

Output:

10
20
30

The process looks like:

head
 ↓
10 → 20 → 30 → null
     ↓
   move forward

We keep moving to current.next until we reach null.

Adding a Node

One of the advantages of a linked list is that we can insert nodes without creating a completely new array.

Suppose we have:

10 → 20 → 30

and we want to insert 15 between 10 and 20.

We can change the links:

10 → 15 → 20 → 30

In Java:

Node newNode = new Node(15);

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

Now the list becomes:

10 → 15 → 20 → 30 → null

The important thing is that we're changing references rather than shifting all the existing elements.

Adding a Node at the Beginning

Adding a node at the beginning is even simpler.

Suppose:

10 → 20 → 30

We want to add 5.

First, create the node:

Node newNode = new Node(5);

Make it point to the current head:

newNode.next = head;

Then make the new node the head:

head = newNode;

Now:

head
 ↓
5 → 10 → 20 → 30 → null

This operation is very efficient.

Removing a Node

Suppose we have:

10 → 20 → 30

and we want to remove 20.

We need to change the connection:

10 → 30

In other words, instead of:

10 → 20 → 30

we make 10 point directly to 30.

first.next = first.next.next;

Now:

10 → 30 → null

The node containing 20 is no longer part of the list.

Linked List vs Array

Arrays and linked lists both store collections of data, but they work differently.

With an array:

10 | 20 | 30 | 40 | 50

The elements are accessed using indexes:

numbers[3]

With a linked list:

10 → 20 → 30 → 40 → 50

We follow links from one node to the next.

This creates some important differences.

*For a typical fixed array when shifting elements is required.

The biggest advantage of a linked list is that insertion and deletion can be very efficient when we already have the appropriate node/reference.

Why Is Access O(n)?

Suppose we want the fourth element:

10 → 20 → 30 → 40 → 50

With an array, we can directly use:

numbers[3]

That's O(1).

With a linked list, we have to start from the head:

10
 ↓
20
 ↓
30
 ↓
40

We have to follow the links until we reach 40.

So accessing an element by position takes:

O(n)

in the worst case.

Types of Linked Lists

There are several types of linked lists.

The most basic one is the singly linked list, where each node points only to the next node:

10 → 20 → 30 → null

A doubly linked list has references to both the next and previous nodes:

null ← 10 ⇄ 20 ⇄ 30 → null

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

10 → 20 → 30
↑         ↓
└─────────┘

We'll explore these different types separately.

A Simple Linked List Implementation

Let's create a basic linked list and print all its elements:

class Node {
    int data;
    Node next;

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

class Main {
    public static void main(String[] args) {

        Node head = new Node(10);

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

        Node current = head;

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

Output:

10
20
30

Although this example is small, it demonstrates the fundamental idea: each node stores data and a reference to the next node.

Java's Built-in Linked List

Java already provides a LinkedList class in the Collections Framework.

For example:

import java.util.LinkedList;

class Main {
    public static void main(String[] args) {

        LinkedList<String> names = new LinkedList<>();

        names.add("John");
        names.add("Jason");
        names.add("Alex");

        System.out.println(names);
    }
}

Output:

[John, Jason, Alex]

You can use methods such as:

names.addFirst("Michael");
names.addLast("David");
names.removeFirst();
names.removeLast();

However, when learning DSA, it's important to understand how a linked list works internally rather than only using Java's built-in class.

A Real-Life Example

Think about a treasure hunt.

You find a note that says:

The next clue is at location B.

At location B, another note says:

The next clue is at location C.

And so on.

Clue A → Clue B → Clue C → Clue D

Each clue knows where the next clue is, but it doesn't necessarily know about all the other clues.

That's similar to a singly linked list.

Each node contains its data and a reference to the next node.

When Should You Use a Linked List?

Linked lists can be useful when:

• The collection needs frequent insertions or deletions.

• You don't need fast random access by index.

• The size of the data can change frequently.

• You already have a reference to the position where an insertion or deletion needs to happen.

However, linked lists aren't always better than arrays. If you frequently need to access elements by index, an array is usually much more efficient.

The main idea is:

A linked list is a collection of nodes where each node stores data and a reference to another node, allowing the nodes to be connected together.

Once you understand Node, head, next, and how we traverse the list, the rest of linked lists becomes much easier.