Linked List in Data Structures - Types of Linked Lists & Its Applications

Linked List in data structures is a non-primitive, linear, and dynamic data structure. It is a chain of nodes where each node is a different element.

In this DSA tutorial, we will see the linked list data structure in detail i.e. its features, working, implementation, etc. To further enhance your understanding and application of linked list concepts, consider enrolling in the Dsa Course, where you can gain comprehensive insights into effective data structure utilization for improved problem-solving and time management.

What is a Linked List in Data Structures?

 Linked List is a fundamental linear data structure used to store elements in a sequential manner. Unlike arrays, the elements (called nodes) in a linked list are not stored in contiguous memory locations. Instead, each node is dynamically allocated and connected using pointers.

Each node in a linked list consists of two parts:

• Data: The actual value or information stored.
• Pointer (or Reference): A link to the memory address of the next node in the sequence.

The first node of a linked list is known as the Head, and it serves as the entry point to the list. The last node is called the Tail, which points to NULL, indicating the end of the list.

Types of Linked Lists in Data Structures

1. Singly-linked list: Here, each node has data and a pointer that contains a reference to the next node in the list. This means that we can traverse in only one direction, from the head to the tail. It is the most common linked list.
2. Doubly linked list: In this type of linked list, each interconnected node contains three fields that contain references to both the next and previous nodes in the list along with the data. This allows traversal in both directions, making it easier to insert or delete nodes at any point in the list.
3. Circular linked list: Here, the last node in the list contains a reference to the first node instead of NULL, creating a loop. This means that traversal can continue indefinitely, until the program crashes.

How to declare/create a Singly-Linked List in Data Structures?

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

Here, we have created a structure named node that contains two variables, data of integer type, and a pointer, next that contains the address of the next node.

If you are still not thorough with pointers and user-defined data types like structures, refer to Data Types in C++ and Pointers in C++.

Standard Operations on Linked Lists in Data Structures

1. Traversal

We can access each element of the linked list starting from the head node. Just keep moving a temp node to the next one and display its contents. When temp is NULL, it means we have reached the end of the linked list so we get out of the while loop.

2. Insertion

We can insert elements to either the beginning, middle, or end of the linked list. Inserting a new node at any given position is done by manipulating at most two next pointers, the prevNode and the newNode.

Set newNode's next pointer to the prevNode's next pointer and set prevNode's next pointer to the newNode where prevNode denotes a pointer to the node after which newNode is to be inserted. However, to access any given position, we have to traverse starting from the head till the prevNode.

The order of execution matters in case of insertion. If we interchange the steps i.e. first set prevNode's next pointer to the newNode then we lose the reference to the remaining of the linked list previously occurring after the prevNode.

3. Deletion

Same as insertion, you can delete either from the beginning, end, or a particular position. Deleting a node located at a specified index is done by manipulating at most two next pointers, the prevNode, and the targetNode.

Set prevNode's next pointer to the targetNode's next pointer and set targetNode's next pointer to NULL where prevNode denotes a pointer to the node after which targetNode is to be deleted.

