Linked list data structure

A linked list is a fundamental data structure that stores a collection of elements in a linear order. Unlike arrays, linked lists do not store elements in contiguous memory locations, which allows for more flexible memory usage and easier insertion and deletion operations. Java provides a standard implementation of linked lists through the LinkedList class in the Java Collections Framework, but understanding the inner workings of a linked list helps developers better grasp its use cases and limitations. This article delves deep into linked lists, providing a comprehensive overview of their structure, types, implementation, and use in Java.

What is a Linked List?

A linked list consists of nodes where each node contains data and a reference (or link) to the next node in the sequence. The last node’s reference points to null, marking the end of the list. The structure of a linked list can be summarized as:

• Node: The basic unit of the linked list. Each node contains the data and a reference to the next node.
• Head: The first node in the linked list. It is a special pointer that represents the start of the list.
• Tail: The last node in the linked list. Its reference to the next node is null.

Types of Linked Lists

• Singly Linked List: The simplest form of a linked list where each node points to the next node. Traversal is possible only in one direction.
• Doubly Linked List: Each node has two references, one to the next node and one to the previous node. This allows traversal in both directions.
• Circular Linked List: Similar to a singly linked list but with the tail node pointing back to the head node, forming a circular structure.
• Doubly Circular Linked List: A doubly linked list with the tail node’s next reference pointing to the head and the head node’s previous reference pointing to the tail.

Benefits of Linked Lists

1. Dynamic Size: Linked lists can easily grow or shrink in size by simply changing references, unlike arrays which require a fixed size or resizing.
2. Efficient Insertions/Deletions: Inserting or deleting elements in a linked list is more efficient compared to arrays, particularly at the start and middle positions.
3. Memory Efficiency: Nodes are allocated dynamically, preventing the need for pre-allocating large amounts of memory.

Drawbacks of Linked Lists

1. Memory Overhead: Each node requires extra memory for storing references, making linked lists less memory-efficient than arrays.
2. Sequential Access: Accessing elements by index is slower due to the sequential nature of linked lists, unlike arrays which provide direct access.
3. Pointer Management: Managing node references can be complex and error-prone, leading to bugs if not handled correctly.

Implementation of Linked Lists in Java

Let’s explore how to implement a singly linked list in Java. We’ll create a Node class for the list elements and a LinkedList class to manage the list operations.

Node Class

class Node {
    int data;
    Node next;

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

Singly Linked List Class

class SinglyLinkedList {
    private Node head;

    // Add an element at the front of the list
    public void addFirst(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }

    // Add an element at the end of the list
    public void addLast(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
    }

    // Delete the first occurrence of a given value
    public void delete(int data) {
        if (head == null) return;
        if (head.data == data) {
            head = head.next;
            return;
        }
        Node temp = head;
        while (temp.next != null && temp.next.data != data) {
            temp = temp.next;
        }
        if (temp.next == null) return;
        temp.next = temp.next.next;
    }

    // Print all the elements in the list
    public void printList() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }
}

Testing the Singly Linked List

Let’s use this implementation to test a basic singly linked list in Java.

public class LinkedListTest {
    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();
        list.addFirst(10);
        list.addFirst(20);
        list.addLast(30);
        list.addLast(40);

        System.out.print("List elements: ");
        list.printList(); // Output: 20 10 30 40

        list.delete(10);
        System.out.print("After deletion: ");
        list.printList(); // Output: 20 30 40
    }
}

Doubly Linked List Implementation

A doubly linked list requires each node to store references to both the previous and next nodes.

Node Class for Doubly Linked List

class DoublyNode {
    int data;
    DoublyNode prev, next;

    DoublyNode(int data) {
        this.data = data;
        this.prev = this.next = null;
    }
}

Doubly Linked List Class

class DoublyLinkedList {
    private DoublyNode head;

    // Add an element at the front of the list
    public void addFirst(int data) {
        DoublyNode newNode = new DoublyNode(data);
        newNode.next = head;
        if (head != null) {
            head.prev = newNode;
        }
        head = newNode;
    }

    // Add an element at the end of the list
    public void addLast(int data) {
        DoublyNode newNode = new DoublyNode(data);
        if (head == null) {
            head = newNode;
            return;
        }
        DoublyNode temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
        newNode.prev = temp;
    }

    // Delete the first occurrence of a given value
    public void delete(int data) {
        if (head == null) return;
        if (head.data == data) {
            head = head.next;
            if (head != null) {
                head.prev = null;
            }
            return;
        }
        DoublyNode temp = head;
        while (temp != null && temp.data != data) {
            temp = temp.next;
        }
        if (temp == null) return;
        if (temp.next != null) {
            temp.next.prev = temp.prev;
        }
        if (temp.prev != null) {
            temp.prev.next = temp.next;
        }
    }

    // Print all the elements in the list
    public void printList() {
        DoublyNode temp = head;
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }
}

Testing the Doubly Linked List

Let’s create a test to demonstrate the operations of the doubly linked list.

public class DoublyLinkedListTest {
    public static void main(String[] args) {
        DoublyLinkedList list = new DoublyLinkedList();
        list.addFirst(10);
        list.addFirst(20);
        list.addLast(30);
        list.addLast(40);

        System.out.print("List elements: ");
        list.printList(); // Output: 20 10 30 40

        list.delete(10);
        System.out.print("After deletion: ");
        list.printList(); // Output: 20 30 40
    }
}

Use Cases for Linked Lists

1. Dynamic Memory Allocation: Linked lists are suitable for scenarios where the number of elements can change dynamically, preventing the need for resizing arrays.
2. Graph Data Structures: They are often used to represent graph adjacency lists.
3. Implementing Other Data Structures: Linked lists can be used to implement stacks, queues, and other complex data structures.
4. Real-Time Applications: They are used in real-time applications requiring constant time insertions or deletions.