Abhishek Gupta

Posted on Apr 11 • Edited on Apr 14

🔗 Linked List: 0 100% Mastery Roadmap

🟢 1. WHAT IS A LINKED LIST?

A Linked List is a linear data structure in which elements are stored in the form of nodes, and each node is connected to the next node using a pointer (reference).

Unlike arrays, elements in a linked list are not stored in contiguous memory locations. Instead, they are stored at different (non-contiguous) memory locations and are connected using pointers (or references).

🔹 Basic Concept (Easy Words)

A linked list is made up of nodes (small blocks of data)
Each node contains:
- Data → stores the value
- Next (Pointer) → stores the address of the next node
Nodes are connected using pointers, forming a chain-like structure
Nodes are stored in different (non-contiguous) memory locations

🔹 Important Terms

🔸 HEAD

Pointer to the first node of the list
Entry point to access the linked list

🔸 NODE

Basic unit of a linked list
Contains:
- Data
- Pointer (next address)

🔸 POINTER / REFERENCE

Stores the address of another node
Used to connect nodes together

🔸 NULL

Indicates end of the list
Means no next node exists

🔸 TRAVERSAL

Process of visiting each node
Starts from head and moves till NULL

🔸 LENGTH

Total number of nodes in the list
Found by traversing the entire list

🔸 NEXT

Pointer inside a node
Stores address of the next node

🔸 DYNAMIC MEMORY

Memory is allocated as needed
No need for fixed size

🔸 NON-CONTIGUOUS MEMORY

Nodes are stored in random memory locations
Not stored in sequence like arrays

📌 What is a Node?

👉 A node is like a Container which contains data and a reference to the next node in a linked list.

Think of a node as a basic building block used to create a linked list.

🔹 Simple Real-Life Meaning

Imagine a train:

Each coach (bogie) = a node
Inside each coach = data (passengers)
Connection between coaches = pointer (link)

So, the train works only because all coaches are connected.

👉 Similarly, a linked list works because all nodes are connected.

🔹 What Does a Node Contain?

A node has two parts:

1. 📦 Data (Value)

This is the actual information stored in the node.

Examples:

2. 🔗 Link (Pointer)

This stores the address of the next node.

It tells:
👉 “Where is the next node?”

🔹 Structure of a Node

[ Data | Next ]

Data → value stored in the node
Next → address of the next node

🔹 Example of Linked Nodes

10 → 20 → 30 → 40 → NULL

Explanation:

Each value is stored in a separate node
Each node is connected using a pointer
The last node points to NULL (end of list)

🎯 3. Core Idea (Very Important)

👉 To create a node in a singly linked list, we create an object that contains two properties: value and next.

Instead of creating objects manually, we use a constructor function or class. Using the new keyword, JavaScript creates a new object, assigns value and next, and returns the node.


{
  value: 5,
  next: null
}

👉 This object has:

data (value)
pointer (next)

❌ 4. Problem with Manual Creation

If we create nodes manually:

let node1 = { value: 5, next: null };
let node2 = { value: 10, next: null };

👉 Problems:

Repetitive ❌
Time-consuming ❌
Not scalable ❌

✅ 5. Solution → Use Function / Class

👉 Instead of creating objects manually, we use a constructor function (or class)

So:

We don’t create objects ourselves
We just call a function
It creates the object for us automatically ✅

🏗️ 6. Final Code (Constructor Function)

function Node(val) {
  this.value = val;   // store data
  this.next = null;   // store reference to next node
}

🧠 7. What is Happening Internally?

When you write:

let node1 = new Node(5);

👉 JavaScript performs these steps:

🔥 Step-by-step (Dry Run)

Create empty object:

{}

this points to that object:

```javascript id="step2"
this = {}




3. Assign values:



```javascript id="step3"
this.value = 5
this.next = null

Return object:

```javascript id="step4"
{
value: 5,
next: null
}




👉 So finally:



```javascript id="final-object"
node1 = {
  value: 5,
  next: null
}

🔁 8. Creating Multiple Nodes (Key Idea)

👉 You don’t create objects manually again and again

Instead:

let node1 = new Node(5);
let node2 = new Node(10);
let node3 = new Node(20);

👉 Every time you call:

new Node(value)

➡️ A new object is created automatically

🔗 9. Connecting Nodes

node1.next = node2;
node2.next = node3;