Just like insertion, the order is important here also. It's important to realize that setting targetNode's next pointer to NULL as the first step would cost us the reference to the remaining of the linked list (if the targetNode wasn't the Tail).

4. Search

It is performed to search for an element from the list using the given key.

The following are the steps to search for an element

• Make head as the current node.
• Run a loop until the current node is NULL because the last element points to NULL.
• In each iteration, check if the key of the node is equal to the item. If the key matches the item, return true otherwise return false.

Read More - Data Structure Interview Questions for Freshers

Implementation of Linked Lists in Different Programming Languages

class Node:
    def __init__(self, data=0, next_node=None):
        self.data = data
        self.next = next_node

class LinkedList:
    def __init__(self):
        self.head = None

    def traversal(self):
        itr = self.head
        while itr:
            print(itr.data)
            itr = itr.next

    def insertion(self, prev_node, new_node):
        new_node.next = prev_node.next
        prev_node.next = new_node

    def deletion(self, prev_node, target_node):
        prev_node.next = target_node.next

    def search(self, key):
        itr = self.head
        while itr:
            if itr.data == key:
                return True
            itr = itr.next
        return False  # key not found!

linked_list = LinkedList()
linked_list.head = Node(1)
second = Node(2)
third = Node(3)

linked_list.head.next = second
second.next = third

# Print the initial linked list
print("Initial Linked List:")
linked_list.traversal()

# Insert a new node (4) after the second node
new_node = Node(4)
linked_list.insertion(second, new_node)

# Print the linked list after insertion
print("\nLinked List after Insertion:")
linked_list.traversal()

# Delete the second node
linked_list.deletion(linked_list.head, second)

# Print the linked list after deletion
print("\nLinked List after Deletion:")
linked_list.traversal()

# Search for a key (3) in the linked list
key = 3
print(f"\nKey {key} is {'found' if linked_list.search(key) else 'not found'} in the linked list.")
    

class Node {
    int data;
    Node next;

    Node() {
        this.data = 0;
        this.next = null;
    }

    Node(int x) {
        this.data = x;
        this.next = null;
    }

    Node(int x, Node next) {
        this.data = x;
        this.next = next;
    }
}

class LinkedList {
    Node head; // 'head' - pointer to the first node of the linked list

    // Constructor for creating a linked list
    LinkedList() {
        this.head = null;
    }

    void traversal() {
        Node itr = head;
        while (itr != null) {
            System.out.println(itr.data);
            itr = itr.next;
        }
    }

    // 'newNode' - pointer to the node to be inserted
    // 'prevNode' - pointer to the node after which insertion occurs
    void insertion(Node prevNode, Node newNode) {
        newNode.next = prevNode.next;
        prevNode.next = newNode;
    }

    // 'targetNode' - pointer to the node to be deleted
    // 'prevNode' - pointer to the node after which deletion occurs
    void deletion(Node prevNode, Node targetNode) {
        prevNode.next = targetNode.next;
    }

    boolean search(int key) {
        Node itr = head;
        while (itr != null) {
            if (itr.data == key)
                return true;
            itr = itr.next;
        }
        return false; // key not found!
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        // Example usage:
        list.head = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);

        list.head.next = second;
        second.next = third;

        // Print the initial linked list
        System.out.println("Initial Linked List:");
        list.traversal();

        // Insert a new node (4) after the second node
        Node newNode = new Node(4);
        list.insertion(second, newNode);

        // Print the linked list after insertion
        System.out.println("\nLinked List after Insertion:");
        list.traversal();

        // Delete the second node
        list.deletion(list.head, second);

        // Print the linked list after deletion
        System.out.println("\nLinked List after Deletion:");
        list.traversal();

        // Search for a key (3) in the linked list
        int key = 3;
        System.out.println("\nKey " + key + " is " + (list.search(key) ? "found" : "not found") + " in the linked list.");
    }
}
    

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;

    Node() : data(0), next(nullptr) {}
    Node(int x) : data(x), next(nullptr) {}
    Node(int x, Node* next) : data(x), next(next) {}
};

class LinkedList {
public:
    Node* head; // pointer to the first node of the linked list

    // constructor for creating a linked list
    LinkedList() : head(nullptr) {}

    void traversal() {
        Node* itr = head;
        while (itr != nullptr) {
            cout << itr->data << endl;
            itr = itr->next;
        }
    }

    // 'newNode' - pointer to the node to be inserted
    // 'prevNode' - pointer to the node after which insertion occurs
    void insertion(Node* prevNode, Node* newNode) {
        newNode->next = prevNode->next;
        prevNode->next = newNode;
    }

    // 'targetNode' - pointer to the node to be deleted
    // 'prevNode' - pointer to the node after which deletion occurs
    void deletion(Node* prevNode, Node* targetNode) {
        prevNode->next = targetNode->next;
        delete targetNode;
    }

    bool search(int key) {
        Node* itr = head;
        while (itr != nullptr) {
            if (itr->data == key)
                return true;
            itr = itr->next;
        }
        return false; // key not found!
    }
};

int main() {
    LinkedList list;

    list.head = new Node(1);
    Node* second = new Node(2);
    Node* third = new Node(3);

    list.head->next = second;
    second->next = third;

    // Print the initial linked list
    cout << "Initial Linked List:" << endl;
    list.traversal();

    // Insert a new node (4) after the second node
    Node* newNode = new Node(4);
    list.insertion(second, newNode);

    // Print the linked list after insertion
    cout << "\nLinked List after Insertion:" << endl;
    list.traversal();

    // Delete the second node
    list.deletion(list.head, second);

    // Print the linked list after deletion
    cout << "\nLinked List after Deletion:" << endl;
    list.traversal();

    // Search for a key (3) in the linked list
    int key = 3;
    cout << "\nKey " << key << " is "
         << (list.search(key) ? "found" : "not found") << " in the linked list." << endl;

    return 0;
}
    

Output

Initial Linked List:
1
2
3

Linked List after Insertion:
1
2
4
3

