Linked List In Data Structures | Types, Operations & More (+Code)

15 mins read

In data structures, a linked list is a dynamic linear data structure where elements, called nodes, are connected using pointers. Unlike arrays, linked lists do not require contiguous memory allocation, making them efficient for insertions and deletions. Each node typically consists of data and a pointer to the next node, forming a chain-like structure.

In this article, we will explore the types of linked lists, their implementation, advantages, and real-world applications to understand why they are a fundamental concept in data structures.

What Is Linked List In Data Structures?

A Linked List is a data structure used to store a collection of elements, where each element (called a node) contains two parts:

1. Data – The actual value stored in the node.
2. Pointer – A reference (or link) to the next node in the sequence.

Unlike arrays, linked lists do not store elements in a continuous memory location. Instead, each node is connected to the next through pointers, making insertion and deletion operations more efficient compared to arrays.

Real-Life Analogy: A Train

Think of a linked list as a train where:

• Each coach represents a node (it has data: passengers, and a link to the next coach).
• The engine (head of the linked list) points to the first coach.
• If we want to add or remove a coach, we don’t need to shift all other coaches (unlike an array where shifting might be required).
• The last coach (node) has no further link, just like the tail of a linked list points to NULL.

Types Of Linked Lists In Data Structures

A linked list is a dynamic data structure consisting of nodes connected through pointers. Depending on how nodes are linked, linked lists can be classified into different types.

1. Singly Linked List

A singly linked list consists of nodes where each node contains:

• Data (the value stored in the node).
• A pointer to the next node in the sequence.

This type of linked list allows only forward traversal from the head (first node) to the tail (last node),which points to NULL.

Structure:

[10 | * ] → [20 | * ] → [30 | * ] → [NULL]

Real-Life Analogy:

A one-way street where vehicles move in a single direction without the ability to turn back.

Advantages:

• Uses less memory as each node stores only one pointer.
• Insertion and deletion at the beginning are efficient.

Disadvantages:

• Cannot traverse backward due to the absence of a previous pointer.
• Searching requires a full scan from the head node.

2. Doubly Linked List

A doubly linked list is an extension of a singly linked list where each node contains:

• Data
• A pointer to the next node
• A pointer to the previous node

This structure allows both forward and backward traversal.

Structure:

NULL ← [10 | * | * ] ↔ [20 | * | * ] ↔ [30 | * | * ] → NULL

Real-Life Analogy:

A metro train where passengers can move forward or backward between compartments.

Advantages:

• Bidirectional traversal allows movement in both directions.
• Easier deletion of a node without requiring a full traversal.

Disadvantages:

• Requires more memory due to two pointers per node.
• Slightly slower operations due to additional pointer management.

3. Circular Linked List

A circular linked list is a variation where the last node points back to the first node, forming a continuous loop. It can be either singly circular or doubly circular.

Structure (Singly Circular):

[10 | * ] → [20 | * ] → [30 | * ] → (points back to 10)

Structure (Doubly Circular):

[10 | * | * ] ↔ [20 | * | * ] ↔ [30 | * | * ] ↺ (points back to 10)

Real-Life Analogy:

A circular race track where cars keep moving in a loop without a definite end.

Advantages:

• No NULL values, enabling continuous traversal.
• Useful in applications like round-robin scheduling and buffered tasks.

Disadvantages:

• Can lead to infinite loops if not properly handled.
• More complex implementation compared to singly and doubly linked lists.

Choosing The Right Linked List

• Singly Linked List is suitable when memory optimization is a priority and one-way traversal is sufficient.
• Doubly Linked List is useful when frequent insertions and deletions are required, and backward traversal is needed.
• Circular Linked List is ideal when a continuous looping structure is required, such as in operating systems and scheduling algorithms.

Linked List Operations In Data Structures

A linked list is a dynamic data structure that allows insertion and deletion of elements efficiently. The fundamental operations on a linked list include:

