Linked List is one of the most important linear data structures used in computer science. It is a dynamic data structure that stores a collection of elements called nodes. Unlike arrays, linked lists do not store data in continuous memory locations. Instead, each element contains data and a reference (address) to the next element.
Linked lists are widely used when the size of data changes frequently because they allow insertion and deletion of elements without shifting other elements. They provide flexibility in memory management and are an important concept for understanding advanced data structures like stacks, queues, graphs, and trees.
In programming interviews and competitive programming, linked lists are frequently asked because they test a student's understanding of pointers, memory allocation, and logical problem-solving.
A Linked List is a linear collection of data elements where each element is stored inside a node. Every node contains two parts:
The first node of a linked list is called the Head Node. The head stores the address of the first node, which allows accessing the complete linked list.
The last node contains a special value called NULL, which indicates the end of the linked list.
HEAD
|
↓
+------+------+
| Data | Next |
+------+------+
|
↓
+------+------+
| Data | Next |
+------+------+
|
↓
NULL
Each node connects with another node using pointers. This connection creates a chain-like structure.
Arrays are simple and efficient for storing data, but they have some limitations. The size of an array is fixed, and inserting or deleting elements requires shifting other elements.
Linked lists overcome these limitations by providing dynamic memory allocation.
In programming, a linked list node is created using a structure or class. The node contains data and a pointer that stores the address of the next node.
struct Node
{
int data;
struct Node *next;
};
Here:
Node 1: Data = 10 Next = Address of Node 2 Node 2: Data = 20 Next = Address of Node 3 Node 3: Data = 30 Next = NULL
The linked list can be represented as:
10 → 20 → 30 → NULL
| Characteristic | Description |
|---|---|
| Dynamic Size | Size can increase or decrease during program execution. |
| Non-Contiguous Memory | Nodes can be stored anywhere in memory. |
| Pointer Based | Nodes are connected using memory addresses. |
| Efficient Insertion | Insertion can be performed without shifting elements. |
| Flexible Memory Usage | Memory is allocated only when required. |
Linked lists are mainly classified into different types depending on how nodes are connected.
A Singly Linked List is the simplest type of linked list. Each node contains data and a pointer to the next node.
A node can only move in one direction, from the first node towards the last node.
HEAD | ↓ [10|Next] → [20|Next] → [30|NULL]
Insertion means adding a new node into an existing linked list. A new node can be inserted at different positions.
A new node is added before the first existing node.
Before: 10 → 20 → 30 Insert 5: After: 5 → 10 → 20 → 30
Time Complexity:
O(1)
A new node is added after the last node of the linked list.
Before: 10 → 20 → 30 Insert 40: After: 10 → 20 → 30 → 40
Time Complexity:
O(n)
A new node can be inserted at any required position by changing the links of previous and next nodes.
Before: 10 → 20 → 40 Insert 30: After: 10 → 20 → 30 → 40
The previous node pointer is modified to connect with the new node.
Traversal means visiting each node of the linked list one by one to access or display data.
Example: 10 → 20 → 30 → NULL Output: 10 20 30
Time Complexity:
O(n)
| Array | Linked List |
|---|---|
| Fixed size | Dynamic size |
| Continuous memory allocation | Non-contiguous memory allocation |
| Fast random access | No direct access |
| Insertion is costly | Insertion is easier |
| No extra pointer memory | Requires pointer memory |
A Doubly Linked List is an advanced form of a linked list in which each node contains two pointers. One pointer stores the address of the next node, while the second pointer stores the address of the previous node.
This structure allows traversal in both forward and backward directions, making it more flexible than a singly linked list.
NULL ← [Prev|10|Next] ⇄ [Prev|20|Next] ⇄ [Prev|30|Next] → NULL
In this structure, every node maintains information about both neighboring nodes.
A Circular Linked List is a linked list in which the last node points back to the first node instead of storing NULL.
This creates a circular chain of nodes that can be traversed continuously.
┌──────────────┐
↓ │
10 → 20 → 30 → 40
↑ ↓
└────────────────┘
The last node contains the address of the first node, creating a loop.
A Circular Doubly Linked List combines the features of both doubly linked lists and circular linked lists.
Each node contains two pointers, and the last node connects back to the first node while the first node also points to the last node.
⇄ 10 ⇄ 20 ⇄ 30 ⇄
↑ ↓
└───────────────┘
This structure allows bidirectional circular traversal.
Deletion is the process of removing a node from a linked list.
Proper pointer adjustment is necessary to maintain the structure of the list.
The first node is removed and the head pointer is updated to the next node.
Before: 10 → 20 → 30 → NULL Delete 10 After: 20 → 30 → NULL
Time Complexity:
O(1)
The last node is removed from the linked list.
Before: 10 → 20 → 30 → NULL Delete 30 After: 10 → 20 → NULL
Time Complexity:
O(n)
A node can also be removed from a particular location by adjusting neighboring links.
Before: 10 → 20 → 30 → 40 Delete 30 After: 10 → 20 → 40
Searching means finding whether a particular element exists in the linked list.
Since linked lists do not support direct indexing, searching is performed sequentially.
10 → 20 → 30 → 40 Search 30 Result: Element Found
Time Complexity:
O(n)
Updating means modifying the value stored inside an existing node.
Before: 10 → 20 → 30 Update 20 to 25 After: 10 → 25 → 30
The node is first searched and then its data field is modified.
Unlike arrays, linked list nodes are not stored in continuous memory locations.
Each node can be stored anywhere in memory and connected through pointers.
Address Data Next 1000 10 2500 2500 20 4000 4000 30 NULL
This flexibility allows efficient memory utilization.
| Operation | Time Complexity |
|---|---|
| Traversal | O(n) |
| Searching | O(n) |
| Insertion at Beginning | O(1) |
| Insertion at End | O(n) |
| Deletion at Beginning | O(1) |
| Deletion at End | O(n) |
| Access by Position | O(n) |
Linked lists are used in many software systems because of their flexibility and dynamic nature.
Stacks can be efficiently implemented using linked lists without fixed size limitations.
Queues use linked lists for dynamic insertion and deletion operations.
Adjacency lists used in graph structures are implemented using linked lists.
Operating systems use linked lists to manage free memory blocks.
Forward and backward navigation uses doubly linked lists.
Media applications use linked lists to move between songs or videos.
Text editors often implement undo and redo functionality using linked data structures.
Each coach is connected to the next coach similar to linked list nodes.
Employee records can be linked using references to create organizational structures.
Posts can be connected dynamically as users create new content.
Routes and connected locations may use linked structures internally.
A linked list is a dynamic linear data structure consisting of nodes connected through pointers.
Because memory is allocated during runtime and the size can grow or shrink as required.
Singly Linked List, Doubly Linked List, Circular Linked List, and Circular Doubly Linked List.
A node is the basic unit of a linked list that contains data and one or more pointers.
The head node is the first node of a linked list and provides access to all other nodes.
Because elements do not need to be shifted like arrays.
Direct random access is not possible.
Doubly Linked List.
O(n).
O(1).
Circular Linked List.
A special value indicating that no node exists after the current node.
They provide flexible memory management and serve as the foundation for many advanced data structures.
Linked List is one of the most important concepts in Data Structures. It provides dynamic memory allocation, efficient insertion and deletion operations, and forms the basis of many advanced structures such as stacks, queues, trees, and graphs.
Understanding singly linked lists, doubly linked lists, circular linked lists, and their operations helps students build strong programming and problem-solving skills. Linked lists are frequently asked in university examinations, coding interviews, and technical recruitment processes.
Mastering linked lists is a major step toward becoming proficient in Data Structures and Algorithms.