🖼️ 10. Visualization

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

🧠 11. What is `this`?

👉 this = current object being created

It allows us to:

Put data inside object
Build structure dynamically

🚀 12. Why `new` Keyword is MUST

👉 new does everything automatically:

Creates object
Links this
Executes function
Returns object

❌ Without `new`

let node1 = Node(5);

👉 Wrong because:

No object creation ❌
this breaks ❌

🧠 13. Memory Concept (Interview Level)

👉 next does NOT store full node
👉 It stores reference (address)

Example:

node1 → { value: 5, next: address of node2 }
node2 → { value: 10, next: null }

⚠️ 14. Common Mistake

this.value = val;
this.value = null; // ❌ wrong

👉 Always:

this.next = null;

🧪 15. Class Version (Modern JavaScript)

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

👉 Same working, cleaner syntax ✅

🔹 Easy Way to Understand

Think of a treasure hunt game:

Each clue contains:
- 🏆 Reward (data)
- 📍 Next location (pointer)

You keep moving from one clue to the next.

👉 This is exactly how nodes work.

🔹 Why Linked List is Important?

A linked list is important because it provides a dynamic and flexible way of storing data.

It is used when:

Size of data is unknown in advance
Frequent insertion and deletion is required
Memory should be used efficiently at runtime

🔹 Advantages of Linked List

📌 Dynamic size (can grow and shrink at runtime)
📌 No need for continuous (contiguous) memory
📌 Easy insertion and deletion (no shifting required)
📌 Memory is allocated only when needed
📌 Useful for implementing Stack, Queue, Graph, and Hash collision handling

🔥 Linked List vs Array (Very Important for Exams & Interviews)

🔹 1. Basic Structure Difference

Array

Stores elements in continuous (contiguous) memory
Uses index-based access

Index:  0   1   2   3
Array:  3   4   5   1

Linked List

Stores elements in non-contiguous memory
Uses nodes (Data + Pointer)

3 → 4 → 5 → 1 → NULL

🔹 2. Node Structure (Core Concept)

A node contains:

[ Data | Pointer ]

Data → actual value
Pointer → address of next node

👉 In doubly linked list:

[ Prev | Data | Next ]

🔹 3. Memory Difference

Array (Contiguous Memory)

| 3 | 4 | 5 | 1 |

Memory is continuous
No extra pointer memory

Linked List (Non-Contiguous Memory)


[3 | • ] → [4 | • ] → [5 | • ] → [1 | NULL]

Nodes are stored randomly in memory
Extra memory used for pointers
Doubly linked list uses more memory than singly linked list

🔹 4. Example (3, 4, 5, 1)

Array

Index:  0   1   2   3
Value:  3   4   5   1

Linked List

3 → 4 → 5 → 1 → NULL

🔹 5. Accessing Elements

Array → Fast Access

arr[2] = 5 → O(1)

✔ Direct index access
✔ Very fast

Linked List → Slow Access

To access an element:

3 → 4 → 5 → 1

To reach "5":

Start from head
Traverse node by node

❌ No direct access
✔ Time Complexity: O(n)

🔹 6. Insertion & Deletion

Linked List → Easy

No shifting required
Only pointer changes

Example:

3 → 4 → 5 → 1
Insert 10 between 4 and 5

✔ Efficient (O(1) if position known)

Array → Difficult

Requires shifting elements

3 4 5 1
Insert 10 at index 1 → shift elements

❌ Time Complexity: O(n)

🔹 7. Memory Usage

Structure	Memory
Array	Efficient (no pointers)
Singly Linked List	Extra memory (1 pointer/node)
Doubly Linked List	More memory (2 pointers/node)

🔹 8. Time Complexity Comparison

Operation	Array	Linked List
Access	O(1)	O(n)
Search	O(n)	O(n)
Insert (beginning)	O(n)	O(1)
Insert (middle)	O(n)	O(1)*
Delete	O(n)	O(1)*

if node reference is known

🔹 9. Key Differences (Quick Revision)

Array:

Fast access
Fixed size (or costly resizing)
Contiguous memory
Poor insertion/deletion

Linked List:

Slow access
Dynamic size
Non-contiguous memory
Easy insertion/deletion

🔹 10. Real-Life Use Cases

Array:

Image processing
Index-based systems
Static data storage

Linked List:

Music playlist
Browser history
Undo/Redo system
Memory management
Graph adjacency list