Linked List after Deletion:
1
4
3

Key 3 is found in the linked list.   

Complexity Analysis of Linked List Operations

• Time Complexity

  Operations	Best Case	Average Case	Worst case
  Traversal	O(n)	O(n)	O(n)
  Insertion	O(1)	O(1)	O(n)
  Deletion	O(1)	O(1)	O(n)
  Search	O(1)	O(n)	O(n)

• Space Complexity: The space complexity of the linked list for all operations is O(n).

Arrays vs Linked Lists in terms of Time Complexity

Differences between Arrays and Linked Lists

After seeing the above comparisons in general and in terms of time complexity, we observe that a linked list is not superior to an array or vice-versa. These data structures complement each other and sometimes become superior to the other in certain use cases.

 Applications of Linked Lists

Linked lists are widely used in computer science for solving various programming problems and for building other data structures. Their ability to handle dynamic memory and efficient insertion and deletion makes them suitable for many applications. Here are the key applications of linked lists:

1. Implementing Other Data Structures- Linked lists serve as the foundation for building several important data structures, such as:

• Stacks (LIFO structure)
• Queues (FIFO structure)
• Graphs (Adjacency List representation)
• Hash Tables (to handle collisions using separate chaining)

2. Dynamic Memory Allocation- Operating systems and memory managers use linked lists to track free and used memory blocks. A free list is maintained using a linked list to allocate and release memory dynamically at runtime.

3. Handling Large and Variable Data Sets- When the size of the data is unknown or changes frequently during program execution, linked lists are preferred over arrays because they don’t require predefined sizing and can grow or shrink efficiently.

4. Navigation Systems-Doubly linked lists are used in web browsers to manage page history, enabling back and forward navigation between web pages.

5. Scheduling and Task Management- Operating systems often use circular linked lists to manage process scheduling, where the scheduler cycles through tasks in a round-robin manner.

6. Undo/Redo Functionality- Applications like text editors and drawing tools use linked lists to implement undo and redo actions, maintaining a history of previous states.

7. Polynomial Arithmetic- In mathematical computations, linked lists can be used to represent and manipulate polynomials where each node holds a term with its coefficient and exponent.

Advantages of Linked Lists

• Efficient Insertion and Deletion: Unlike arrays, inserting or deleting elements in a linked list does not require shifting other elements. Only the pointers need to be updated, making operations like insertion and deletion faster and more efficient, especially for large datasets.
• Flexibility in Implementation: Linked lists are highly versatile and serve as the foundation for various advanced data structures such as stacks, queues, graphs, and hash tables (with chaining). This flexibility makes them essential in many algorithmic and system-level implementations.
• Memory Efficiency: Linked lists utilize memory more effectively by allocating space only as needed. Since nodes are created dynamically, there is no unused or wasted memory as in the case of static data structures like arrays.
• Ease of Implementation: Implementing a linked list is relatively straightforward. It requires defining a simple node structure and a few pointer-based operations, making it a great choice for beginners learning data structures and memory management.
• Dynamic Size Allocation: Linked lists offer dynamic memory allocation, meaning the list can grow or shrink at runtime without predefined size limits. This makes them ideal for applications where the amount of data changes frequently.

1. Memory Consumption: The use of pointers is more in linked lists hence, complex and requires more memory.
2. Traversal: Unlike arrays, linked lists do not allow direct access to individual nodes. Traversing a linked list requires iterating through all the nodes from the beginning of the list until the desired node is found. This can be inefficient and slow, especially for large linked lists. Traversing in reverse order is not possible in singly linked lists.
3. No Random Access: Linked lists do not support random access, i.e., accessing a specific node directly without traversing the list. This can be a significant disadvantage for some applications that require fast access to individual elements.
4. Cache Misses: Linked lists can suffer from cache misses, i.e., when the CPU needs to access data that is not in the cache. This can slow down the execution of programs that frequently access data from linked lists.
5. Search: Linked lists are not efficient for searching large amounts of data, which can be better handled by other data structures such as trees or hash tables.

Summary

So, here we saw every aspect of a linked list in data structures. You might have got at least some idea regarding linked lists and their applications. I know it's quite difficult to understand the whole topic in a single go. Therefore, refer to it again and again till you get thorough with the linked list in data structures. To test your knowledge of linked lists, enroll in our Free Data Structures Certification Training.

Take our Datastructures skill challenge to evaluate yourself!

In less than 5 minutes, with our skill challenge, you can identify your knowledge gaps and strengths in a given skill.

GET FREE CHALLENGE