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

Linked Lists in Data Structures: An Overview

To further enhance your understanding and application of linked list concepts, consider enrolling in the best Data Structures and Algorithms 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?

The first node of a linked list is called the Head, and it acts as an access point. The head pointer points to the first element of the linked list. The last node is called the Tail, and it marks the end of a linked list by pointing to a NULL value. After arrays, linked lists are the second most used data structure.

Representation of Linked Lists in Data Structures

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;
};

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

2. Insertion

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

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

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.

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 commonly used in computer programming for their ability to efficiently store and manipulate collections of data. Here are some common applications of linked lists:

1. Implementing data structures: Linked lists are commonly used to implement data structures like stacks, queues, graphs, and hash tables.
2. Dynamic Memory allocation: A linked list of free memory blocks is maintained, and new memory is allocated by removing blocks from the free list.
3. File systems: Linked lists are used in file systems to represent directories and files.
4. Music and video players:  The list of songs in the music player is linked to the previous and next songs.  Linked lists maintain playlists.
5. Graphs: Adjacency list representation of graphs uses linked lists to store adjacent vertices.
6. Games: Linked lists are used to represent game boards where each element in the list represents a cell on the board.

Advantages of Linked Lists

1. Dynamic: Linked lists can be resized during runtime, which means that anyone can add or remove elements from the list without worrying about the size limitations of the underlying data structure.
2. Efficient insertion and deletion: Adding or removing elements to and from a linked list is very easy because the user only needs to update the address of the pointer of the node as the nodes are stored in random locations.
3. Flexibility: Linked lists can be used to implement a variety of advanced data structures, such as stacks, queues, and hash tables. This flexibility makes linked lists a versatile tool for many programming tasks.
4. Memory efficiency: Memory consumption of a linked list is efficient as its size can grow or shrink dynamically according to our requirements, which means effective memory utilization hence, no memory wastage.
5. Easy implementation: Implementing a linked list is relatively easy, as the developer only needs to define a node structure and a few functions to manipulate the links between nodes.

Disadvantages of Linked Lists

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