Linked List - Data Structures and Algorithms (DSA) Guide

A Linked List is a data structure used for storing collections of data. Unlike an array, which stores data contiguously in memory, a Linked List stores references to its elements.

A single element in a Linked List, typically called a “node,” holds both the data and a reference (or “link”) to the next node in the sequence.

Types of Linked Lists

Singly Linked List: Each node has a link to the next node.
Doubly Linked List: Each node has links to both the next and previous nodes.
Circular Linked List: The last node in the list points back to the first node instead of having a null reference.

Advantages

Dynamic size
Efficient insertions and deletions

Disadvantages

No direct access to random elements
Extra memory required for storing node references

Implementing (Singly) Linked List in Java

public class LinkedList {
    // Inner class for the nodes
    private static class Node {
        int data;
        Node next;

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

    // Reference to the head node
    private Node head;

    // Constructor to initialize the linked list
    public LinkedList() {
        this.head = null;
    }

    // Method to add an element to the end of the list
    public void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }

    // Method to delete an element from the list
    public void delete(int data) {
        if (head == null) {
            return;
        }

        // Special case: head needs to be deleted
        if (head.data == data) {
            head = head.next;
            return;
        }

        Node current = head;
        while (current.next != null) {
            if (current.next.data == data) {
                current.next = current.next.next;
                return;
            }
            current = current.next;
        }
    }

    // Method to display the elements in the list
    public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    // Main method to test the linked list
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        
        System.out.print("List after adding elements: ");
        list.display();  // Output: 1 2 3 4

        list.delete(2);
        System.out.print("List after deleting 2: ");
        list.display();  // Output: 1 3 4

        list.delete(1);
        System.out.print("List after deleting 1: ");
        list.display();  // Output: 3 4

        list.delete(4);
        System.out.print("List after deleting 4: ");
        list.display();  // Output: 3
    }
}

Usage of Linked Lists

Linked lists are used in various scenarios for different advantages they offer:

Dynamic Memory Allocation: Unlike arrays, they can easily grow or shrink in size, allocating memory as needed.
Efficient Insertions/Deletions: Adding or removing an element doesn’t require shifting, unlike arrays, making these operations quicker.
Implementation of Other Data Structures: Used as building blocks for more complex data structures like stacks, queues, and graphs.
Memory Utilization: Good option when you have a limited understanding of the data you need to store and want to use memory more efficiently.
Sequence Maintenance: Used in scenarios like maintaining a playlist where the order of elements can change frequently.
Polynomial Representation: Used in computer algebra systems for representing polynomials.
Page Replacement Algorithms: In Operating Systems, used in Least Recently Used (LRU) cache scheme.
Undo Functionality: In text editors, to keep track of editing history for undo operations.
Sparse Data Structures: Useful in creating sparse arrays or matrices.

Java and Singly Linked Lists: Using Built-in Constructs

Java provides an in-built class to deal with the singly linked list data structure. Let’s explore it in detail!

1. LinkedList Class:

Although Java’s LinkedList class is implemented as a doubly-linked list, its functionality and methods can be used to operate as a singly linked list. It resides in the java.util package.

Key Methods:

add(E e): Appends the specified element to the end of the list.
add(int index, E element): Inserts the specified element at the specified position in the list.
get(int index): Returns the element at the specified position in the list.
remove(): Retrieves and removes the head (first element) of the list.
remove(int index): Removes the element at the specified position.
size(): Returns the number of elements in the list.

2. Using LinkedList as a Singly Linked List:

Though LinkedList is inherently doubly-linked, we can restrict our interactions to make it behave like a singly linked list.

import java.util.LinkedList;

public class SinglyLinkedListDemo {
    public static void main(String[] args) {
        LinkedList<Integer> singlyList = new LinkedList<>();
        
        // Add elements
        singlyList.add(1);
        singlyList.add(2);
        singlyList.add(3);
        
        // Access element by index
        int secondElement = singlyList.get(1);  // Output: 2
        
        // Remove head element
        int removedElement = singlyList.remove();  // Removes the head. Output: 1
    }
}

3. Points to Note:

While LinkedList is a doubly-linked list at its core, by only using certain methods and avoiding direct navigation to previous nodes, you can use it as a singly linked list.
Java’s standard library doesn’t provide a dedicated singly linked list implementation because the LinkedList class is versatile and covers both single and doubly linked list use cases.
For most applications, the overhead of a doubly-linked list in the LinkedList class is negligible, but if the overhead becomes a concern, you might need to implement a custom singly linked list.

In summary, Java’s LinkedList class can serve as a handy tool for singly linked list operations, even though it’s inherently doubly-linked.