1. Insertion

Adding a new node at different positions in the linked list.

Types of Insertion:

• At the Beginning: The new node becomes the head, and its pointer is set to the previous head.
• At a Specific Position: The new node is inserted between two existing nodes, adjusting their pointers.
• At the End: The new node is added at the tail, and the last node’s pointer is updated.

Real-Life Analogy:

Adding a new coach to a train at the front, middle, or end of a railway track.

Complexity:

• Best Case: O(1) (insertion at the beginning)
• Worst Case: O(n) (insertion at the end or middle)

Code Example:

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    
    Node(int value) {
        data = value;
        next = NULL;
    }
};

// Function to insert at the beginning
void insertAtBeginning(Node*& head, int value) {
    Node* newNode = new Node(value);
    newNode->next = head;
    head = newNode;
}

// Function to insert at the end
void insertAtEnd(Node*& head, int value) {
    Node* newNode = new Node(value);
    if (head == NULL) {
        head = newNode;
        return;
    }
    Node* temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

// Function to insert at a specific position
void insertAtPosition(Node*& head, int value, int position) {
    if (position == 0) {
        insertAtBeginning(head, value);
        return;
    }
    
    Node* newNode = new Node(value);
    Node* temp = head;
    for (int i = 0; temp != NULL && i < position - 1; i++) {
        temp = temp->next;
    }
    
    if (temp == NULL) {
        cout << "Position out of bounds!" << endl;
        return;
    }
    
    newNode->next = temp->next;
    temp->next = newNode;
}

// Function to print the list
void printList(Node* head) {
    while (head != NULL) {
        cout << head->data << " -> ";
        head = head->next;
    }
    cout << "NULL" << endl;
}

int main() {
    Node* head = NULL;
    
    insertAtBeginning(head, 10);
    insertAtEnd(head, 30);
    insertAtPosition(head, 20, 1);
    
    printList(head); // Output: 10 -> 20 -> 30 -> NULL
    
    return 0;
}

Output:

10 -> 20 -> 30 -> NULL

Explanation:

In the above code example-

1. Node Class:
• We define a Node class with data (to store values) and next (to point to the next node).
• The constructor initializes the data and sets next to NULL.
2. Insert at Beginning:
• We create a new node and point its next to the current head.
• The head is updated to the new node.
3. Insert at End:
• If the list is empty, the new node becomes the head.
• Otherwise, we traverse to the last node and update its next to the new node.
4. Insert at Position:
• If inserting at position 0, we call insertAtBeginning().
• Otherwise, we traverse to the given position and adjust pointers.
• If the position is out of bounds, we display an error message.
5. Print Function:
• We traverse the list and print each node’s value.
6. Main Function:
• We start with an empty list.
• Insert 10 at the beginning, 30 at the end, and 20 at position 1.
• Finally, we print the list: 10 -> 20 -> 30 -> NULL

2. Deletion

Removing a node from the linked list and updating pointers accordingly.

Types of Deletion:

• From the Beginning: The head node is removed, and the next node becomes the new head.
• From a Specific Position: The node is removed, and the previous node’s pointer is updated to skip it.
• From the End: The last node is removed, and the second-last node’s pointer is set to NULL.

Real-Life Analogy:

Removing a specific coach from a train without affecting the remaining coaches.

Complexity:

• Best Case: O(1) (deleting the first node)
• Worst Case: O(n) (deleting the last node)

Code Example:

void deleteNode(Node*& head, int position) {
    if (head == NULL) {
        cout << "List is empty!" << endl;
        return;
    }

    Node* temp = head;
    
    // Deleting the first node
    if (position == 0) {
        head = head->next;
        delete temp;
        return;
    }

    // Find the previous node
    for (int i = 0; temp != NULL && i < position - 1; i++) {
        temp = temp->next;
    }

    if (temp == NULL || temp->next == NULL) {
        cout << "Position out of bounds!" << endl;
        return;
    }

    Node* nodeToDelete = temp->next;
    temp->next = nodeToDelete->next;
    delete nodeToDelete;
}

int main() {
    Node* head = NULL;

    insertAtEnd(head, 10);
    insertAtEnd(head, 20);
    insertAtEnd(head, 30);
    
    cout << "Before deletion: ";
    printList(head);
    
    deleteNode(head, 1);
    
    cout << "After deletion: ";
    printList(head);
    
    return 0;
}

Output:

Before deletion: 10 -> 20 -> 30 -> NULL
After deletion: 10 -> 30 -> NULL

Explanation:

In the above code example-

1. Delete Node Function:
   • If the list is empty, we print "List is empty!" and return.
   • If deleting the first node, we update head to the next node and free the memory.
   • Otherwise, we traverse to the node before the target position.
   • If the position is out of bounds, we print an error message.
   • Otherwise, we adjust pointers and delete the node.
2. Main Function:
   • We start with an empty list.
   • Insert 10, 20, and 30 at the end.
   • Print the list before deletion.
   • Delete the node at position 1 (removing 20).
   • Print the list after deletion.

3. Traversal

Visiting each node in the linked list to access data.

Approach:

• Start from the head node.
• Move to the next node using the pointer until reaching NULL.

Real-Life Analogy:

Walking from the first to the last coach of a train, checking each passenger.

Complexity:

• Time Complexity: O(n) (as every node needs to be visited)

Code Example:

void traverseList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}

