Table of contents
1.
Introduction
2.
What is a Linked List?
3.
Uses of Linked List:
4.
Why use a linked list over an array?
5.
Representation of Linked Lists
5.1.
Syntax:
6.
Why do we need linked lists?
7.
Operations in the Linked Lists
7.1.
1. Traversal Operation
7.2.
Algorithm :
7.3.
2. Insertion Operation
7.4.
3. Deletion Operation 
7.5.
4. Updation Operation
7.6.
5. Sort Operation
8.
Types of Linked Lists
8.1.
Singly Linked Lists
8.2.
Doubly Linked Lists
8.3.
Circular Linked Lists
9.
Advantages of Linked List
10.
Disadvantages of Linked List
11.
Applications of Linked List
12.
Frequently Asked Questions
12.1.
What are the 4 types of linked list?
12.2.
Which of the following are linked list operations?
12.3.
What are the operations of queue?
12.4.
What are the various operations on stack using linked list?
13.
Conclusion
Last Updated: Oct 4, 2024
Easy

Linked List in Data Structure

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

A linked list is a type of linear data structure that uses nodes to store the data.

linked list operations

Each node in a linked list is a structure-defined data type that consists of data and a pointer referencing the address of the next node.

What is a Linked List?

A linked list is a linear data structure where elements, called nodes, are connected through pointers. Each node contains data and a reference to the next node, forming a sequence. Unlike arrays, linked lists do not require contiguous memory allocation, allowing dynamic memory management and efficient insertion and deletion operations.

Uses of Linked List:

Let's discuss the main uses of linked lists in detail:

1. Dynamic memory allocation: Linked lists are useful when you need to allocate memory dynamically. Unlike arrays, which have a fixed size, linked lists can grow or shrink during runtime. Each node in a linked list is allocated memory independently, allowing for efficient memory utilization. This makes linked lists suitable for scenarios where the size of the data is unknown or varies frequently.

2. Insertion and deletion operations: Linked lists provide efficient insertion and deletion operations, especially when dealing with elements in the middle of the list. Unlike arrays, where inserting or deleting elements in the middle requires shifting all subsequent elements, linked lists can perform these operations by simply adjusting the pointers of the nodes. This makes linked lists advantageous in scenarios where frequent insertions or deletions are required.

3. Implementing stacks and queues: Linked lists are commonly used to implement stacks and queues. In a stack, elements are inserted and removed from the same end (top), while in a queue, elements are inserted at one end (rear) and removed from the other end (front). Linked lists provide a natural way to implement these data structures efficiently, as they allow for constant time (O(1)) insertion and deletion operations at the ends of the list.

4. Representing graphs and trees: Linked lists can be used to represent graphs and trees. In a graph, each node can be represented as a linked list node, and the edges can be represented by pointers connecting the nodes. Similarly, in a tree, each node can be represented as a linked list node, and the child nodes can be connected using pointers. Linked lists provide a flexible way to build and traverse these data structures.

5. Memory management: Linked lists are used in memory management systems, such as the free list. When memory is dynamically allocated and deallocated, the free memory blocks can be organized as a linked list. This allows for efficient tracking and allocation of free memory blocks, as the memory manager can traverse the linked list to find a suitable block for allocation.

6. Undo/Redo functionality: Linked lists can be used to implement undo/redo functionality in applications. Each action or state can be stored as a node in a linked list. By maintaining pointers to the current state and the previous states, the application can easily navigate back and forth through the undo/redo history.

Why use a linked list over an array?

Linked lists and arrays are both data structures used to store collections of elements, but they have different characteristics and are suited for different scenarios. Let's see some of the reasons why you might choose to use a linked list over an array:

1. Dynamic size: Arrays have a fixed size that needs to be specified at the time of declaration and cannot be changed once created. In contrast, linked lists can grow or shrink dynamically during runtime without a fixed size. Nodes can be added or removed as needed. If the number of elements is unknown or can change frequently, a linked list is more suitable than an array.

2. Insertion and deletion efficiency: Inserting or deleting elements in the middle of an array is inefficient because it requires shifting all the subsequent elements to maintain the contiguous memory layout. In a linked list, insertion and deletion operations can be performed efficiently by adjusting the pointers of the nodes. If your application involves many insertion or deletion operations, especially in the middle of the collection, a linked list can provide better performance compared to an array.

