Linked List
A Linked List is a linear data structure where elements are stored in separate objects called nodes, and each node contains data plus a link to another node.
The biggest difference from an array is:
Array → elements are stored next to each other in memory.
Linked List → nodes can be anywhere in memory, and pointers connect them.
1. Why Do We Need Linked Lists?
Consider an array:
[10] [20] [30] [40] [50]
Arrays are excellent for accessing elements:
arr[3]
because we can directly calculate where the element is.
But arrays have a problem: inserting or deleting elements in the middle can require shifting many elements.
For example, inserting 25:
Before: 10 20 30 40 50
We need:
10 20 25 30 40 50
Several elements may need to move.
A linked list handles this differently.
10 → 20 → 30 → 40 → 50
If we want to insert 25:
10 → 20 → 25 → 30 → 40 → 50
We can change links instead of shifting every element.
2. What Is a Node?
A linked list consists of nodes.
A basic node contains two things:
┌──────────────┬──────────────┐ │ Data │ Next │ └──────────────┴──────────────┘
For example:
┌──────┬──────┐ │ 10 │ ────────→ └──────┴──────┘
The two parts are:
Data
Stores the actual value.
10
Next
Stores a pointer/reference to the next node.
3. Basic Linked List Structure
Suppose we have:
10 → 20 → 30 → 40 → NULL
It actually looks conceptually like:
┌────┬──────┐ ┌────┬──────┐ ┌────┬──────┐ │ 10 │ ───────→ │ 20 │ ───────→ │ 30 │ ───────→ NULL └────┴──────┘ └────┴──────┘ └────┴──────┘
The last node points to:
NULL
which means:
There is no next node.
4. Head
The linked list needs a starting point.
This is called the head.
head ↓ 10 → 20 → 30 → 40 → NULL
head stores the address/reference of the first node.
If:
head = NULL
then the linked list is empty.
5. Why Is It Called a Linked List?
Because nodes are linked together.
Node 1 ↓ Node 2 ↓ Node 3 ↓ Node 4
The connection is created using pointers.
So:
Data + Link
creates a chain:
10 → 20 → 30 → 40
6. Creating a Node in C++
A simple node can be defined using a struct:
struct Node { int data; Node* next; };
Here:
data
stores the value.
And:
next
is a pointer to another Node.
7. Creating a Single Node
Example:
Node* node1 = new Node(); node1->data = 10; node1->next = nullptr;
Conceptually:
node1 ↓ ┌────┬────────┐ │ 10 │ nullptr│ └────┴────────┘
There is currently only one node.
8. Creating Multiple Nodes
We can create:
Node* first = new Node(); Node* second = new Node(); Node* third = new Node();
Then:
first->data = 10; second->data = 20; third->data = 30;
Connect them:
first->next = second; second->next = third; third->next = nullptr;
Now:
first ↓ 10 → 20 → 30 → NULL
9. Understanding ->
When working with a pointer to a structure/class, we use:
->
For example:
first->data
means:
Access the
datamember of the node pointed to byfirst.
Similarly:
first->next
means:
Access the
nextpointer of that node.
10. Creating a Linked List More Cleanly
A common approach:
struct Node { int data; Node* next; Node(int value) { data = value; next = nullptr; } };
Now:
Node* first = new Node(10); Node* second = new Node(20); Node* third = new Node(30); first->next = second; second->next = third;
The result:
10 → 20 → 30 → NULL
11. Traversing a Linked List
Unlike an array, we cannot directly do:
list[3]
Instead, we start at head and follow the links.
Example:
Node* current = head; while(current != nullptr) { cout << current->data << " "; current = current->next; }
Suppose:
head ↓ 10 → 20 → 30 → NULL
Traversal:
current → 10 ↓ current → 20 ↓ current → 30 ↓ current → NULL
Output:
10 20 30
Complexity:
Time = O(n)
because we may visit every node.
12. Inserting at the Beginning
Suppose:
10 → 20 → 30 → NULL
We want to insert:
5
Create a new node:
5
Then:
newNode->next = head;
Now:
5 → 10 → 20 → 30 → NULL
Finally:
head = newNode;
Code:
Node* newNode = new Node(5); newNode->next = head; head = newNode;
Complexity
O(1)
This is one of the biggest advantages of a linked list.
13. Inserting at the End
Suppose:
10 → 20 → 30 → NULL
We want:
10 → 20 → 30 → 40 → NULL
Create:
40
Then find the last node:
10 → 20 → 30 → NULL ↑ last
Set:
last->next = newNode;
Result:
10 → 20 → 30 → 40 → NULL
If we only have a head pointer, finding the last node requires traversal.
Therefore:
O(n)
However, if we maintain a tail pointer, insertion at the end can be made O(1).
14. Tail
The tail is the last node.
Example:
head tail ↓ ↓ 10 → 20 → 30 → 40 → NULL
If we maintain both:
head tail
then we can quickly access both ends.
15. Inserting in the Middle
Suppose:
10 → 20 → 40 → 50
We want to insert 30 after 20.
Create:
30
We need to change the links:
Before:
20 → 40
After:
20 → 30 → 40
Conceptually:
newNode->next = current->next; current->next = newNode;
Result:
10 → 20 → 30 → 40 → 50 → NULL
The actual pointer changes are simple.
But finding the correct position may require traversal.
So the overall complexity is often:
O(n)
if we start only from head.
16. Deleting the First Node
Suppose:
head ↓ 10 → 20 → 30 → NULL
We want to delete 10.
Simply move head:
head = head->next;
Now:
head ↓ 20 → 30 → NULL
The old first node can then be released appropriately in manual-memory C++ code.
Complexity:
O(1)
17. Deleting the Last Node
Suppose:
10 → 20 → 30 → NULL
We want:
10 → 20 → NULL
We need to find the node before 30.
10 → 20 → 30 ↑ previous
Then:
20 → NULL
With a singly linked list and only a head pointer, finding the previous node requires traversal.
Complexity:
O(n)
18. Deleting a Specific Node
Suppose:
10 → 20 → 30 → 40
We want to remove:
30
We need to connect:
20 → 40
Before:
20 → 30 → 40
After:
20 → 40
The node 30 is removed from the chain.
Again, finding it may require traversal.
19. Searching a Linked List
Suppose:
10 → 20 → 30 → 40 → NULL
We want to find 30.
Start at head:
10 → 20 → 30 ↑ ↑ ↑ 1st 2nd Found
Code:
Node* current = head; while(current != nullptr) { if(current->data == 30) { cout << "Found"; break; } current = current->next; }
Worst-case complexity:
O(n)
Unlike an array, we cannot directly jump to the 30th node.
20. Why Can't We Do Random Access?
With an array:
arr[4]
can directly locate the fifth element.
With a linked list:
10 → 20 → 30 → 40 → 50
to reach 50, we generally need:
head ↓ 10 ↓ 20 ↓ 30 ↓ 40 ↓ 50
Therefore accessing the nth node is generally:
O(n)
This is a major difference between arrays and linked lists.
21. Array vs Linked List
| Feature | Array | Linked List |
|---|---|---|
| Memory layout | Contiguous | Nodes can be scattered |
| Random access | O(1) | O(n) |
| Search | O(n) | O(n) |
| Insert at beginning | Usually O(n) | O(1) |
| Delete at beginning | Usually O(n) | O(1) |
| Insert at known node | Shifting may be needed | O(1) link changes |
| Extra pointer memory | No | Yes |
| Fixed-size array | Fixed | Dynamic |
| Cache locality | Usually good | Generally less predictable |
The important lesson:
Arrays are good for fast access. Linked lists are good when frequent insertions/deletions and flexible size are important.
22. Types of Linked Lists
There are several important types.
1. Singly Linked List
Each node points only to the next node.
10 → 20 → 30 → NULL
2. Doubly Linked List
Each node has:
previous data next
Example:
NULL ← 10 ⇄ 20 ⇄ 30 → NULL
3. Circular Linked List
The last node points back to the first node.
10 → 20 → 30 ↑ ↓ └──────────┘
These are important topics within linked lists.
23. Singly Linked List
The structure is:
struct Node { int data; Node* next; };
Each node has:
data ↓ next ↓ next node
Example:
head ↓ ┌────┬─────┐ ┌────┬─────┐ ┌────┬──────┐ │ 10 │ ─────→ │ 20 │ ─────→ │ 30 │ NULL │ └────┴─────┘ └────┴─────┘ └────┴──────┘
24. Doubly Linked List
A doubly linked list contains two links.
┌─────────┬──────┬─────────┐ │ prev │ data │ next │ └─────────┴──────┴─────────┘
Example:
NULL ← 10 ⇄ 20 ⇄ 30 → NULL
This allows movement in both directions:
Forward: 10 → 20 → 30 Backward: 30 → 20 → 10
The tradeoff is that every node requires an additional pointer.
25. Circular Linked List
In a normal singly linked list:
10 → 20 → 30 → NULL
In a circular linked list:
10 → 20 → 30 ↑ ↓ └──────────┘
The last node points back to the first node.
So there is no NULL at the end.
Circular lists can be useful for things like:
- Round-robin scheduling
- Repeated cyclic processing
- Circular buffers in certain designs
26. Reversing a Linked List
This is one of the most important linked-list problems.
Suppose:
10 → 20 → 30 → NULL
We want:
30 → 20 → 10 → NULL
We can use three pointers:
previous current next
Initially:
previous = NULL current = head
Then repeatedly reverse the link.
Core idea:
next = current->next; current->next = previous; previous = current; current = next;
At the end:
head = previous;
Result:
30 → 20 → 10 → NULL
Complexity:
Time = O(n) Space = O(1)
This is a very important DSA pattern.
27. Finding the Middle Node
Suppose:
10 → 20 → 30 → 40 → 50
Middle:
30
A very common technique is slow and fast pointers.
slow → moves 1 step fast → moves 2 steps
Example:
slow: 10 → 20 → 30 fast: 10 → 30 → 50
When fast reaches the end, slow is around the middle.
This technique is called the:
Fast and Slow Pointer technique
It is extremely important for linked-list problems.
28. Detecting a Cycle
Consider:
10 → 20 → 30 → 40 ↑ ↓ └─────────┘
The list contains a cycle.
A common solution is Floyd's Cycle Detection Algorithm, also called the Tortoise and Hare algorithm.
Use:
slow → 1 step fast → 2 steps
If there is a cycle, eventually:
slow == fast
This can detect a cycle in:
Time = O(n) Space = O(1)
29. Why Linked Lists Are Dynamic
An array often has a predetermined capacity:
int arr[100];
A linked list can create nodes as needed:
Create node ↓ Connect node ↓ Create another ↓ Connect again
So the list can grow:
10 ↓ 10 → 20 ↓ 10 → 20 → 30 ↓ 10 → 20 → 30 → 40
There is no requirement that all nodes be placed next to each other in memory.
30. Memory of a Linked List
Suppose we have:
10 → 20 → 30
Each node needs:
Data + Pointer
So compared with an array, a linked list has additional memory overhead for pointers.
For example, conceptually:
Array: [10][20][30] Linked List: [10 | next] → [20 | next] → [30 | NULL]
This is one reason linked lists aren't automatically "better" than arrays.
31. Advantages of Linked Lists
1. Dynamic size
Nodes can be added and removed as needed.
2. Easy insertion/deletion
Once the relevant node/position is known, changing links can be very efficient.
3. No need for contiguous memory
Nodes can exist at different memory locations.
4. Useful foundation
Linked lists help you understand:
- Pointers
- Dynamic memory
- References
- Node-based structures
- Trees
- Graphs
32. Disadvantages of Linked Lists
1. No direct/random access
You cannot efficiently do:
list[500]
like an array.
2. Extra memory
Each node needs pointer information.
3. More complicated
Pointers make linked lists harder to understand than arrays initially.
4. Poorer cache locality
Nodes may be scattered around memory, so traversing them can be less cache-friendly than traversing a contiguous array.
5. Searching is still O(n)
A linked list does not automatically make searching faster.
33. Important Complexity Table
For a singly linked list, a typical complexity table is:
| Operation | Complexity |
|---|---|
| Access first node | O(1) |
| Access nth node | O(n) |
| Search | O(n) |
| Insert at beginning | O(1) |
| Delete first node | O(1) |
| Insert after a known node | O(1) |
| Delete after a known previous node | O(1) |
| Insert at end with only head | O(n) |
| Insert at end with tail pointer | O(1) |
| Reverse | O(n) |
| Find middle | O(n) |
| Detect cycle | O(n) |
The exact complexity of insertion/deletion depends heavily on whether you already have a pointer to the relevant node.
34. Complete Basic Singly Linked List Example
Here is a simple implementation:
#include <iostream> using namespace std; struct Node { int data; Node* next; Node(int value) { data = value; next = nullptr; } }; int main() { Node* head = new Node(10); head->next = new Node(20); head->next->next = new Node(30); Node* current = head; while(current != nullptr) { cout << current->data << " "; current = current->next; } return 0; }
Output:
10 20 30
The structure is:
head ↓ 10 → 20 → 30 → NULL
35. The Most Important Mental Model
Don't think of a linked list as:
[10][20][30][40]
Think of it as:
next next 10 ─────────→ 20 ─────────→ 30 ─────────→ NULL
Each node says:
"Here is my data, and here is where the next node is."
That is the fundamental idea behind a linked list.
36. Array vs Linked List — The Core Difference
Remember this:
ARRAY [10][20][30][40][50] ↑ Direct access arr[3] → 40 O(1)
versus:
LINKED LIST 10 → 20 → 30 → 40 → 50 ↑ Start here and follow links To reach 40: 10 → 20 → 30 → 40 O(n)
So:
Array → fast access
Linked List → flexible node insertion/deletion
Neither is universally better. The right choice depends on the problem.
Final Summary
A linked list consists of:
Node │ ├── Data │ └── Next pointer
Multiple nodes create:
head ↓ 10 → 20 → 30 → 40 → NULL
The most important concepts you should understand before moving forward are:
- Node
- Head
- Next pointer
- NULL
- Traversal
- Insertion
- Deletion
- Searching
- Singly linked list
- Doubly linked list
- Circular linked list
- Reverse linked list
- Slow/fast pointers
- Cycle detection
- Linked-list complexity