🟡 HOW LINKED LIST STORES DATA IN MEMORY

🔹 Basic Idea

Nodes are stored in random (non-contiguous) memory locations
Each node contains:
- Data
- Pointer (address) to the next node
Connection is logical (via pointers), not physical

📌 Structure of a Node

[ Data | Next Address ]

📌 Memory Representation

Memory Addresses:   100    500    200    800

Nodes:
[10 | 500] → [20 | 200] → [30 | 800] → [40 | NULL]

100 stores data 10 and points to 500
500 stores data 20 and points to 200
200 stores data 30 and points to 800
800 stores data 40 and points to NULL (end of list)

🔹 Important Points

The first node is accessed using a pointer called head
The last node points to NULL
Nodes are not stored sequentially in memory
Order is maintained using addresses (links)

🔹 Advantages

Dynamic size (can grow/shrink easily)
Efficient insertion/deletion (no shifting required)
Memory is used as needed

🔹 Disadvantages

Extra memory needed for pointers
No direct access (must traverse from head)
Slower access compared to arrays

⚡ Key Comparison with Array

Feature	Array	Linked List
Memory	Contiguous	Non-contiguous
Size	Fixed	Dynamic
Access	Direct (fast)	Sequential (slow)
Insertion	Costly (shift)	Easy (pointer change)

🟡 TYPES OF LINKED LIST (DETAILED)

Linked List is a linear data structure where elements (nodes) are connected using pointers.

🔹 1. SINGLY LINKED LIST (SLL)

📌 Definition

Each node contains:
- Data
- One pointer (Next)
Points only to the next node

📌 Structure


[Data | Next] → [Data | Next] → [Data | NULL]

📌 Key Points

Traversal is only forward
Last node points to NULL
Simplest type of linked list

✅ Advantages

Less memory (only one pointer)
Easy to implement

❌ Disadvantages

Cannot move backward
Traversal is slow (O(n))

💡 Use Cases

Stacks
Basic dynamic memory structures

🔹 2. DOUBLY LINKED LIST (DLL)

📌 Definition

Each node contains:
- Previous pointer
- Data
- Next pointer

📌 Structure


NULL ← [Prev | Data | Next] ⇄ [Prev | Data | Next] → NULL

📌 Key Points

Traversal in both directions
Extra memory needed for prev

✅ Advantages

Easy backward traversal
Easier deletion (no need to track previous node)

❌ Disadvantages

More memory usage
More complex

💡 Use Cases

Navigation systems (back/forward)
Undo/Redo operations

🔹 3. CIRCULAR LINKED LIST (CLL)

📌 Definition

Last node connects back to first node
No node points to NULL

📌 Structure


[Data | Next] → [Data | Next] → [Data | Next]
↑__________________________________↓

📌 Key Points

Forms a loop
Can start traversal from any node

✅ Advantages

No NULL pointer issues
Efficient for cyclic processes

❌ Disadvantages

Infinite loop risk
Harder to debug

💡 Use Cases

Round-robin scheduling
Multiplayer games (turn rotation)

🔹 4. CIRCULAR DOUBLY LINKED LIST (CDLL)

📌 Definition

Combination of DLL + Circular
Each node has:
- Prev pointer
- Next pointer
First and last nodes are connected

📌 Structure


↔ [Prev | Data | Next] ⇄ [Prev | Data | Next] ↔
↑____________________________________________↓

📌 Key Points

Traversal in both directions
No NULL pointer

✅ Advantages

Full flexibility (forward + backward)
Efficient for continuous navigation

❌ Disadvantages

Most complex
Highest memory usage

💡 Use Cases

Advanced navigation systems
Music/playlist looping

🧠 IMPORTANT INTERVIEW POINTS

🔸 Difference Between Types

Feature	Singly LL	Doubly LL	Circular LL	Circular Doubly LL
Pointers	1	2	1	2
Direction	One-way	Two-way	One-way	Two-way
NULL Present	Yes	Yes	No	No
Memory Usage	Low	Medium	Low	High
Complexity	Easy	Medium	Medium	Hard

🔸 Time Complexity (Common)

Operation	SLL	DLL	CLL	CDLL
Traversal	O(n)	O(n)	O(n)	O(n)
Insertion (head)	O(1)	O(1)	O(1)	O(1)
Deletion	O(n)	O(1)*	O(n)	O(1)*

