What Is a Linked List?
A linked list is a linear data structure used to store a collection of elements. Unlike arrays, the elements in a linked list are not stored in contiguous memory locations. Instead, each element is stored in a separate memory location and connected through pointers.
Each element in a linked list is called a node. A node contains two main parts: the actual data and a reference (pointer) to the next node in the sequence. This connection between nodes forms a chain-like structure.
Imagine a treasure hunt game where each clue leads you to the next clue. Similarly, in a linked list, each node tells you where the next node is located. This means you cannot directly jump to any element like you can in arrays. Instead, you must start from the first node and move step by step until you reach the desired node.
This property makes linked lists particularly useful in situations where the size of data changes frequently. Unlike arrays, which require a fixed memory size, linked lists can grow or shrink dynamically during program execution.
Another key advantage of linked lists is their efficient insertion and deletion operations. Since nodes are connected using pointers, inserting or deleting an element simply requires adjusting these links rather than shifting elements like in arrays.
Structure of a Linked List Node
Every node in a linked list usually contains two fields:
Stores the actual information
Stores the address of the next node
A simple representation of a node:
For example, storing the numbers 10 → 20 → 30 → 40:
• Head points to the first node.
• Each node points to the next node.
• The last node points to NULL, indicating the end of the list.
Concept of Dynamic Memory Allocation
What Is Dynamic Memory Allocation?
Dynamic memory allocation refers to the process of allocating memory during the runtime of a program rather than at compile time. This means the program can request memory whenever it needs it and release it when it no longer needs it.
In many programming languages such as C or C++, functions used to manage dynamic memory include:
In traditional data structures like arrays, memory is allocated in a fixed block before execution. If you allocate space for 100 elements but only use 50, the remaining memory is wasted. Dynamic memory allocation solves this problem by allocating memory only when required.
Why It's Important in Linked Lists
Linked lists rely heavily on dynamic memory allocation because each node is created separately during runtime. Imagine a music streaming app where users keep adding songs to a playlist — with linked lists, each song can be added dynamically as a new node.
Core Concepts
Types of Linked Lists
Singly Linked List
A singly linked list is the simplest form of a linked list. In this structure, each node contains data and a pointer that points to the next node in the sequence. Traversal is unidirectional — you can only move forward.
Structure:
• Each node has only one pointer
• Traversal is possible only in one direction
• The last node points to NULL
• Simple and memory efficient compared to other types
C++ PROGRAM — Create and Display
using namespace std;
struct Node {
int data;
Node* next;
};
int main() {
Node* head = NULL;
Node* first = new Node();
Node* second = new Node();
Node* third = new Node();
first->data = 10; first->next = second;
second->data = 20; second->next = third;
third->data = 30; third->next = NULL;
head = first;
Node* temp = head;
while(temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
return 0;
}
Doubly Linked List
A doubly linked list is an advanced version of a singly linked list. Each node contains two pointers — one to the previous node and one to the next node.
Structure:
Each node has three components: Previous pointer · Data · Next pointer
✅ Advantages
Traversal in both directions, easier deletion, more flexibility
⚠️ Disadvantage
Requires extra memory because each node stores two pointers
C++ PROGRAM
using namespace std;
struct Node {
int data;
Node* prev;
Node* next;
};
int main() {
Node* first = new Node();
Node* second = new Node();
Node* third = new Node();
first->data = 10; first->prev = NULL; first->next = second;
second->data = 20; second->prev = first; second->next = third;
third->data = 30; third->prev = second; third->next = NULL;
Node* temp = first;
while(temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
return 0;
}
prev for previous node and next for next node. This allows moving forward and backward in the list.
Circular Linked List
In a circular linked list, the last node does not point to NULL. Instead, it points back to the first node, forming a circular structure.
Structure:
↑___________________________|
• No node points to NULL
• The last node connects back to the first node
• Traversal can start from any node
• Used in round-robin scheduling in operating systems
C++ PROGRAM
using namespace std;
struct Node {
int data;
Node* next;
};
int main() {
Node* first = new Node();
Node* second = new Node();
Node* third = new Node();
first->data = 10; first->next = second;
second->data = 20; second->next = third;
third->data = 30; third->next = first; // points back to first
Node* temp = first;
do {
cout << temp->data << " ";
temp = temp->next;
} while(temp != first);
return 0;
}
do-while loop is used to avoid infinite loops.
Manipulating Data
Linked List Operations
Traversal · Insertion · Deletion · Searching
Traversal Operation
Traversal means visiting every node in the linked list one by one. Time complexity: O(n)
Steps involved:
1. Start from the head node
2. Access the data in the current node
3. Move to the next node using the pointer
4. Repeat until the pointer becomes NULL
C++ PROGRAM
using namespace std;
struct Node { int data; Node* next; };
void display(Node* head) {
Node* temp = head;
while(temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
}
int main() {
Node* head = new Node(); Node* second = new Node(); Node* third = new Node();
head->data = 5; head->next = second;
second->data = 15; second->next = third;
third->data = 25; third->next = NULL;
display(head); return 0;
}
Insertion Operation
Insertion means adding a new node to the linked list. It can happen at the beginning, end, or middle.
Insert 15 between 10 and 20:
After: 10 → 15 → 20 → 30
Insertion at beginning: O(1) · Insertion at end or middle: O(n)
C++ PROGRAM — Insert at Beginning
using namespace std;
struct Node { int data; Node* next; };
void insertBeginning(Node*& head, int value) {
Node* newNode = new Node();
newNode->data = value;
newNode->next = head;
head = newNode;
}
void display(Node* head) {
while(head != NULL) { cout << head->data << " "; head = head->next; }
}
int main() {
Node* head = NULL;
insertBeginning(head, 30);
insertBeginning(head, 20);
insertBeginning(head, 10);
display(head); return 0;
}
Deletion Operation
Deletion removes a node from the linked list.
Delete 20:
After: 10 → 30 → 40
Steps involved:
1. Locate the node to be deleted
2. Update the previous node's pointer
3. Free the memory of the deleted node
Deletion at beginning: O(1) · Deletion at end: O(n)
C++ PROGRAM — Delete First Node
using namespace std;
struct Node { int data; Node* next; };
void deleteFirst(Node*& head) {
if(head == NULL) return;
Node* temp = head;
head = head->next;
delete temp;
}
int main() {
Node* head = new Node(); Node* second = new Node();
head->data = 10; head->next = second;
second->data = 20; second->next = NULL;
deleteFirst(head);
while(head != NULL) { cout << head->data << " "; head = head->next; }
return 0;
}
Searching Operation
Searching means finding a node with a specific value. Time complexity: O(n) — elements must be accessed sequentially.
1. Start from the head node
2. Compare each node's data with the target value
3. Continue until the value is found or the list ends
C++ PROGRAM
using namespace std;
struct Node { int data; Node* next; };
bool search(Node* head, int key) {
while(head != NULL) {
if(head->data == key) return true;
head = head->next;
}
return false;
}
int main() {
Node* head = new Node(); Node* second = new Node(); Node* third = new Node();
head->data = 10; head->next = second;
second->data = 20; second->next = third;
third->data = 30; third->next = NULL;
if(search(head, 20)) cout << "Element Found";
else cout << "Element Not Found";
return 0;
}
Time Complexity of Operations
| Operation | Time Complexity | Notes |
|---|---|---|
| Traversal | O(n) | Visit every node |
| Searching | O(n) | Sequential access only |
| Insertion (Beginning) | O(1) | Fastest insertion |
| Insertion (End) | O(n) | Requires traversal |
| Deletion (Beginning) | O(1) | Fastest deletion |
| Deletion (End) | O(n) | Requires traversal |
✅ Advantages
⚠️ Disadvantages
Applications of Linked Lists
Music players use circular linked lists to allow continuous playback of songs.
Text editors use linked lists to store and manage changes for undo/redo.
Operating systems use linked lists to efficiently manage free memory blocks.
Graphs are represented using adjacency lists implemented with linked lists.
Many languages implement stack and queue data structures using linked lists.
Summary
| Topic | Explanation |
|---|---|
| Dynamic Memory | Memory created during runtime |
| Singly Linked List | Node points to next node |
| Doubly Linked List | Node points to next and previous |
| Circular Linked List | Last node connects to first |
| Traversal | Visiting each node |
| Insertion | Adding new node |
| Deletion | Removing node |
| Searching | Finding a node |
Conclusion
Linked lists are one of the most important data structures in computer science. Unlike arrays, they store elements in separate memory locations and connect them using pointers. This structure allows linked lists to dynamically grow or shrink, making them ideal for programs where the size of data changes frequently.
We explored dynamic memory allocation, different types of linked lists (singly, doubly, and circular), and important operations such as traversal, insertion, deletion, and searching. We also looked at several real-world applications where linked lists are widely used.
Understanding linked lists is crucial for mastering data structures because they serve as the foundation for many advanced structures like stacks, queues, graphs, and trees.
Frequently Asked Questions
1. What is a linked list in simple words?
A linked list is a data structure where elements are stored in nodes, and each node points to the next node in the sequence.
2. What are the main types of linked lists?
The main types are singly linked list, doubly linked list, and circular linked list.
3. Why are linked lists better than arrays in some cases?
Linked lists allow efficient insertion and deletion without shifting elements, making them suitable for dynamic data.
4. What is the time complexity of searching in a linked list?
Searching in a linked list takes O(n) time because elements must be accessed sequentially.
5. Where are linked lists used in real life?
They are used in operating systems, music playlists, memory management, graph representation, and undo/redo features in applications.
0 Comments
If you have any doubts, Please let me know