3. Memory allocation: Arrays require a contiguous block of memory to store their elements. If the size of the array is large or if there is not enough contiguous memory available, it may be difficult to allocate memory for an array. Linked lists do not require contiguous memory, as each node is allocated memory independently and can be scattered throughout the memory. If memory is fragmented or if you need to allocate memory dynamically, linked lists can be more suitable than arrays.

4. Flexibility: Arrays have a fixed size and a specific index-based access mechanism, making them suitable for scenarios where random access to elements is frequent. Linked lists provide more flexibility in terms of structure and organization. They can be easily modified to support additional features like doubly linked lists or circular linked lists. If you need a more flexible data structure that can adapt to different requirements or if you don't rely heavily on random access, linked lists can be a better choice.

5. Random access: It's important to note that arrays have an advantage when it comes to random access. Arrays provide constant-time (O(1)) access to elements based on their index, which is not efficiently possible in linked lists. If your program heavily relies on random access to elements, arrays may be a better choice.

6. Cache locality: Arrays have better cache locality compared to linked lists. Since array elements are stored contiguously in memory, accessing them sequentially can be more efficient due to cache optimization. If your program performs many sequential accesses to elements, arrays can provide better performance in terms of cache utilization.

Representation of Linked Lists

Representation of Linked Lists

A linked list is a collection of “nodes” connected together via links. These nodes consist of the data to be stored and a pointer to the address of the next node within the linked list. In the case of arrays, the size is limited to the definition, but in linked lists, there is no defined size. Any amount of data can be stored in it and can be deleted from it.

The first node in a linked list is referred to as the head, while the last node frequently links to null to denote the end of the list. Each link contains a data field or fields as well as a link field named next. Every link is connected to the next link using the next link.

Syntax:

struct Node {
   int data;
   Node* next;
};

 

The syntax above represents a single node in a linked list. The next pointer connects the next node, forming a lengthy chain known as a linked list.

Why do we need linked lists?

It offers some amazing features and thus it is of great use, some of the advantages of it include:

  • Dynamic Size: It offers the flexibility to extend the size at runtime and thus we need to worry about the size of data elements beforehand.
  • Ease of Deletion/Insertion: It offers a good and economical way of insertion and deletion of data elements as this insertion and deletion can be costly with the use of arrays.

Operations in the Linked Lists

 There are several operations which were performed on the Linked Lists

  1. Traversal - To traverse throughout the linked list.
     
  2. Insertion - Insertion of a node at any position.
     
  3. Deletion - Deletion of a node from any position.
     
  4. Updation - Updation of data of a node.
     
  5. Sort - Sorting the node members
     

We will cover each one of these operations on linked lists in C/C++ one by one in detail. So, fasten your seat belts.

1. Traversal Operation

Traversal is one of the basic operations on linked lists in C/C++ in which we traverse throughout the linked list from beginning to the end or from head to tail.

Traversal can be used to print the nodes of the linked list, to reach out for a required node in a list.

Let us take the example of printing the nodes of the linked list through traversal operation.
 

Algorithm :

  • First, initialize a Node variable, say ‘temp’ pointing to the head of the linked list.
     
  • Iterate till the ‘temp’ will not become NULL.
     
  • Print the node’s data.
     
  • Increment ‘temp’ to temp’s next.
     
void traversal(Node* head) {
    Node* temp = head;
    while(temp != NULL)
    {
        cout<<(temp->data);
        temp = temp->next;
    }
}      

2. Insertion Operation

Of the operations on linked lists in C/C++, insertion is used to insert a node at a particular position. The positions can be:

  • At the beginning of the linked list.
     
  • At the end of the linked list.
     
  • After after a particular node.
     

Insertion at the Beginning - In this case we need not to traverse the linked list. We will check if the list is empty then we will make the new node as head. Otherwise, we have to connect the head of the list with the new node by making the next pointer of the node pointing to the head and then making the new node as head of the list.

Node* insertAtBegin(Node* head, int x)
{
    // creation of a new node of linked list.
    Node* newNode = new Node(x)
 
    // checking if the linked list is empty.
    if(head == NULL)         
    return newNode;
 
    // insertion of the node at the beginning.
    else     
    {
        newNode->next = head;
        return newNode;
    }
}

 

Insertion at the end - In this case we have to traverse throughout the linked list until we will find the last node and then we will insert the required node in the list.

For this, we have to consider some special cases. For eg. if the list is empty then we will just create the new node and make it as head. In this case the new node will be the first and the last node of the list.