int main() {
    Node* head = NULL;

    insertAtEnd(head, 10);
    insertAtEnd(head, 20);
    insertAtEnd(head, 30);
    
    cout << "Linked List: ";
    traverseList(head);
    
    return 0;
}

Output:

Linked List: 10 20 30

Explanation:

In the above code example-

1. Traverse List Function:
• We start from head and iterate through the list.
• For each node, we print its data.
• The loop stops when temp becomes NULL.
2. Main Function:
• We initialize an empty list.
• Insert 10, 20, and 30 at the end.
• Print the list using traverseList().

4. Searching

Finding a specific node based on its value.

Approach:

• Start from the head.
• Compare each node’s value with the target value.
• Continue until the value is found or the end is reached.

Real-Life Analogy:

Searching for a specific seat number inside a train by checking each seat.

Complexity:

• Worst Case: O(n) (linear search)

Code Example:

bool search(Node* head, int key) {
    Node* temp = head;
    while (temp != NULL) {
        if (temp->data == key)
            return true;
        temp = temp->next;
    }
    return false;
}

int main() {
    Node* head = NULL;

    insertAtEnd(head, 10);
    insertAtEnd(head, 20);
    insertAtEnd(head, 30);
    
    int key = 20;
    if (search(head, key))
        cout << key << " found in the list!" << endl;
    else
        cout << key << " not found in the list!" << endl;
    
    return 0;
}

Output:

20 found in the list!

Explanation:

In the above code example-

1. Search Function:
   • We start from head and iterate through the list.
   • If a node’s data matches the key, we return true.
   • If we reach the end without finding the key, we return false.
2. Main Function:
   • We initialize an empty list.
   • Insert 10, 20, and 30 at the end.
   • Search for 20 in the list.
   • Print whether the key is found or not.

5. Updating

Changing the data of an existing node.

Approach:

• Traverse to the required node.
• Modify its value without changing the structure.

Real-Life Analogy:

Updating a passenger's ticket information while they remain in the same seat.

Complexity:

• Worst Case: O(n) (if the last node needs to be updated)

Code Example:

void updateNode(Node* head, int oldValue, int newValue) {
    Node* temp = head;
    while (temp != NULL) {
        if (temp->data == oldValue) {
            temp->data = newValue;
            return;
        }
        temp = temp->next;
    }
    cout << "Value not found!" << endl;
}

