Table of Contents

1. Types of Linked Lists

2. Various Operations on Linked Lists

3. Why Do We Need Linked Lists

4. Drawbacks of Linked Lists

Types of Linked Lists

1. Singly Linked List: Each node contains a data element and a reference (link) to the next node in the sequence. It allows traversal only in one direction, from the head to the tail.

2. Doubly Linked List: Each node contains a data element and two references (links), one to the previous node and one to the next node in the sequence. This allows bidirectional traversal.

3. Circular Linked List: Similar to a singly or doubly linked list, but in a circular linked list, the last node points back to the first node (in a singly circular linked list) or the last node points back to the first node and the first node points to the last node (in a doubly circular linked list).

4. Circular Doubly Linked List: It combines the features of a circular linked list and a doubly linked list. Each node has two references, one to the next node and one to the previous node, and the last node points back to the first node.

5. Skip List: A skip list is a probabilistic data structure that allows for fast search, insertion, and deletion operations. It consists of multiple linked lists layers, where each layer represents a subset of the elements in the list, and higher layers provide skip pointers to elements in lower layers.

6. Sparse Linked List: A sparse linked list is used to efficiently represent data with a large number of elements, where most of the elements have a default value. It only stores nodes for non-default values, thereby saving memory.

Various Operations on Linked Lists

1. Insertion

2. Deletion

3. Traversal

4. Sorting

Insertion of a node in a existing list

public class ListNodeInsertingNode {

    //INSERTING A NODE AT THE BEGINNING OF THE LINKED LIST
    public ListNode insertAtBeginning(ListNode head, int valueToInsert){
        //CREATING A NEW NODE
        ListNode newNode = new ListNode(valueToInsert);

        //ESTABLISH THE CONNECTION
        newNode.next = head;

        //REASSIGNING THE HEAD POINTER
        head = newNode;

        //RETURNING THE HEAD
        return head;
    }

    //INSERTING THE NODE AT THE END OF THE LINKEDLISTS
    public ListNode insertAtEnd(ListNode head, int valueToInsert){

        //CREATE A LISTNODE TO INSERT
        ListNode newNode = new ListNode(valueToInsert);

        //TRAVERSE TO THE END OF THE LIST
        ListNode ptr = head;
        while(ptr.next != null){
        ptr = ptr.next;
        }

        //ASSIGN THE NEWNODE TO THE TAIL OF THE LINKEDLISt
        ptr.next = newNode;

        //RETURNING THE HEAD
        return head;
    }


    //INSERTING AT A RANDOM POSITION IN THE LINKEDLIST
    public ListNode insertAt(ListNode head, int valToInsert, int position){

        //CREATE A LISTNODE TO INSERT
        ListNode newNode = new ListNode(valToInsert);

        ListNode ptr = head;
        //TRAVERSE TO THE LOCATION
        for(int i=0; i<position; i++){
            ptr = ptr.next;
        }

        //INSERT THE NODE
        newNode.next = ptr.next;
        ptr.next = newNode;

        //RETURN THE HEAD
        return head;
    }
}

Deletion

public class ListNodeDeletion {
    //DELETING FROM THE HEAD POSITION
    public ListNode deleteFromBeginning(ListNode head){

        //JUST MOVE THE HEAD TO THE NEXT POSITION
        head = head.next;

        //RETURN THE HEAD
        return head;
    }
    //DELETING FROM THE TAIL POSITION
    public ListNode deleteFromTheEnd(ListNode head){
        //MOVE TO THE SECOND LAST NODE
        ListNode ptr = head;
        while(ptr.next.next != null){
            ptr = ptr.next;
        }

        //POINT THE SECOND LAST NODE TO THE NULL
        ptr.next = null;

        //RETURN THE HEAD
        return head;
    }
    //DELETING FROM THE RANDOM POSITION
    public ListNode deleteFromRandom(ListNode head, int position){
        //MOVE TO THE PREVIOUS POSITION OF NODE TO DELETE
        ListNode ptr = head;
        for(int i = 0; i < position - 1; i++){
            ptr = ptr.next;
        }

        //GET THE NODE TO DELETE
        ListNode nodeToDelete = ptr.next;

        //GET THE ADDRESS OF NODE NEXT TO THE NODE TO BE DELETED
        ListNode nextNode = nodeToDelete.next;

        //POINT THE NEXT OF PTR TO NEXTNODE
        ptr.next = nextNode;

        //RETURN HEAD
        return head;


    }
}

Traversal

public class ListNodeTraversal {

  public void traversal(ListNode head){
    ListNode temp = head;

    while(temp != null){
        System.out.println(temp.value);
        if(temp.next != null){
            System.out.print("-->");
        }
        temp = temp.next;
    }
  }

}

Sorting