Node* insertAtEnd(Node* head, int x)
{
 
    // If the list is empty.
    if( head == NULL )     
    {
        Node* newNode = new Node(x);
        head = newNode;
        return head;
    }
    Node* temp = head;

    // Traversing the list till the last node
    while(temp->next != NULL)
    {
        temp = temp->next;
    }
    Node* newNode = new Node(x);
    temp->next = newNode;
    return head;
}

 

Insertion after a particular node -

In this case a reference to a particular node will be given. Then a new node will be inserted after that.

If the reference of the node is not given instead data of the node is given, then we have to traverse to the given node matching the given data and then we will insert the new node after that node.

void insertAfterNode(Node* givenNode, int x)
{
    Node* newNode = new Node(x);
    
    newNode->next = givenNode->next;
    givenNode->next = newNode;
}

3. Deletion Operation 

This is one type of the operations on linked lists in C/C++, in which we just need to follow the following steps:

  • Traversing to the previous node of the node to be deleted.
     
  • Changing the next pointer of that previous node to point to the address of the next node of the node to be deleted.
     
  • Freeing up the memory which is occupied by the node to be deleted.
Node deleteNode(Node* head, Node* toBeDeleted)
{

    // If the node to be deleted is the head node.
    if(head == toBeDeleted) 
    {
        return head.next;
    }

    // temp is the traversing node.
    Node* temp = head;
    
    while( temp->next != NULL )
    {

        // Searching for the previous node of the node to be deleted.
        if(temp->next == toBeDeleted) 
        {
            temp->next = temp->next->next;

            // Freeing up the memory of the node to be deleted.
            return head;
        }
        temp = temp->next;
    }

    // If no node matches in the Linked List.
    return head;
}

4. Updation Operation

This kind is one of the operations on linked lists in C/C++, in which we have to replace the data part of the required node with the given value.

For this, we will be traversing throughout the linked list until we find a node that will be matching to the required node to be updated.

void updateNode(Node* head, int value, int newValue)
{
    // temp is the traversing node
    Node* temp = head;
    while(temp != NULL)
    {
        // If the node matches the given node to be updated.
        if( temp->data == val)
        { 
            // Updating the data part of the node with the new value.
            temp->data = newVal;
            return;
        }
        temp = temp->next;
    }
}

5. Sort Operation

This operation sorts the nodes present in a linked list. You can use various sorting algorithms for linked lists but merge sort is one of the most performant. Let's see the implementation of Merge sort for singly linked lists in C++:-

ListNode* mergeLists(ListNode* Left, ListNode* Right){
    ListNode *head = new ListNode(-1), *curr = head;
    
    while(Left && Right){
        if(Left->val < Right->val){
            curr->next = Left;
            Left = Left->next;
        }else{
            curr->next = Right;
            Right = Right->next;
        }
        curr = curr->next;
    }
    
    curr->next = (Left)?Left:Right;
    
    return head->next;
}

ListNode* sortList(ListNode* head) {
    if(!head || !head->next) return head;

    ListNode *slow = head, *fast = head->next;
    
    while(fast && fast->next){
        slow = slow->next;
        fast = fast->next->next;
    }
    
    auto Right = sortList(slow->next);
    slow->next = NULL;
    auto Left = sortList(head);
    
    return mergeLists(Left, Right);
}

 

The sortList() function accepts the Linked List head pointer and returns the head pointer after sorting it recursively. At each step, the middle node is found, and the left and right halves are sorted independently, and then they are merged using the mergeLists() helper function.

Types of Linked Lists

There are three types of linked lists that have their own unique ways of implementation. They are namely:

  1. Singly Linked Lists. 
     
  2. Doubly Linked List
     
  3. Circular Linked Lists.
     

Singly Linked Lists

Singly Linked List is the collection of nodes which consist of data and the pointer part which will be pointing to the address of the next node.

singly linked list

The structure of the node of Singly Linked List be like:

Struct Node
{
    int data;
    Node* next;
};

 

The nodes are connected with  the help of the next pointer which is pointing towards the address of the next node. If the next node is not present or the current node is the last node of the Linked List then the next pointer will be pointing to NULL.

singly linked list

Doubly Linked Lists

Doubly Linked List is the collection of nodes which consists of data and two pointers one of which will be pointing to the previous node’s address and another will be pointing to the next node’s address.

Doubly Linked List

The structure of the node of Singly Linked List be like:

Struct Node
{
    int data;
    Node* next;
    Node* prev;
};

 