*O(1) deletion in DLL/CDLL if node is known

🔸 When to Use Which?

Use Singly LL → when memory is limited
Use Doubly LL → when backward traversal needed
Use Circular LL → when process is cyclic
Use Circular Doubly LL → when full flexibility needed

🟣 7. LINKED LIST VS ARRAY (DEEP)

Feature	Array	Linked List
Memory	Contiguous	Non-contiguous
Size	Fixed / Resizable	Fully dynamic
Access	O(1)	O(n)
Insert/Delete	O(n)	O(1) (if pointer known)
Cache Friendly	Yes	No
Memory Overhead	Low	High (pointers)

🟣 8. TIME COMPLEXITY CHEAT SHEET

Operation	Time
Access	O(n)
Search	O(n)
Insert at head	O(1)
Insert at tail	O(1)*
Delete	O(1)*

if pointer available

🟠 9. CORE OPERATIONS (MUST MASTER)

📌 Traversal

Visit each node one by one

📌 Insertion

At beginning
At end
At position
After node
Before node

📌 Deletion

From beginning
From end
By value
By position

📌 Update

Change node value

📌 Search

Linear search

🟠 10. EDGE CASES (VERY IMPORTANT)

Empty list
Single node list
Two nodes
Deleting head
Deleting tail
Loop present
Duplicate values
Large inputs

⚡ When to Use Array

✅ Use Array When:

Fast Access is Required (O(1))
- You need to directly jump to any element
- Example: arr[4] instantly gives value

🏢 Analogy:

You know the exact flat number → go directly there

Data Size is Fixed or Known
- Size doesn’t change frequently

Example:

Marks of 100 students
Days in a week

Frequent Read Operations
- More reading, less inserting/deleting

Better Cache Performance
- Stored in continuous memory → faster in real systems

❌ Avoid Array When:

Frequent insertions/deletions in middle
Size changes dynamically

🔗 When to Use Linked List

✅ Use Linked List When:

Frequent Insertions/Deletions
- No shifting needed
- Just update pointers

🏠 Analogy:

Insert a new house → just change address slips

Dynamic Size
- Can grow/shrink anytime

Memory is Fragmented
- Doesn’t require continuous space

Implementing Advanced Structures
- Stacks
- Queues
- Graphs

❌ Avoid Linked List When:

You need fast random access
Extra memory (pointer storage) is a concern

//// sdfsegfs

🔴 11. IMPORTANT PATTERNS

🧠 1. Two Pointer Technique

Slow & Fast pointer

Used in:

Cycle detection
Middle node

🧠 2. Reversal Pattern

Iterative
Recursive

🧠 3. Dummy Node Technique

Simplifies insertion/deletion

🧠 4. Sliding Pointer

Used in partition problems

🔴 12. MUST-DO PROBLEMS (INTERVIEW CORE)

Easy

Reverse Linked List
Find middle
Remove duplicates

Medium

Detect cycle (Floyd)
Merge two sorted lists
Remove nth from end
Intersection of two lists

Hard

LRU Cache 🔥
Clone list with random pointer
Reverse in k-groups
Flatten linked list

🔥 13. ADVANCED CONCEPTS

📌 Floyd Cycle Detection

Fast moves 2 steps
Slow moves 1 step

📌 Random Pointer Linked List

Each node points randomly

📌 Skip List

Multi-level linked list

📌 XOR Linked List (Rare)

Memory optimized

🔥 14. DOUBLY LINKED LIST (DETAIL)

Node:

[Prev | Data | Next]

Pros:

Backward traversal

Cons:

Extra memory

🔥 15. CIRCULAR LINKED LIST (DETAIL)

No NULL
Last connects to first

Used in:

Round-robin scheduling

🧠 16. MEMORY UNDERSTANDING

Each node allocated dynamically
Uses heap memory
Pointer stores address

🧠 17. COMMON MISTAKES

❌ Forgetting NULL check
❌ Losing head pointer
❌ Infinite loop in circular list
❌ Wrong pointer update order

⚔️ 18. INTERVIEW STRATEGY

Draw diagram first ✍️
Handle edge cases
Use dummy node
Dry run example

🚀 19. REAL WORLD USE CASES

Music playlist
Browser history
Undo/Redo
Navigation systems

💰 ₹5 CRORE ANALOGY (Linked List Explained)

