Linked List in Data Structure: Types, Operations and Examples
Arrays are simple and fast when the amount of data is known in advance, but real programs do not always work with a fixed number of elements. Sometimes new data has to be inserted, old data has to be removed, and the structure needs to grow or shrink while the program is running.
A Linked List handles this situation differently from an array. Instead of keeping all elements together in one continuous block, it stores data inside separate nodes and connects those nodes using links.
What is a Linked List in Data Structure?
A Linked List is a collection of connected nodes.
Every node contains some useful data and a link that tells the program where the next node is located.
In this example, the list contains three nodes with values 10, 20 and 30.
The first node points to the second node, the second points to the third, and the final node points to NULL, which means that the list ends there.
Why Do We Need Linked Lists?
To understand why Linked Lists are useful, first compare them with arrays.
An array normally stores elements in consecutive memory locations. This is why array indexing and memory-address calculations can be performed efficiently. If you want to understand that memory layout in detail, read the earlier chapter on Array Address Calculation in Data Structure.
Linked Lists follow a different approach. Nodes can exist at different memory locations, and links connect them logically.
Array
Elements are usually stored in contiguous memory locations.
Linked List
Nodes may exist at different locations but remain connected through pointers.
Structure of a Linked List Node
In a Singly Linked List, every node usually has two parts:
1. Data Field
The data field stores the actual value that we want to keep in the list.
For example:
2. Link / Pointer Field
The link field stores information that connects the current node with another node.
In a Singly Linked List, this normally points to the next node.
What is the Head Pointer?
A Linked List needs a way to know where it begins.
The reference to the first node is usually called HEAD.
If HEAD contains NULL, the Linked List is empty.
Important Features of Linked List
Dynamic Size
Nodes can be created when required, so the list can grow or shrink during program execution.
Non-Contiguous Storage
Nodes do not need to occupy adjacent memory locations.
Link-Based Access
The next element is reached by following a link instead of calculating an array index.
Types of Linked List
The major Linked List types are:
1. Singly Linked List
Each node points only to the next node.
2. Doubly Linked List
Each node keeps links to both the previous and next nodes.
3. Circular Linked List
The final node connects back to the first node instead of pointing to NULL.
1. Singly Linked List
A Singly Linked List is the simplest Linked List type.
Each node contains:
- data, and
- a link to the next node.
Movement normally happens in one direction:
We cannot directly move from C back to B unless we start again from the beginning or store additional information.
2. Doubly Linked List
A Doubly Linked List stores an extra link in every node.
Each node usually contains:
A Doubly Linked List allows traversal in both directions.
3. Circular Linked List
A Circular Linked List does not end with a NULL link.
Instead, the last node connects back to the first node.
Conceptually:
This structure is useful when processing needs to continue repeatedly in a cycle.
Circular Doubly Linked List
A Circular Doubly Linked List combines both ideas:
- every node has previous and next links, and
- the first and last nodes are connected.
This makes forward and backward circular traversal possible.
Linked List vs Array
| Basis | Array | Linked List |
|---|---|---|
| Memory | Usually contiguous | Nodes may be non-contiguous |
| Size | Often fixed or resized as a whole | Can grow and shrink node by node |
| Random Access | Fast through index | Sequential traversal required |
| Insertion / Deletion | May require shifting elements | Can be efficient when position/node is known |
| Extra Memory | No link field per element | Pointers require extra memory |
| Cache Locality | Usually better | Often weaker because nodes may be scattered |
Arrays also use concepts such as Row Major and Column Major storage when working with multidimensional data. That topic is explained separately in Row Major vs Column Major Order in Data Structure.
Basic Operations on Linked List
The most important Linked List operations are:
Traversal
Visit nodes one by one.
Insertion
Add a new node.
Deletion
Remove an existing node.
Searching
Find whether a value exists.
Updating
Change data stored in a node.
Counting
Determine the total number of nodes.
Traversal in Linked List
Traversal means visiting every node one by one.
Unlike an array, we cannot normally jump directly to any node using an index.
Traversal Algorithm
Insertion in Linked List
Insertion means adding a new node to the list.
Common insertion positions are:
- at the beginning,
- at the end, and
- at a specific position or after a particular node.
Insertion at Beginning
Suppose the original list is:
We want to insert 5 at the beginning.
Pseudocode
Insertion at End
Suppose:
We want to add 40.
If the list also maintains a TAIL pointer, insertion at the end can be much faster because traversal to the last node may not be required.
Insertion at a Specific Position
Suppose:
We want to insert 30 between 20 and 40.
The important part is changing links in the correct order so that the rest of the list is not lost.
Deletion in Linked List
Deletion means removing a node while keeping the remaining nodes correctly connected.
Common cases are:
- delete the first node,
- delete the last node, and
- delete a node from a particular position.
Deletion from Beginning
Suppose:
After deleting 10:
The HEAD is updated to point to the second node.
Pseudocode
Deletion from End
For:
we must reach the node before 30 and change its next field to NULL.
In a Singly Linked List, finding the previous node usually requires traversal from HEAD unless extra information is maintained.
Deletion of a Specific Node
Suppose the list is:
To delete 30, change the next link of 20 so that it points directly to 40.
Searching in Linked List
Searching normally starts from HEAD.
Each node is checked until:
- the required value is found, or
- the list ends.
Searching Algorithm
Updating a Linked List Node
Updating means finding a required node and changing its stored data.
Example:
Time Complexity of Linked List Operations
| Operation | Typical Singly Linked List Complexity | Reason |
|---|---|---|
| Access by Position | O(n) | Nodes must usually be followed sequentially |
| Search | O(n) | May need to inspect every node |
| Insert at Beginning | O(1) | Only HEAD and one link are changed |
| Delete from Beginning | O(1) | HEAD can move directly to the next node |
| Insert at End | O(n) without tail | Last node must be found |
| Insert at End | O(1) with tail | TAIL directly identifies the last node |
| Delete Known Node / After Known Predecessor | Can be O(1) | Only local links need modification |
Singly vs Doubly vs Circular Linked List
| Feature | Singly Linked List | Doubly Linked List | Circular Linked List |
|---|---|---|---|
| Links per Node | Usually one | Usually two | Depends on singly or doubly circular form |
| Forward Traversal | Yes | Yes | Yes |
| Backward Traversal | No | Yes | Only in doubly circular form |
| Last Node | Points to NULL | Next points to NULL | Connects back to first node |
| Extra Memory | Lower | Higher | Depends on implementation |
| Best For | Simple sequential structures | Two-way navigation | Repeated cyclic processing |
Advantages of Linked List
Dynamic Growth
The list can grow as new nodes are created instead of requiring one fixed continuous block.
Flexible Insertion
Once the correct node is known, insertion may require only a small number of link changes.
Flexible Deletion
Removing a node usually does not require shifting all later elements like an array may require.
Useful Building Block
Linked Lists are used to implement stacks, queues, graph structures and other dynamic data structures.
Disadvantages of Linked List
No direct random access: To reach the fifth node, we usually need to follow previous nodes first.
Extra memory: Every node needs at least one pointer in addition to its data.
Pointer handling: Incorrect link updates can break the list or lose access to nodes.
Weak cache locality: Nodes can be located at different places in memory.
More complex implementation: Insertion and deletion require careful pointer changes.
Applications of Linked List
Stacks
A stack can be implemented using dynamically linked nodes.
Queues
Front and rear nodes can be connected efficiently.
Graph Representation
Adjacency lists commonly use list-like structures to represent neighbours.
Browser Navigation
Two-way navigation concepts can be modelled with doubly linked structures.
Music Playlists
Circular or doubly linked structures can represent previous/next playback.
Memory Management
Free blocks and dynamically allocated objects may be organised using linked structures.
Linked List and Sparse Data Structures
Linked structures are also useful when only a small amount of data exists among many possible positions.
For example, the earlier chapter on Sparse Matrix in Data Structure explained that non-zero matrix elements can be stored using special compact representations. A linked representation is one possible way to connect only the useful non-zero elements instead of storing the complete matrix.
This shows an important Data Structure principle:
Example: Building a Linked List Step by Step
Suppose we want:
Step 1: Create First Node
Step 2: Add Second Node
Step 3: Add Third Node
The important point is that the logical order is created by links. The physical memory locations do not need to appear in the same order.
Simple C Structure for a Singly Linked List Node
Here:
- data stores the value, and
- next stores the address of another Node.
How Memory Works in a Linked List
Suppose three nodes are stored at different memory locations:
| Node | Memory Address | Data | Next Address |
|---|---|---|---|
| Node 1 | 1000 | 10 | 4500 |
| Node 2 | 4500 | 20 | 2800 |
| Node 3 | 2800 | 30 | NULL |
Even though the addresses are:
the logical order is still:
Array says: “Find me by position.”
Linked List says: “Follow my link.”
This one difference explains most of the behaviour of both structures.
Linked List vs Sparse Matrix vs Array Storage
| Structure | Main Storage Idea | Useful When |
|---|---|---|
| Array | Elements stored in indexed sequence | Fast indexed access is important |
| Linked List | Nodes connected using links | Dynamic insertion/deletion is important |
| Sparse Matrix | Store mainly useful non-zero data | Most matrix positions are zero |
Common Mistakes Students Make
1. Saying Linked List uses contiguous memory
A Linked List does not require nodes to be stored next to each other.
2. Forgetting HEAD
HEAD identifies the beginning of the list. Losing HEAD may make the list unreachable.
3. Changing pointers in the wrong order
During insertion or deletion, wrong pointer updates can disconnect the remaining list.
4. Assuming direct index access
A normal Linked List does not support array-style O(1) random access.
5. Forgetting the NULL condition
Traversal of a normal Singly Linked List stops when the pointer becomes NULL.
6. Using NULL as the last link in a Circular Linked List
The last node of a circular list points back to the beginning.
Best Memory Trick for Linked List
NODE = Data + Direction
Think of every node as a small box that contains:
For types:
Singly → One direction
Doubly → Two directions
Circular → Comes back again
Quick Comparison for Exams
Exam Questions with Answers
Q1. What is a Linked List?
A Linked List is a linear Data Structure made up of nodes. Each node stores data and one or more links that connect it with other nodes.
Q2. What is a node?
A node is an individual unit of a Linked List. In a Singly Linked List, it normally contains a data field and a next pointer.
Q3. What is HEAD?
HEAD is the pointer or reference that identifies the first node of a Linked List.
Q4. Name the major types of Linked List.
The major types are Singly Linked List, Doubly Linked List and Circular Linked List.
Q5. Why is Linked List called a dynamic Data Structure?
Because nodes can be created and removed during program execution, allowing the structure to grow or shrink according to requirement.
Q6. What is the difference between Singly and Doubly Linked List?
A Singly Linked List normally contains one next link, while a Doubly Linked List contains both previous and next links and therefore supports traversal in both directions.
5-Mark Exam Answer: Linked List
A Linked List is a linear Data Structure in which elements are stored inside nodes. The nodes do not need to occupy consecutive memory locations. Instead, they are logically connected using pointers or links.
A basic Singly Linked List node contains:
The first node is identified using HEAD, while the next field of the last node contains NULL.
The major types of Linked List are:
- Singly Linked List
- Doubly Linked List
- Circular Linked List
Important operations include traversal, insertion, deletion, searching and updating.
Linked Lists are useful because they can grow dynamically and allow flexible insertion and deletion. However, they require additional pointer memory and do not provide direct array-like random access.
10-Mark Exam Answer: Linked List, Types and Operations
A Linked List is a dynamic linear Data Structure formed using a collection of nodes. Each node contains data and one or more pointers that connect it with other nodes. Unlike an array, Linked List nodes do not need to be stored in contiguous memory locations.
In a Singly Linked List, every node contains a data field and a next pointer:
The main types of Linked List are:
1. Singly Linked List: Every node points to the next node and traversal occurs mainly in one direction.
2. Doubly Linked List: Every node contains previous and next pointers, allowing movement in both directions.
3. Circular Linked List: The final node points back to the first node instead of NULL.
The important Linked List operations are traversal, insertion, deletion, searching and updating.
Insertion can occur at the beginning, end or a specific position. Deletion can also be performed from different positions by updating the required links.
A Linked List is useful when the size of data changes frequently and insertion or deletion is important. Its disadvantages include extra pointer memory, sequential access and more complex pointer handling.
Linked Lists are commonly used for stacks, queues, graph adjacency lists, playlists and other dynamic structures.
Frequently Asked Questions
Is Linked List a linear Data Structure?
Yes. A Linked List is considered a linear Data Structure because its nodes are logically arranged in a sequence, even though they may not be physically adjacent in memory.
Why does a Linked List not require contiguous memory?
Each node stores a link to another node. Therefore, the program can follow these links even when the nodes are stored at different memory locations.
What is the difference between an array and a Linked List?
An array provides index-based access and normally stores its elements in contiguous memory, while a Linked List connects separately allocated nodes using pointers.
Which Linked List supports backward traversal?
A Doubly Linked List supports backward traversal because each node contains a pointer to its previous node as well as its next node.
Why is Circular Linked List called circular?
Because the last node connects back to the first node, creating a cycle instead of ending with NULL.
Is insertion always O(1) in a Linked List?
No. The actual link update may take constant time, but finding the required insertion position can require O(n) traversal.
Can Linked List be used to implement Stack and Queue?
Yes. Linked Lists are commonly used to create dynamic implementations of stacks and queues.
What is the biggest advantage of Linked List?
Its main advantage is flexibility. Nodes can be added or removed dynamically without requiring all later elements to be shifted as in many array operations.
