DSA Linked List

Overview

A linked list stores elements as separate nodes connected by links rather than in continuous memory. Linked lists are particularly useful when data must be added or removed frequently and form a foundation for stacks, queues, trees, and graphs.

Key concepts

• Each node stores data and a reference to the next node
• The first node is the head
• The final node points to null
• Nodes are reached by following links instead of using direct indexes

What is a Linked List?

A linked list is a collection of connected nodes. Unlike array elements, nodes do not need to be adjacent in memory because each node stores the location of the next node.

Head
 ↓
[10 | next] → [20 | next] → [30 | next] → [40 | null]

Here, 10 is stored in the head node, 40 is stored in the final node, and null marks the end of the list.

Why do we need a Linked List?

Inserting an element at the beginning of a large array requires shifting every existing element. A linked list can perform the same insertion by creating a node and changing a small number of links. This makes linked lists useful when additions and removals are frequent.

Creating a Node

A JavaScript object can represent a node with data and next properties.

const node = {
  data: 10,
  next: null
};

console.log(node);
// { data: 10, next: null }

Creating a simple Linked List

const third = {
  data: 30,
  next: null
};

const second = {
  data: 20,
  next: third
};

const first = {
  data: 10,
  next: second
};

10 → 20 → 30 → null

Traversing a Linked List

Traversal starts at the head and follows next references until the current node becomes null.

let current = first;

while (current !== null) {
  console.log(current.data);
  current = current.next;
}
// 10, 20, 30

Types of Linked Lists

Singly Linked List

Each node points only to the next node. This is the simplest and most common linked list.

10 → 20 → 30 → null

Doubly Linked List

Each node stores references to both the previous and next nodes, allowing movement in either direction.

null ← 10 ⇄ 20 ⇄ 30 → null

Circular Linked List

The final node links back to the head instead of null, creating a continuous loop.

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

Time complexity of common operations

A linked list does not support direct index access. Reaching a particular position requires following nodes from the head. Keeping a tail reference can make insertion at the end O(1).

Advantages of Linked Lists

• Fast insertion at the beginning
• Fast deletion at the beginning
• Dynamic size that can grow or shrink
• No requirement for continuous memory
• Easy node rearrangement through link updates

Limitations of Linked Lists

• No random index-based access
• Searching requires O(n) traversal
• References consume additional memory
• Following nodes can be less cache-friendly than traversing an array

Real-life example

Imagine a treasure hunt where every clue reveals the location of the next clue. You cannot jump directly to the final clue; you must follow each link in order. A linked list behaves in the same way.

Where are Linked Lists used?

• Music playlists
• Browser history
• Undo and redo systems
• Image viewers
• Memory management
• File systems
• Stack and queue implementations

Tips for beginners

• Understand one node before building a list
• Draw nodes and links on paper
• Practice traversal before insertion and deletion
• Compare operation costs with arrays
• Practice reversing a list and finding its middle node