Linked Lists Data Structure Explained

A Linked List is a linear data structure where elements are stored as nodes. Each node contains data and a reference to another node. Unlike arrays, linked lists do not require elements to be stored next to each other in memory.

Linked Lists are important in Data Structures and Algorithms because they teach how dynamic data structures work. They are useful for understanding memory references, insertion, deletion, traversal, and how more advanced structures such as stacks, queues, hash tables, graphs, and adjacency lists can be built.

Introduction

In programming, data is often stored in collections. Arrays are one of the most common collections because they are simple and allow fast access by index. However, arrays have limitations when frequent insertions and deletions are needed, especially in the middle or beginning of the collection.

A Linked List solves a different type of problem. Instead of placing all elements in continuous memory locations, it stores each element inside a node. Each node knows where the next node is located.

This makes Linked Lists flexible. Nodes can be created and connected dynamically while the program is running. Understanding Linked Lists helps developers understand references, pointers, memory allocation, and the internal design of many data structures.

What Is a Linked List?

A Linked List is a sequence of nodes connected together using references. Each node usually contains two parts:

  • Data: The actual value stored in the node.

  • Next reference: A reference or pointer to the next node in the list.

A simple linked list can be represented like this:

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

The first node contains 10 and points to the second node. The second node contains 20 and points to the third node. The third node contains 30 and points to null, which means the list ends there.

The first node is usually called the head of the linked list.

Linked List Terminology

Before studying Linked List operations, it is important to understand the common terms.

  • Node: A single element in the linked list.

  • Head: The first node in the linked list.

  • Tail: The last node in the linked list.

  • Next: A reference from one node to the next node.

  • Previous: A reference to the previous node, used in doubly linked lists.

  • Null: A value that indicates there is no next node.

These terms appear in almost every linked list implementation.

Why Linked Lists Are Important in DSA

Linked Lists are important because they introduce the idea of connecting data using references instead of relying on indexes. This is a major step in learning Data Structures and Algorithms.

Linked Lists help developers understand:

  • Dynamic memory allocation.

  • References and pointers.

  • Node-based data structures.

  • Efficient insertion and deletion.

  • Traversal logic.

  • How stacks and queues can be implemented.

  • How graph adjacency lists work.

Even if developers do not manually implement linked lists every day, the concepts behind them appear in many real systems.

Linked Lists vs Arrays

Arrays and Linked Lists are both linear data structures, but they store and manage data differently.

An array stores elements in contiguous memory locations. This means elements are placed next to each other in memory, and each element can be accessed quickly using an index.

Array:
Index:  0   1   2
Value: 10  20  30

A Linked List stores elements as separate nodes. Each node points to the next node.

Linked List:
[10] → [20] → [30] → null

Main differences include:

  • Arrays provide fast random access using indexes.

  • Linked Lists require traversal to reach a specific position.

  • Arrays may require shifting elements during insertion or deletion.

  • Linked Lists can insert or delete nodes efficiently when the position is known.

  • Arrays use continuous memory.

  • Linked Lists use nodes that can be stored in different memory locations.

Neither structure is always better. The best choice depends on the problem.

DSA Linked Lists in Memory

One of the most important ideas behind Linked Lists is how they are stored in memory.

In an array, elements are stored next to each other:

Memory:
Address 1000 → 10
Address 1004 → 20
Address 1008 → 30
Address 1012 → 40

Because the elements are contiguous, the program can calculate the address of any element using the base address and index.

In a Linked List, nodes do not need to be stored next to each other:

Memory:
Address 2040 → [10 | next: 9000]
Address 9000 → [20 | next: 3050]
Address 3050 → [30 | next: null]

The nodes may be located anywhere in memory. Each node stores a reference to the next node, so the list can be followed from one node to another.

Why Memory Representation Matters

Memory representation matters because it explains the strengths and weaknesses of Linked Lists.

Since nodes are connected by references, inserting a new node does not require shifting all elements like an array. The program only changes references.

For example, to insert 15 between 10 and 20:

Before:
[10] → [20] → [30]

After:
[10] → [15] → [20] → [30]

The new node can be created anywhere in memory. The reference from 10 is changed to point to 15, and 15 points to 20.

However, this also means Linked Lists do not support direct index access efficiently. To reach the third node, the program must start from the head and follow links step by step.

Structure of a Node

A node is the basic building block of a Linked List. In a singly linked list, a node contains data and a next reference.

Node:
+------+------+
| data | next |
+------+------+

For example:

+------+------+
|  10  |  →   |
+------+------+

In code, a node can be represented as an object or class.

Node Example in PHP

<?php

class Node
{
    public mixed $data;
    public ?Node $next = null;

    public function __construct(mixed $data)
    {
        $this->data = $data;
    }
}

This PHP class represents a simple node. The data property stores the value, and the next property stores a reference to the next node.

