Linked Lists: Your Data’s Best Friend, Node Doubt About It!

Introduction

A LinkedList is a fundamental data structure in programming, It consists of a sequence of elements, called nodes, where each node contains some data and a reference (or pointer) to the next node in the sequence.

Imagine you have a bunch of boxes and each box has something inside it along with the address showing where the next box is, that’s pretty much how LinkedList works in programming.

In a LinkedList each box is called a node and it contains two things :

1. The actual data that you want to store(eg: Int, String etc.)
2. Pointer to the next box (node) in the list.

The first box (node) is called as the head of the list and it is a starting point of the list, likewise the last box (node) is called as a tail of the list and it is a ending point of the list. To find a specific node you start from the head and follow the pointers till you reach the node that you were looking for. Adding a new node is like inserting the new node in the chain, LinkedList doesn’t have a predefined length, it can grow and shrink in size because each element contains reference to the next element allowing for dynamic size adjustment.

Visual representation of a LinkedList.

Structure of Node

In a linked list, a node is like a container that holds two things: the actual data you want to store and a reference to the next node in the list.

1. Data: The data part of a node can be any type of information you want to store, like a number, a word, or even a more complex object.
2. Next pointer: The next part of a node is a reference (or pointer) to the next node in the linked list. This pointer tells the computer where to find the next node in the sequence.

Visual Representation of a Node in Linked List

In this diagram, “Data” represents the value stored in the node, and “Next” is a pointer or reference to the next node in the list. The “Next” field stores the memory address of the next node, indicating where it is located in the computer’s memory.

This structure allows linked lists to efficiently store and access data in a flexible manner, as nodes can be added or removed without the need to shift other elements, unlike arrays.

Example :

public class Node {
    int value; //Data store in the Node.
    Node next; //Reference to the next node in the list
    
    // Constructor to create a new node with given data and next reference
    public Node(int data) {
        this.data = data;
        this.next = null; // By default, the next reference is null
    }
 }

Operations on LinkedList

Before delving into the operations of a LinkedList, let’s explore how a basic implementation of a LinkedList should look in Java.

public class LinkedList {
  private Node head; // Head of the Linked List
  private Node tail; // Tail of the Linked List
  private int length; // Length of the Linked List
  
  // Node class representing a single node in the linked list
  private static class Node {
    int value; 
    Node next;
    