🏠 Concept Mapping

House = Node
Money (₹) = Data
Address Slip = Pointer (next)

🔗 Structure


House1 → House2 → House3 → House4 → House5 → NULL

🧱 Inside Each House (Node)

Each house contains:

💰 Money (Data)
📄 Address slip pointing to the next house (Pointer)

🏠 House Breakdown

House1
- Money: ₹1 crore
- Next: House2
House2
- Money: ₹1 crore
- Next: House3
House3
- Money: ₹1 crore
- Next: House4
House4
- Money: ₹1 crore
- Next: House5
House5
- Money: ₹1 crore
- Next: NULL (end of list)

🧠 Key Idea: Sequential Access

You cannot jump directly to a house.

To reach House5:


House1 → House2 → House3 → House4 → House5

➡️ You must follow the chain step-by-step.

🧾 Programming Mapping

Real World	Programming
House	Node
Money	Data
Address Slip	Pointer (`next`)
First House	Head
Last House	Tail (`next = NULL`)

💡 Advantages

1. Dynamic Size

You can easily add more houses:


House5 → House6 → NULL

2. Easy Insertion

Insert a new house between House2 and House3:


House2 → NewHouse → House3

➡️ Only pointers change, no shifting needed.

⚠️ Limitation

Slow access
To reach House5, you must pass through all previous houses

🎯 Final Intuition

Think of it as a treasure trail:

Each house gives you money 💰
And tells you where to go next 📍
If you lose the address slip, the chain breaks ❌

🟢 1. WHAT IS A LINKED LIST?

🔹 Basic Concept (Easy Words)

🔹 Important Terms

🔸 HEAD

🔸 NODE

🔸 POINTER / REFERENCE

🔸 NULL

🔸 TRAVERSAL

🔸 LENGTH

🔸 NEXT

🔸 DYNAMIC MEMORY

🔸 NON-CONTIGUOUS MEMORY

📌 What is a Node?

🔹 Simple Real-Life Meaning

🔹 What Does a Node Contain?

1. 📦 Data (Value)

2. 🔗 Link (Pointer)

🔹 Structure of a Node

🔹 Example of Linked Nodes

Explanation:

🎯 3. Core Idea (Very Important)

❌ 4. Problem with Manual Creation

✅ 5. Solution → Use Function / Class

🏗️ 6. Final Code (Constructor Function)

🧠 7. What is Happening Internally?

🔥 Step-by-step (Dry Run)

🔁 8. Creating Multiple Nodes (Key Idea)

🔗 9. Connecting Nodes

🖼️ 10. Visualization

🧠 11. What is this?

🚀 12. Why new Keyword is MUST

❌ Without new

🧠 13. Memory Concept (Interview Level)

⚠️ 14. Common Mistake

🧪 15. Class Version (Modern JavaScript)

🔹 Easy Way to Understand

🔹 Why Linked List is Important?

🔹 Advantages of Linked List

🔥 Linked List vs Array (Very Important for Exams & Interviews)

🔹 1. Basic Structure Difference

Array

Linked List

🔹 2. Node Structure (Core Concept)

🔹 3. Memory Difference

Array (Contiguous Memory)

Linked List (Non-Contiguous Memory)

🔹 4. Example (3, 4, 5, 1)

Array

Linked List

🔹 5. Accessing Elements

Array → Fast Access

Linked List → Slow Access

🔹 6. Insertion & Deletion

Linked List → Easy

Array → Difficult

🔹 7. Memory Usage

🔹 8. Time Complexity Comparison

🔹 9. Key Differences (Quick Revision)

Array:

Linked List:

🔹 10. Real-Life Use Cases

Array:

Linked List:

🟡 HOW LINKED LIST STORES DATA IN MEMORY

🔹 Basic Idea

📌 Structure of a Node

📌 Memory Representation

🔹 Important Points

🔹 Advantages

🔹 Disadvantages

⚡ Key Comparison with Array

🟡 TYPES OF LINKED LIST (DETAILED)

🔹 1. SINGLY LINKED LIST (SLL)

📌 Definition

📌 Structure

📌 Key Points

✅ Advantages

❌ Disadvantages

💡 Use Cases

🔹 2. DOUBLY LINKED LIST (DLL)

🧠 11. What is `this`?

🚀 12. Why `new` Keyword is MUST

❌ Without `new`