Node Example in JavaScript

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

The JavaScript version follows the same structure. Each node stores data and a reference to the next node.

Types of Linked Lists

There are several types of Linked Lists. Each type changes how nodes are connected and what operations are easier to perform.

The main types are:

  • Singly Linked List.

  • Doubly Linked List.

  • Circular Linked List.

  • Circular Doubly Linked List.

Understanding these types helps developers choose the correct structure for different problems.

Singly Linked List

A Singly Linked List is the simplest type of linked list. Each node contains data and a reference to the next node.

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

Traversal is only possible in one direction: from head to tail.

A Singly Linked List is useful when:

  • Forward traversal is enough.

  • Memory usage should be lower than a doubly linked list.

  • Insertions and deletions are mainly done at the beginning.

  • A simple node-based structure is needed.

The limitation is that moving backward is not possible because nodes do not store references to previous nodes.

Doubly Linked List

A Doubly Linked List stores two references in each node: one to the next node and one to the previous node.

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

This allows traversal in both directions.

A node in a doubly linked list usually contains:

  • Data.

  • Next reference.

  • Previous reference.

Doubly Linked Lists are useful when:

  • Forward and backward traversal are needed.

  • Deleting a known node should be efficient.

  • Navigation-like behavior is needed.

  • Undo and redo systems are implemented.

The trade-off is that each node requires extra memory for the previous reference.

Circular Linked List

A Circular Linked List is a linked list where the last node points back to the first node instead of pointing to null.

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

This creates a loop.

Circular Linked Lists are useful when:

  • The process needs to cycle repeatedly through elements.

  • Round-robin scheduling is needed.

  • A circular playlist or turn-based system is required.

  • The end should naturally connect back to the beginning.

The important warning is that traversal must have a stopping condition. Otherwise, the program may loop forever.

Circular Doubly Linked List

A Circular Doubly Linked List combines both ideas. Each node has next and previous references, and the last node connects back to the first node while the first node connects back to the last node.

┌──────────────────────┐
↓                      ↑
[10] ⇄ [20] ⇄ [30]
↑                      ↓
└──────────────────────┘

This type supports forward and backward circular traversal.

It is useful in systems where continuous navigation is needed, such as circular buffers, advanced playlists, and some low-level data structures.

The trade-off is higher implementation complexity and extra memory per node.

Linked List Operations

Linked Lists support several important operations. The most common operations are:

  • Traversal.

  • Insertion at the beginning.

  • Insertion at the end.

  • Insertion at a specific position.

  • Deletion from the beginning.

  • Deletion from the end.

  • Deletion by value.

  • Search.

  • Update.

  • Reverse.

Each operation depends on changing references correctly.

Traversal Operation

Traversal means visiting each node in the linked list from the head to the end.

For example:

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

The traversal order is:

10
20
30

Traversal starts from the head node and follows the next references until null is reached.

Traversal Pseudocode

current = head

while current is not null:
    print current.data
    current = current.next

The current pointer moves one node at a time.

Insertion at the Beginning

Insertion at the beginning means adding a new node before the current head.

Suppose the list is:

[20] → [30] → null

We want to insert 10 at the beginning.

The steps are:

  1. Create a new node with value 10.

  2. Make the new node point to the current head.

  3. Update head to the new node.

The result is:

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

This operation is efficient because it does not require traversing the list.

Insertion at the End

Insertion at the end means adding a new node after the last node.

Suppose the list is:

[10] → [20] → null

We want to insert 30 at the end.

The steps are:

  1. Create a new node with value 30.

  2. Start from the head.

  3. Move until the last node is reached.

  4. Make the last node point to the new node.

The result is:

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

If the list maintains a tail reference, insertion at the end can be O(1). Without a tail reference, it is O(n) because traversal is needed.

Insertion at a Specific Position

Insertion at a specific position means adding a node between existing nodes.

Suppose the list is:

[10] → [30] → null

We want to insert 20 between 10 and 30.

The steps are:

  1. Create a new node with value 20.

  2. Find the node after which the new node should be inserted.

  3. Make the new node point to the next node.

  4. Make the previous node point to the new node.

The result is:

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

The order of reference updates is important. If references are changed incorrectly, part of the list may be lost.

Deletion from the Beginning

Deletion from the beginning removes the head node.

Suppose the list is:

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

To remove 10, we update the head to point to the next node.

head = head.next

The result is:

[20] → [30] → null

This operation is O(1) because no traversal is needed.

Deletion from the End

Deletion from the end removes the last node.

Suppose the list is:

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

To delete 30 in a singly linked list, we need to find the node before the last node.

The node before 30 is 20. We set its next reference to null.

[10] → [20] → null

This operation is O(n) in a singly linked list because we must traverse to find the second-last node.