public class LinkedListSort {

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }
    }

    public static ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;

        ListNode dummy = new ListNode(0);
        ListNode prevSorted = dummy;

        ListNode current = head;
        while (current != null) {
            ListNode nextNode = current.next;

            // Find the position to insert the current node in the sorted part of the list
            ListNode temp = dummy;
            while (temp.next != null && temp.next.val < current.val) {
                temp = temp.next;
            }

            // Insert the current node into the sorted part of the list
            current.next = temp.next;
            temp.next = current;

            // Move to the next node to be sorted
            current = nextNode;
        }

        return dummy.next;
    }

    public static void main(String[] args) {
        // Example usage
        ListNode head = new ListNode(4);
        head.next = new ListNode(2);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(3);

        ListNode sortedList = sortList(head);

        // Print the sorted list for demonstration
        while (sortedList != null) {
            System.out.print(sortedList.val + " ");
            sortedList = sortedList.next;
        }
    }
}

Why do we need Linked Lists ?

1. Dynamic Memory Allocation: Linked lists provide a way to dynamically allocate memory for data elements at runtime. Unlike arrays, where memory allocation is fixed, linked lists allow for flexible memory management, enabling efficient memory utilization in applications with unpredictable data sizes.

2. Insertion and Deletion Efficiency: Linked lists excel in insertion and deletion operations, particularly in scenarios where elements are frequently added to or removed from the data structure. Unlike arrays, which may require shifting elements to accommodate insertions or deletions, linked lists can efficiently perform these operations by adjusting pointers without moving other elements.

3. Variable Size: Linked lists accommodate variable-size data structures, allowing each node to store data of different sizes. This flexibility is advantageous in applications where elements vary significantly in size, such as storing strings of different lengths or objects with varying attributes.

4. Dynamic Data Structures: Linked lists support dynamic data structures, meaning they can grow or shrink in size as needed during program execution. This adaptability is beneficial in scenarios where the size of the data structure is unknown beforehand or changes over time, enabling efficient utilization of memory resources.

5. Efficient Memory Utilization: Linked lists optimize memory utilization by allocating memory for each node individually, only as needed. This contrasts with arrays, which typically allocate a fixed-size block of memory, potentially leading to wasted space when not fully utilized. Linked lists can efficiently use memory resources, especially in applications with sporadic memory demands.

6. Support for Complex Operations: Linked lists facilitate complex data operations, such as reversing the list, merging multiple lists, or splitting a list, with relative ease. These operations can be implemented efficiently by manipulating pointers, making linked lists suitable for various data processing tasks in applications ranging from data structures to algorithms.

7. Ease of Implementation: Linked lists offer a straightforward implementation compared to other data structures like trees or graphs. They consist of simple nodes with references to the next (and sometimes previous) node, making them relatively easy to understand and implement in code.

8. Support for Recursive Algorithms: Linked lists lend themselves well to recursive algorithms due to their recursive nature. Recursive operations, such as traversing the list or performing certain manipulations, can be implemented concisely and efficiently using recursive techniques, leveraging the inherent structure of linked lists.

Drawbacks

1. No Random Access: Unlike arrays, linked lists do not support constant-time random access to elements. Traversing a linked list requires sequential access from the head (or tail), making operations like accessing the k-th element inefficient, as it necessitates traversing k nodes.

2. Extra Memory Overhead: Linked lists incur additional memory overhead due to the storage of pointers (references) alongside data elements. Each node requires extra memory to store pointers to the next (and sometimes previous) node, potentially leading to increased memory consumption compared to arrays, especially for small data elements.

3. Less Cache Locality: Linked lists suffer from poor cache locality compared to arrays. Since nodes are typically allocated dynamically in different memory locations, accessing consecutive elements may result in cache misses, reducing performance, particularly in scenarios with large lists or frequent access patterns.

4. I**nefficient Memory Utilization:** While linked lists offer dynamic memory allocation, they may not always utilize memory efficiently. Each node incurs memory overhead for storing pointers, and fragmentation can occur when nodes are scattered throughout memory, leading to wasted space and inefficient memory utilization.

5. Difficulty in Reversal and Traversal: Certain operations, such as reversing a linked list or traversing it in reverse order, can be more complex and less efficient compared to arrays. Reversing a linked list requires adjusting pointers for each node, potentially necessitating traversal of the entire list.

6. Lack of Support for Binary Search: Linked lists do not support efficient binary search operations due to their sequential nature. Binary search relies on random access to elements, which linked lists lack, making binary search inefficient and impractical for linked lists.

7. Vulnerability to Memory Leaks: Improper management of memory allocation and deallocation in linked lists can lead to memory leaks. Failing to release memory properly for nodes that are no longer in use can result in memory leaks, degrading performance and potentially causing application instability over time.

8. Increased Complexity in Implementation: While linked lists have a simple conceptual structure, implementing and maintaining linked list operations, such as insertion, deletion, and traversal, may involve more complex code compared to arrays. Managing pointers and handling edge cases can introduce additional complexity and potential sources of bugs.