    Node(int data) {
        this.data = data;
        this.next = null; 
 }

}

Explanation :

1. LinkedList Class: This class represents a linked list and has three important parts:

• head: It's like the starting point of the list.
• tail: It's like the end point of the list.
• length: It keeps track of how many items are in the list.

2. Node Class: Each item in the list is called a node. It has two parts:

• value: It stores the actual data of the node.
• next: It points to the next node in the list.

3. Node Constructor: When a new node is created, its value is set, and by default, it doesn’t point to any other node (next is null).

1. Get Operation

• What it does: Retrieves the value from a specific position in the linked list.
• How it works:
  - Start at the head of the list.
  - Move through the list until you reach the desired position.
  - Return the value at that position.
• Example: If you have a linked list [5, 3, 9, 2] and you want to get the value at index 2, you would traverse the list and return 9 .
• Time Complexity: O(n)
• Code :

// Method to get the node at a specified index in the linked list
public Node get(int index){
    // Check if the index is out of bounds
    if(index < 0 || index >= length) return null;
    
    // If the index is for the last node, return the tail
    if(index == length - 1) return tail;
    
    // If the index is for the first node, return the head
    if(index == 0) return head;
    
    // Traverse the list to find the node at the specified index
    Node node = head;
    for(int i = 0; i < index; i++){
      node = node.next;
    }
    return node; // Return the node at the specified index
  }

2. Set Operation

• What it does: Updates the value at a specific position in the linked list.
• How it works:
  - Start at the head of the list.
  - Move through the list until you reach the desired position.
  - Update the value at that position with the new value.
• Example: If you have a linked list [5, 3, 9, 2] and you want to set the value at index 1 to 7, the list would become [5, 7, 9, 2] .
• Time Complexity: O(n)
• Code :

// Method to set the value of a node at a specified index in the linked list
public boolean set(int index, int value){
    // Get the node at the specified index
    Node temp = get(index);
    
    // If the node exists, update its value and return true
    if(temp != null){
      temp.value = value;
      return true;
    }
    
    // If the node doesn't exist (index out of bounds), return false
    return false;
}

3. Insert Operation

1. Insert at the end

• What it does : Inserts a node at the end of the linked list.
• How it works :
  - create a new node with the given value.
  - If the list is empty, set both head and tail to the new node.
  - Otherwise, set the next of the current tail to the new node, and update the tail to the new node.
• Example : If you have a linked list [5, 3, 9] and you want to insert 7 at the end, the list would become [5, 3, 9, 7] .
• Time Complexity: O(1)
• Code :

// Method to append a new node with the given value at the end of the linked list
public void append(int value) {
    // Create a new node with the given value
    Node newNode = new Node(value);
    
    // If the list is empty, set both head and tail to the new node
    if (length == 0) {
        head = newNode;
        tail = newNode;
    } else {
        // Otherwise, set the next of the current tail to the new node and update the tail
        tail.next = newNode;
        tail = newNode;
    }
    length++; // Increase the length of the list
}

2. Insert at the Beginning

• What it does : Inserts a new node with a given value at the beginning of the linked list.
• How it works :
  - create a new node with the given value.
  - Set the next of the new node to the current head.
  - Update the head to the new node.
• Example : If you have a linked list [5, 3, 9] and you want to insert 7 at the beginning, the list would become [7, 5, 3, 9] .
• Time Complexity: O(1)
• Code :

// Method to prepend a new node with the given value at the beginning of the linked list
public void prepend(int value){
    // Create a new node with the given value
    Node prepend = new Node(value);
    
    // If the list is empty, set both head and tail to the new node
    if(length == 0){
      head = prepend;
      tail = prepend;
    }else {
      // Otherwise, set the next of the new node to the current head and update the head to the new node
      prepend.next = head;
      head = prepend;
    }
    length++; // Increase the length of the list
}

3. Insert in the Middle

• What it does: Inserts a new node with a given value at a specific position in the linked list.
• How it works:
  - Find the node at the position just before the desired position.
  - Create a new node with the given value.
  - Set the next of the new node to the next of the found node.
  - Set the next of the found node to the new node.
• Example: If you have a linked list [5, 3, 9] and you want to insert 7 at index 1, the list would become [5, 7, 3, 9] .
• Time Complexity: O(n)
• Code :

// Method to insert a new node with the given value at a specified index in the linked list
public boolean insert(int index, int value){
    // Check if the index is out of bounds
    if(index < 0 || index > length){
      return false;
    }
    
    // If the index is at the beginning, prepend the new node
    if (index == 0) {
      prepend(value);
      return true;
    }
    
    // If the index is at the end, append the new node
    if(index == length){
      append(value);
      return true;
    }
    
    // For other indexes, insert the new node in between two existing nodes
    Node newNode = new Node(value);
    Node temp = get(index - 1);
    newNode.next = temp.next;
    temp.next = newNode;
    length++;
    return true;
}

4. Remove Operation

1. Remove at the End

• What it does: Removes the node at the end of the linked list.
• How it works:
  - Start at the head of the list.
  - Move through the list until you reach the second-to-last node.
  - Set the next of the second-to-last node to null to remove the last node.
  - Update the tail to point to the second-to-last node.
• Example: If you have a linked list [5, 3, 9, 2] and you want to remove the last node, the list would become [5, 3, 9] .
• Time Complexity: O(n)
• Code:

// Method to remove the last node from the linked list and return it
public Node removeLast() {
    // If the list is empty, return null
    if (length == 0) return null;
    
    Node temp = head;
    Node pre = head;
    
    // Traverse the list to find the last node and the node just before it
    while (temp.next != null) {
      pre = temp;
      temp = temp.next;
    }
    
    // Update the tail to point to the node just before the last node and set its next to null
    tail = pre;
    tail.next = null;
    length--;
    
    // If the list becomes empty after removing the last node, update head and tail to null
    if(length == 0){
      head = null;
      tail = null;
    }
    
    return temp; // Return the removed last node
}

2. Remove at the Beginning

• What it does: Removes the node at the beginning of the linked list.
• How it works:
  - Update the head to point to the second node in the list.
• Example: If you have a linked list [5, 3, 9, 2] and you want to remove the first node, the list would become [3, 9, 2] .
• Time Complexity: O(1)
• Code:

// Method to remove the first node from the linked list and return it
public Node removeFirst(){
    // If the list is empty, return null
    if(length == 0) return null;
    
    // Create a temporary node and set it to the current head
    Node temp = head;
    
    // Move the head to the next node in the list
    head = head.next;
    
    // Set the next of the temporary node to null to detach it from the list
    temp.next = null;
    
    // Decrement the length of the list
    length --;
    
    // If the list becomes empty after removing the first node, update tail to null
    if(length == 0) tail = null;
    
    return temp; // Return the removed first node
}

3. Remove in the middle

• What it does: Removes the node at a specific position in the linked list.
• How it works:
  - Find the node at the position just before the desired position.
  - Set the next of the found node to skip over the node to be removed.
• Example: If you have a linked list [5, 3, 9, 2] and you want to remove the node at index 1, the list would become [5, 9, 2].
• Time Complexity: O(n)
• Code:

// Method to remove the node at the specified index from the linked list and return it
public Node remove(int index){
    // Check if the index is out of bounds
    if(index < 0 || index >= length) return null;
    
    // If the index is at the beginning, remove the first node
    if(index == 0) return removeFirst();
    
    // If the index is at the end, remove the last node
    if(index == length - 1) return removeLast();
    
    // Find the node just before the node to be removed and the node to be removed
    Node prev = get(index - 1);
    Node temp = get(index);
    
    // Update the next of the previous node to skip over the node to be removed
    prev.next = temp.next;
    
    // Set the next of the removed node to null to detach it from the list
    temp.next = null;
    
    // Decrement the length of the list
    length--;
    
    return temp; // Return the removed node
}

5. Reversal Operation

What it does: Reverses the order of nodes in the linked list.

How it works:

• Initialize three pointers: current, prev (initialized to null), and next.
• Iterate through the list:
  - Set next to the next node of current.
  - Set the next of current to prev (reversing the link).
  - Move prev and current one step forward in the list.
  - Set the new head of the list to prev (which will be the original tail after reversal).
• Example: If you have a linked list [5, 3, 9, 2], after reversal, it would become [2, 9, 3, 5].
• Time Complexity: O(n)
• Code:

// Method to reverse the linked list
public void reverse() {
    Node prev = null; // Initialize a pointer to the previous node (starts as null)
    Node current = head; // Initialize a pointer to the current node (starts at the head)
    Node next = null; // Initialize a pointer to the next node

    // Iterate through the list
    while (current != null) {
        next = current.next; // Save the next node
        current.next = prev; // Reverse the link to the previous node
        prev = current; // Move the prev pointer to the current node
        current = next; // Move the current pointer to the next node
    }

    head = prev; // Set the new head of the list to the last node (prev)
}

Advantages and Disadvantages

Advantages :

1. Dynamic Size: Linked lists can grow or shrink in size dynamically without the need to specify the size beforehand, unlike arrays.
2. Insertion and Deletion: Insertion and deletion operations are efficient in linked lists, especially for large lists, as they involve only changing the links, without the need to shift elements.
3. No Wastage of Memory: Linked lists can use memory efficiently, as they only allocate memory when new nodes are added.
4. Versatility: There are various types of linked lists like singly linked lists, doubly linked lists, and circular linked lists, each offering different properties and uses.

Disadvantages :

1. Random Access: Unlike arrays, linked lists do not support random access to elements. Accessing an element in a linked list requires traversing the list from the beginning, which can be inefficient for large lists.
2. Memory Overhead: Each node in a linked list requires extra memory for storing the reference to the next node, which can lead to higher memory overhead compared to arrays.
3. Cache Inefficiency: Linked lists may exhibit poor cache performance, especially in large lists, as the elements are stored in non-contiguous memory locations.
4. Complexity: Implementing and manipulating linked lists can be more complex than arrays, especially for beginners, due to the need to manage pointers and node allocation.

Real World Applications

1. Undo Functionality in Text Editors: Linked lists can be used to implement the undo functionality in text editors. Each operation (like typing a character or deleting a word) can be stored as a node in the linked list, allowing users to undo actions by traversing the list in reverse.
2. Music Player Playlist: Linked lists can be used to implement playlists in music players. Each song can be stored as a node in the list, with links to the next and previous songs, allowing for easy navigation and manipulation of the playlist.
3. Browser History: Linked lists can be used to implement the back and forward functionality in web browsers. Each visited page can be stored as a node in the list, allowing users to navigate through their browsing history.
4. Stacks and Queues: Linked lists can be used to implement stacks and queues, which are fundamental data structures used in many applications. In a stack, each element is added and removed from the same end, while in a queue, elements are added to one end and removed from the other.
5. File System: Linked lists can be used to represent the file system in operating systems. Each directory or file can be represented as a node in the list, with links to other directories or files in the same directory.

Problems to Solve — Leet Code

1. Middle of the Linked List — LeetCode
2. Delete Node in a Linked List — LeetCode
3. Linked List Components — LeetCode

Resources :

1. Cracking The Coding Interview
2. GeeksForGeeks
3. Google : DSA

I hope you found this article helpful, Leave a comment if you liked it or even if you have any suggestions.

Thank you for your time!