DSA: Linked List

What is a Linked List?

A linked list is a linear data structure composed of nodes, each of which holds a value and a reference (or pointer) to the next node in the list. The first node is referred to as the list’s head, while the last node is referred to as the list’s tail.

Because linked lists are dynamic data structures, their size can be easily changed during programme execution by adding or removing nodes. As a result, they are effective in circumstances where the size of the data being saved is unknown or can change dynamically.

Representation of Linked List:

A linked list node has two fields:

• a data field containing the actual value and a pointer field with the location of the next node in the list. This creates a series of nodes, each of which points to the next, producing a linked list.
• The last node in the list has a null pointer field, marking the end of the list.

Why use linked list over array?

Linked lists and arrays are two common data structures used in programming, and each has benefits and drawbacks. Here are some of the advantages of using a linked list versus an array:

• Linked lists have the advantage of being able to grow and decrease dynamically at runtime, as opposed to arrays, which have a fixed size that is determined at initialization.
• Insertions and deletions in an array necessitate element shifting, which can be a time-consuming operation in big arrays. By simply altering the pointers to the neighbouring nodes, linked lists, on the other hand, can conduct insertions and deletions in constant time.
• Linked lists can be more memory-efficient than arrays, particularly for tiny lists or when the size of the list is unknown in advance.
• Linked lists can be used to build a wide range of data structures, including stacks, queues, and hash tables, and can be easily adjusted to meet a number of needs. Because of this versatility, linked lists are a powerful programming tool.
• Linked lists can be easier to sort than arrays in some instances, especially if the list is already partially sorted.

Types of Linked Lists:

The linked list mainly has three types, they are:

• Singly Linked List: Each node in a singly linked list includes a single pointer that leads to the next node in the list. The list’s final node points to null.

• Doubly Linked List: In a doubly linked list, each node contains two pointers, one pointing to the previous node and the other pointing to the next node in the list. The first node’s previous pointer points to null and the last node’s next pointer points to null.

• Circular Linked List: In a circular linked list, the last node of the list points to the first node, making the list circular. The circular linked list can be implemented as both singly and doubly linked list.

Operations in Linked List:

Linked lists support several operations, some of which are:

• Traversal: To traverse through the linked list and visit each node in order to perform a certain operation on it.

Node current = head;
while(current != null) {
    System.out.print(current.data + " ");
    current = current.next;
}

• Insertion: To insert a new node into the linked list. It can be inserted at the beginning, end or at a specific position in the list.

// Definition of a singly linked list node
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

// Inserting a node at the beginning of a singly linked list
public ListNode insertAtBeginning(ListNode head, int val) {
    ListNode newNode = new ListNode(val);
    newNode.next = head;
    return newNode;
}
-
-
-
-
-
-
// Definition of a doubly linked list node
class ListNode {
    int val;
    ListNode prev;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

// Inserting a node at the end of a doubly linked list
public ListNode insertAtEnd(ListNode head, int val) {
    ListNode newNode = new ListNode(val);
    if (head == null) {
        return newNode;
    }
    ListNode curr = head;
    while (curr.next != null) {
        curr = curr.next;
    }
    curr.next = newNode;
    newNode.prev = curr;
    return head;
}

• Deletion: To remove an existing node from the linked list. It can be removed from the beginning, end or at a specific position in the list.

// Deleting a node with a specific value from a singly linked list
public ListNode deleteNode(ListNode head, int val) {
    if (head == null) {
        return null;
    }
    if (head.val == val) {
        return head.next;
    }
    ListNode prev = head;
    ListNode curr = head.next;
    while (curr != null) {
        if (curr.val == val) {
            prev.next = curr.next;
            return head;
        }
        prev = curr;
        curr = curr.next;
    }
    return head;
}

• Searching: To search for a particular node in the linked list.

public class LinkedList {
    Node head; // head of the list
  
    // Node class
    static class Node {
        int data;
        Node next;
  
        // Constructor
        Node(int d)
        {
            data = d;
            next = null;
        }
    }
  
    // Search an element in the linked list
    public boolean search(Node head, int x)
    {
        Node current = head; // Initialize current
        while (current != null) {
            if (current.data == x)
                return true; // data found
            current = current.next;
        }
        return false; // data not found
    }
  
    // Driver Code
    public static void main(String args[])
    {
        LinkedList list = new LinkedList();
  
        list.head = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);
  
        list.head.next = second; // Link first node with the second node
        second.next = third; // Link second node with the third node
  
        int searchData = 3;
        if (list.search(list.head, searchData))
            System.out.println(searchData + " is present in the list");
        else
            System.out.println(searchData + " is not present in the list");
    }
}

• Sorting: To sort the linked list based on some criteria such as ascending or descending order of the data stored in the nodes.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<Integer>();
        list.add(5);
        list.add(1);
        list.add(4);
        list.add(2);
        list.add(3);

        // Using Collections.sort() method
        Collections.sort(list);

        System.out.println("Sorted list: " + list);
    }
}

• Reversing: To reverse the linked list so that the last node becomes the first node and vice versa.

// Reversing a singly linked list
public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

Here’s a table summarizing the time and space complexity for various operations in a linked list:

Operation	Time Complexity	Space Complexity
Insertion at Head	O(1)	O(1)
Insertion at Tail	O(n)	O(1)
Insertion at Index	O(n)	O(1)
Deletion at Head	O(1)	O(1)
Deletion at Tail	O(n)	O(1)
Deletion at Index	O(n)	O(1)
Search	O(n)	O(1)
Access by Index	O(n)	O(1)
Length/Size	O(n)	O(1)
Reverse	O(n)	O(1)
Concatenation	O(1)	O(1)
Split	O(n)	O(1)

Note: also read about Recursion in DSA

Follow Me

If you like my post please follow me to read my latest post on programming and technology.

https://www.instagram.com/coderz.py/

https://www.facebook.com/coderz.py