Deletion by Value

Deletion by value means removing the first node that contains a specific value.

Suppose the list is:

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

We want to delete 20.

The algorithm searches for the node containing 20 and keeps track of the previous node. Then it changes the previous node's next reference.

Before:
[10] → [20] → [30] → null

After:
[10] → [30] → null

If the value is found at the head, the head must be updated.

Search Operation

Search means finding whether a value exists in the linked list.

Since Linked Lists do not support direct index access like arrays, search requires traversal.

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

To search for 30, the algorithm checks:

10 → not found
20 → not found
30 → found

The time complexity of search is O(n) because in the worst case the algorithm may need to check every node.

Update Operation

Update means changing the value of a node.

For example:

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

If we want to update 20 to 25, we first search for 20, then change its data.

[10] → [25] → [30] → null

The search part takes O(n), while the actual update is O(1) once the node is found.

Reverse Operation

Reversing a linked list means changing the direction of all next references.

Before reversing:

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

After reversing:

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

This is a common interview and algorithm problem because it tests understanding of references.

The typical iterative solution uses three pointers:

  • previous: The previous node.

  • current: The current node.

  • next: The next node saved before changing the link.

Manual Run for Linked List Operations

Let us manually run this sequence:

insertFirst(20)
insertFirst(10)
insertLast(30)
search(20)
delete(20)
insertLast(40)

Start with an empty list:

head = null

After insertFirst(20):

[20] → null

After insertFirst(10):

[10] → [20] → null

After insertLast(30):

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

Now search for 20:

Check 10 → not found
Check 20 → found

Now delete 20:

[10] → [30] → null

Now insert 40 at the end:

[10] → [30] → [40] → null

This manual run shows how linked list operations depend on changing node references.

Singly Linked List Implementation in PHP

Here is a clean PHP implementation of a Singly Linked List with common operations.

<?php

class ListNode
{
    public mixed $data;
    public ?ListNode $next = null;

    public function __construct(mixed $data)
    {
        $this->data = $data;
    }
}

class LinkedList
{
    private ?ListNode $head = null;

    public function insertFirst(mixed $data): void
    {
        $newNode = new ListNode($data);
        $newNode->next = $this->head;
        $this->head = $newNode;
    }

    public function insertLast(mixed $data): void
    {
        $newNode = new ListNode($data);

        if ($this->head === null) {
            $this->head = $newNode;
            return;
        }

        $current = $this->head;

        while ($current->next !== null) {
            $current = $current->next;
        }

        $current->next = $newNode;
    }

    public function search(mixed $target): bool
    {
        $current = $this->head;

        while ($current !== null) {
            if ($current->data === $target) {
                return true;
            }

            $current = $current->next;
        }

        return false;
    }

    public function delete(mixed $target): bool
    {
        if ($this->head === null) {
            return false;
        }

        if ($this->head->data === $target) {
            $this->head = $this->head->next;
            return true;
        }

        $current = $this->head;

        while ($current->next !== null) {
            if ($current->next->data === $target) {
                $current->next = $current->next->next;
                return true;
            }

            $current = $current->next;
        }

        return false;
    }

    public function toArray(): array
    {
        $items = [];
        $current = $this->head;

        while ($current !== null) {
            $items[] = $current->data;
            $current = $current->next;
        }

        return $items;
    }
}

$list = new LinkedList();

$list->insertFirst(20);
$list->insertFirst(10);
$list->insertLast(30);

print_r($list->toArray());

var_dump($list->search(20));

$list->delete(20);

print_r($list->toArray());

This implementation includes insertion at the beginning, insertion at the end, search, delete, and conversion to an array for display.

Singly Linked List Implementation in JavaScript

Here is a JavaScript implementation of a Singly Linked List.

class ListNode {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
    }

    insertFirst(data) {
        const newNode = new ListNode(data);
        newNode.next = this.head;
        this.head = newNode;
    }

    insertLast(data) {
        const newNode = new ListNode(data);

        if (this.head === null) {
            this.head = newNode;
            return;
        }

        let current = this.head;

        while (current.next !== null) {
            current = current.next;
        }

        current.next = newNode;
    }

    search(target) {
        let current = this.head;

        while (current !== null) {
            if (current.data === target) {
                return true;
            }

            current = current.next;
        }

        return false;
    }

    delete(target) {
        if (this.head === null) {
            return false;
        }

        if (this.head.data === target) {
            this.head = this.head.next;
            return true;
        }

        let current = this.head;

        while (current.next !== null) {
            if (current.next.data === target) {
                current.next = current.next.next;
                return true;
            }

            current = current.next;
        }

        return false;
    }

    toArray() {
        const items = [];
        let current = this.head;

        while (current !== null) {
            items.push(current.data);
            current = current.next;
        }

        return items;
    }
}