The nodes are connected with the help of the next pointer which is pointing towards the address of the next node and the prev pointer which is pointing towards the address of the previous node. If the next node is not present or the current node is the last node of the Linked List then the next pointer will be pointing to NULL. And in the other case if the previous node is not present or the current node is the first node of the linked list then the prev pointer will be pointing to NULL.

Doubly Linked Lists

Circular Linked Lists

Circular Linked List is the collection of nodes which consists of data and a pointer which will be pointing to the next node’s address.

The Last node’s next pointer will be pointing to the first node of the Circular Linked List.

Advantages of Linked List

 

1. Dynamic size: One of the main advantages of linked lists is their ability to grow or shrink dynamically during runtime. Unlike arrays, which have a fixed size determined at the time of declaration, linked lists can accommodate changes in the number of elements without the need for resizing. This flexibility makes linked lists suitable for scenarios where the size of the data is unknown or can vary significantly.

2. Efficient insertion and deletion: Linked lists provide efficient insertion and deletion operations, especially when dealing with elements in the middle of the list. In an array, inserting or deleting elements in the middle requires shifting all the subsequent elements, which can be time-consuming. In contrast, linked lists allow for constant-time (O(1)) insertion and deletion by simply adjusting the pointers of the nodes. This efficiency makes linked lists advantageous in scenarios that involve frequent modifications to the list.

3. No need for contiguous memory: Linked lists do not require contiguous memory allocation like arrays do. Each node in a linked list is allocated memory independently and can be scattered throughout the memory. This property makes linked lists suitable for situations where memory is fragmented or when it is difficult to allocate a large contiguous block of memory. Linked lists can efficiently utilize the available memory space.

4. Flexibility in organization: Linked lists offer flexibility in terms of how the elements are organized. They can be easily modified to support various structures such as singly linked lists, doubly linked lists, or circular linked lists. This flexibility allows for the implementation of specialized data structures like stacks, queues, or hash tables using linked lists as the underlying representation.

5. Efficient memory utilization: Linked lists allocate memory for each node dynamically, which means that they only use memory for the actual elements stored in the list. In contrast, arrays may have unused or wasted memory if the actual number of elements is less than the allocated size. Linked lists can be memory-efficient, especially when dealing with large datasets or when the number of elements is unknown beforehand.

6. Easy implementation of certain algorithms: Certain algorithms, such as merging sorted lists or implementing hash tables with chaining, can be more easily implemented using linked lists. The ability to rearrange pointers and dynamically allocate nodes makes linked lists a natural choice for such algorithms. Linked lists can simplify the logic and improve the efficiency of specific algorithmic tasks.

7. Persistent data structures: Linked lists can be used to implement persistent data structures, which are data structures that preserve previous versions of themselves when modified. Each modification creates a new version of the list without altering the previous versions. This immutability property is useful in scenarios like undo/redo functionality, version control systems, or functional programming paradigms.

Disadvantages of Linked List

 

1. Random access: Linked lists do not provide efficient random access to elements. Unlike arrays, where elements can be accessed directly using their index, accessing an element in a linked list requires traversing the list from the beginning until the desired element is found. This sequential access makes random access operations, such as accessing an element at a specific position, inefficient with a time complexity of O(n), where n is the number of elements in the list.

2. Extra memory overhead: Linked lists require extra memory to store the pointers or references that connect the nodes. Each node in a linked list contains not only the data but also one or more pointers to the next or previous nodes. This additional memory overhead can be significant, especially when the size of the data stored in each node is small compared to the size of the pointers. In contrast, arrays do not require any extra memory for connections between elements.

3. Cache inefficiency: Linked lists are not cache-friendly compared to arrays. In arrays, elements are stored contiguously in memory, which allows for better cache utilization when accessing elements sequentially. However, in linked lists, nodes are scattered throughout the memory, and accessing them sequentially may result in cache misses. This cache inefficiency can lead to slower performance, especially when traversing large linked lists.

4. Complexity of implementation: Implementing basic operations like insertion, deletion, and traversal in a linked list can be more complex compared to arrays. Maintaining the correct connections between nodes, handling edge cases, and ensuring proper memory management require careful programming. This complexity can make the code harder to write, debug, and maintain compared to array-based implementations.