int main() {
    Node* head = NULL;

    insertAtEnd(head, 10);
    insertAtEnd(head, 20);
    insertAtEnd(head, 30);
    
    cout << "Before update: ";
    printList(head);
    
    updateNode(head, 20, 25);
    
    cout << "After update: ";
    printList(head);
    
    return 0;
}

Output:

Before update: 10 -> 20 -> 30 -> NULL
After update: 10 -> 25 -> 30 -> NULL

Explanation:

In the above code example-

1. Update Node Function:
   • We start from head and iterate through the list.
   • If a node’s data matches oldValue, we update it to newValue and return.
   • If the value is not found, we print "Value not found!".
2. Main Function:
   • We initialize an empty list.
   • Insert 10, 20, and 30 at the end.
   • Print the list before the update.
   • Update 20 to 25.
   • Print the list after the update.

Choosing The Right Operation Based On Need

• Use insertion when adding new elements dynamically.
• Use deletion to remove unnecessary elements.
• Use traversal to access and process all elements.
• Use searching to locate a specific node.
• Use updating when modifying values without altering structure.

Summary Of Operations & Their Complexities

Advantages And Disadvantages Of Linked Lists In Data Structures

Linked lists provide dynamic memory allocation and efficient insertions/deletions but come with increased memory overhead. Let's explore the key advantages and disadvantages:

Advantages Of Linked Lists

1. Dynamic Memory Allocation

• Unlike arrays, linked lists do not require a fixed size during declaration.
• Memory is allocated as needed, avoiding wastage.

2. Efficient Insertions and Deletions

• Inserting or deleting elements in a linked list is efficient (O(1) for beginning and O(n) for middle or end).
• No need for shifting elements as in arrays.

3. No Wastage of Memory Due to Fixed Size

• Since linked lists grow dynamically, there is no need to reserve extra memory in advance, reducing wastage.

4. Implementation of Advanced Data Structures

• Linked lists serve as the foundation for stacks, queues, graphs, and hash tables.
• They are essential for creating circular and doubly linked lists.

5. Can Handle Different Data Sizes

• Unlike arrays, where elements must be of the same size, linked lists can have elements of varying sizes.

Disadvantages Of Linked Lists

1. Extra Memory Overhead

• Each node requires additional memory for storing a pointer to the next node.
• This increases the overall memory consumption compared to arrays.

2. Slower Access Time

• Unlike arrays, where elements can be accessed using an index, linked lists require sequential traversal (O(n)) to access a node.
• Random access is not possible.

3. Increased Complexity in Implementation

• Operations like searching and updating take longer compared to arrays.
• Requires careful pointer management to avoid issues like memory leaks and dangling pointers.

4. Cache Unfriendliness

• Unlike arrays, which store elements in contiguous memory locations, linked lists use scattered memory.
• This results in poor cache locality and slower performance due to frequent memory access.

Comparison Of Linked Lists And Arrays

In data structures, both linked lists and arrays are used to store collections of data, but they differ in memory management, access speed, and efficiency. Arrays offer fast random access due to their contiguous memory allocation, whereas linked lists allow efficient insertions and deletions because they use dynamic memory allocation. 

The table below provides a detailed comparison between Linked Lists and Arrays, highlighting their key differences in terms of memory, performance, and operations.

When To Use A Linked List?

• When insertion and deletion operations are more frequent than access operations.
• When dynamic memory allocation is required without wasting space.
• When implementing stack, queue, graph structures, and hash tables.

When To Use An Array?

• When fast and direct access is needed using indexing.
• When memory efficiency is important (no extra storage required for pointers).
• When the size of the dataset is known and does not change frequently.

Applications Of Linked Lists 

Linked lists are widely used in computer science and software development due to their dynamic nature and efficient insertions and deletions. Below are some key applications of linked lists:

1. Dynamic Memory Allocation

• Used in operating systems to manage memory allocation (e.g., heap memory allocation).
• Enables programs to use memory efficiently without knowing the exact size in advance.