const list = new LinkedList();

list.insertFirst(20);
list.insertFirst(10);
list.insertLast(30);

console.log(list.toArray());
console.log(list.search(20));

list.delete(20);

console.log(list.toArray());

The JavaScript version follows the same logic as the PHP version. The linked list is built from nodes, and each node points to the next node.

Reverse a Linked List in JavaScript

Reversing a linked list is one of the most important linked list problems.

reverse() {
    let previous = null;
    let current = this.head;

    while (current !== null) {
        const nextNode = current.next;
        current.next = previous;
        previous = current;
        current = nextNode;
    }

    this.head = previous;
}

The idea is to reverse each link one by one. Before changing current.next, we save the next node so the rest of the list is not lost.

Time Complexity of Linked List Operations

Time complexity describes how the running time of an operation grows as the number of nodes increases.

For a Singly Linked List, common complexities are:

  • Access by index: O(n)

  • Search: O(n)

  • Traversal: O(n)

  • Insert at beginning: O(1)

  • Delete from beginning: O(1)

  • Insert at end without tail: O(n)

  • Insert at end with tail: O(1)

  • Delete from end: O(n)

  • Delete known node after previous node: O(1)

The key idea is that Linked Lists are strong when inserting or deleting near known positions, but weak when random access is needed.

Space Complexity of Linked Lists

The space complexity of a Linked List is O(n), where n is the number of nodes.

Each node stores data and at least one reference. This means Linked Lists usually use more memory than arrays for the same number of values because every node has reference overhead.

For a Singly Linked List:

Node = data + next reference

For a Doubly Linked List:

Node = previous reference + data + next reference

Doubly Linked Lists provide more flexibility but require more memory.

Advantages of Linked Lists

Linked Lists have several advantages.

  • They can grow and shrink dynamically.

  • Insertion at the beginning is O(1).

  • Deletion from the beginning is O(1).

  • They do not require contiguous memory.

  • They are useful for implementing stacks and queues.

  • They help understand references and dynamic structures.

These advantages make Linked Lists useful in problems where data changes frequently.

Disadvantages of Linked Lists

Linked Lists also have important disadvantages.

  • They do not support fast random access.

  • Searching takes O(n).

  • Accessing an element by index takes O(n).

  • They use extra memory for references.

  • They can be harder to implement correctly than arrays.

  • Poor reference handling can break the list.

Because of these disadvantages, arrays are often better when fast indexing is needed.

Linked Lists in Real Software Projects

In high-level web development, developers may not manually implement Linked Lists often. Languages and frameworks usually provide built-in arrays, lists, collections, queues, and maps.

However, Linked List ideas appear in many places:

  • Stacks and queues.

  • Undo and redo systems.

  • Browser history navigation.

  • Music playlists.

  • Memory management.

  • Graph adjacency lists.

  • Hash table collision handling in some implementations.

  • Operating system scheduling.

Understanding Linked Lists makes it easier to understand how these systems can be designed internally.

Common Mistakes When Learning Linked Lists

Beginners often make mistakes because Linked Lists require careful reference management.

Common mistakes include:

  • Forgetting to update the head after insertion or deletion.

  • Losing the rest of the list while changing references.

  • Not handling an empty list.

  • Not handling deletion of the first node.

  • Creating an infinite loop in circular linked lists.

  • Confusing node data with node reference.

  • Trying to access linked list elements like array indexes.

The safest approach is to draw the nodes and references before writing code.

Practical Checklist for Understanding Linked Lists

Before moving to advanced data structures, developers should be able to answer these questions:

  • What is a node?

  • What is the head of a linked list?

  • Why are linked list nodes not required to be contiguous in memory?

  • What is the difference between a singly and doubly linked list?

  • How does insertion at the beginning work?

  • How does deletion by value work?

  • Why is search O(n)?

  • Why is insertion at the beginning O(1)?

  • What happens if references are updated in the wrong order?

  • How can a linked list be reversed?

If these questions are clear, the developer understands the real logic of Linked Lists.

Conclusion

A Linked List is a linear data structure made of nodes connected by references. Each node stores data and a link to another node. Unlike arrays, linked lists do not require elements to be stored in contiguous memory locations.

Linked Lists are important because they teach dynamic memory, references, node-based thinking, insertion, deletion, traversal, and the internal behavior of many data structures.

The main types include Singly Linked Lists, Doubly Linked Lists, Circular Linked Lists, and Circular Doubly Linked Lists. Each type has different strengths and trade-offs.

Linked List operations include traversal, insertion, deletion, search, update, and reverse. Insertions and deletions can be efficient when the position is known, but search and random access require O(n) time.

For developers learning Data Structures and Algorithms, Linked Lists are a core topic. They build the foundation for understanding stacks, queues, graphs, memory references, and many advanced algorithmic problems.