5. Lack of spatial locality: Linked lists do not provide good spatial locality, which refers to the proximity of elements in memory. In arrays, elements are stored contiguously, so accessing one element makes it likely that the next element will also be accessed soon. This spatial locality can lead to better cache performance. In linked lists, nodes are scattered in memory, so accessing one node does not guarantee that the next node will be nearby in memory, resulting in reduced spatial locality and potential performance impact.

6. Difficulty in reverse traversal: Traversing a singly linked list in reverse order is not efficient without modifying the list structure. While doubly linked lists allow for efficient reverse traversal, singly linked lists require traversing the entire list to reach the previous elements. This limitation can be problematic when you need to access elements in reverse order frequently.

Applications of Linked List

 

1. Implementing stacks and queues: Linked lists are commonly used to implement stacks and queues. In a stack, elements are inserted and removed from the same end (top), following the Last-In-First-Out (LIFO) principle. In a queue, elements are inserted at one end (rear) and removed from the other end (front), following the First-In-First-Out (FIFO) principle. Linked lists provide efficient insertion and deletion operations at the ends, making them suitable for these data structures.

2. Building hash tables with chaining: Hash tables are data structures that provide fast insertion, deletion, and lookup operations based on keys. One way to handle collisions in hash tables is through chaining, where each bucket of the hash table is a linked list. When multiple elements hash to the same bucket, they are stored in a linked list within that bucket. Linked lists allow for dynamic resizing of the buckets and efficient insertion and deletion of elements in case of collisions.

3. Implementing graphs and trees: Linked lists can be used to represent graphs and trees. In an adjacency list representation of a graph, each vertex is associated with a linked list that stores its adjacent vertices. This allows for efficient traversal and manipulation of the graph. Similarly, trees can be implemented using linked lists, where each node contains a pointer to its child nodes. Linked lists provide a flexible way to represent and traverse these hierarchical data structures.

4. Memory management: Operating systems and memory management systems often use linked lists to keep track of free and allocated memory blocks. The free memory blocks are maintained in a linked list, allowing for efficient allocation and deallocation of memory. When a program requests memory, the memory manager traverses the linked list to find a suitable free block and allocates it to the program. When memory is freed, the block is added back to the linked list for future allocation.

5. Undo and redo functionality: Linked lists can be used to implement undo and redo functionality in applications such as text editors or graphic design software. Each action or operation performed by the user can be stored as a node in a linked list. The undo operation can be achieved by traversing the list backwards, while the redo operation can be achieved by traversing the list forwards. Linked lists provide a natural way to maintain the history of actions and allow for efficient undo and redo operations.

6. Browser history and cache: Web browsers use linked lists to maintain the browsing history and cache. Each visited web page can be represented as a node in a linked list, allowing for efficient navigation through the history. The cache can also be implemented as a linked list, where recently accessed or frequently used resources are stored for quick retrieval. Linked lists enable efficient insertion, deletion, and lookup operations in the browser's history and cache management.

7. Polynomial representation and arithmetic: Linked lists can be used to represent polynomials, where each node represents a term of the polynomial with its coefficient and exponent. Operations like polynomial addition, subtraction, and multiplication can be performed by traversing the linked lists and manipulating the terms accordingly. Linked lists provide a convenient way to store and manipulate polynomial data structures.

You can also read Difference Between Array List and Linked List here.

Frequently Asked Questions

What are the 4 types of linked list?

The four types of linked lists are Singly Linked List, Doubly Linked List, Circular Linked List, and Doubly Circular Linked List. Each has unique properties and advantages for different applications.

Which of the following are linked list operations?

Linked list operations include insertion, deletion, traversal, searching, and updating nodes. These operations are essential for manipulating the elements within the linked list efficiently.

What are the operations of queue?

Queue operations involve enqueue (adding elements to the rear), dequeue (removing elements from the front), peek (viewing the front element without removing), and isEmpty (checking if the queue is empty).

What are the various operations on stack using linked list?

Stack operations using linked list include push (adding elements to the top), pop (removing elements from the top), peek (viewing the top element without removing), and isEmpty (checking if the stack is empty). These operations follow the Last In, First Out (LIFO) principle.

Conclusion

This article covered the types of linked lists and various operations on linked lists in C/C++. If you want to learn more about linked lists and want to practice some questions which require you to take your basic knowledge on operations on linked lists in C/C++, a notch higher, then you can visit our Guided Path for Linked List.

Recommended Reading:

To study more about Linked Lists, refer to Applications Of Linked Lists.

Until then, All the best for your future endeavors, and Keep Coding.

Live masterclass