2. Implementation of Stacks and Queues

• Stacks (Last In, First Out – LIFO) can be implemented using a singly linked list.
• Queues (First In, First Out – FIFO) can be implemented using a singly or doubly linked list.

3. Managing Graph Data Structures

• Adjacency lists in graphs use linked lists to store neighbors of a node efficiently.
• Used in social networks, navigation systems, and recommendation algorithms.

4. Undo/Redo Functionality in Software

• Applications like text editors, graphic software, and web browsers use doubly linked lists to track changes.
• Users can navigate back and forth using the previous and next pointers.

5. Hash Tables (Collision Handling with Chaining)

• In hash tables, linked lists handle collisions using separate chaining.
• If multiple elements map to the same hash index, a linked list is used to store them.

6. Polynomial Arithmetic and Large Number Calculations

• Polynomial operations (addition, multiplication) use linked lists to store terms dynamically.
• Large numbers (beyond built-in data types) are represented as linked lists to handle operations efficiently.

7. Browser Navigation (Forward and Backward)

• Doubly linked lists are used to store browsing history in web browsers.
• Users can navigate forward and backward easily.

8. Music and Video Playlists

• Circular linked lists are used in media players where the last song connects back to the first song.
• Enables seamless looping of playlists.

9. OS Process Management (Job Scheduling)

• Operating systems use linked lists to manage processes and tasks in schedulers.
• Circular linked lists help in round-robin scheduling.

10. Implementation of LRU (Least Recently Used) Cache

• Used in memory management and database caching.
• Doubly linked lists with hash maps store recently used data for faster access.

Conclusion

Linked lists are a fundamental data structure that offers dynamic memory allocation, efficient insertions, and deletions, making them an essential choice in many real-world applications. Unlike arrays, they do not require predefined memory allocation, allowing flexibility in handling growing and shrinking data structures. However, they come with trade-offs, such as sequential access and extra memory for pointers.

From implementing stacks and queues to managing browser history, process scheduling, and graph representations, linked lists play a crucial role in computer science. Understanding their types, operations, advantages, and applications helps in choosing the right data structure for different scenarios.

While linked lists shine in situations requiring frequent modifications, arrays remain the preferred choice when fast random access and cache efficiency are critical. Thus, the selection between linked lists and arrays depends on the specific problem and performance requirements.

Frequently Asked Questions

Q. When should I use a linked list instead of an array?

Use a linked list when you need frequent insertions and deletions, as it avoids the costly shifting operations required in arrays. If you require fast random access, an array is a better choice.

Q. What is the difference between singly and doubly linked lists?

A singly linked list has nodes with a single pointer pointing to the next node, while a doubly linked list has two pointers (one pointing to the next node and another pointing to the previous node), allowing traversal in both directions.

Q. Why is searching slower in a linked list compared to an array?

In a linked list, elements are stored in non-contiguous memory locations, requiring sequential traversal (O(n)) to find an element. In contrast, arrays allow direct indexing (O(1)) for fast access.

Q. What are the disadvantages of linked lists?

Some disadvantages of linked lists include higher memory usage due to pointers, sequential access (no direct indexing), and increased complexity in implementation compared to arrays.

Q. How does a circular linked list differ from a normal linked list?

In a circular linked list, the last node’s pointer connects back to the first node, forming a loop. This enables continuous traversal and is often used in applications like job scheduling and playlist looping.

Suggested Reads:

1. Difference Between Hashing And Encryption Decoded
2. 53 Frequently Asked Linked List Interview Questions With Answers 2024
3. Data Structure Interview Questions For 2024 [With Detailed Answers]
4. Tree Topology | Advantages & Disadvantages In Computer Network
5. Decoding Data Redundancy In DBMS| Causes, Advantages, Solutions
6. Machine Learning Algorithms: Techniques, Applications, And Insights