A linked list is a fundamental data structure that represents a sequence of elements connected through nodes. Each node contains data and a reference (or pointer) to the next node in the sequence. Linked lists come in various forms, including singly linked lists, doubly linked lists, sorted linked lists, and circular linked lists. This article explores the basic concepts and Java implementations of these common linked list structures.

Singly Linked List Implementation

A singly linked list is the most basic form of linked list, where each node contains only a reference to the next node. The first node in the list is called the head node, and the last node points to null, indicating the end of the list.

class SimpleLinkedList {
    private Node start;

    private static class Node {
        int value;
        Node successor;

        Node(int value) {
            this.value = value;
            this.successor = null;
        }
    }

    public void append(int value) {
        Node newNode = new Node(value);
        if (start == null) {
            start = newNode;
        } else {
            Node current = start;
            while (current.successor != null) {
                current = current.successor;
            }
            current.successor = newNode;
        }
    }

    public void displayList() {
        Node current = start;
        while (current != null) {
            System.out.print(current.value + " ");
            current = current.successor;
        }
    }

    public static void main(String[] args) {
        SimpleLinkedList list = new SimpleLinkedList();
        list.append(10);
        list.append(20);
        list.append(30);
        list.displayList(); // Output: 10 20 30
    }
}

Double-Ended Linked List Implemantation

A double-ended linked list extends the singly linked list by maintaining references to both the first and last nodes. This allows for efficient insertion operations at both ends of the list.

class TwoEndedLinkedList {
    private Node front;
    private Node rear;

    private static class Node {
        int value;
        Node next;

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

    public void insertAtEnd(int value) {
        Node newNode = new Node(value);
        if (rear == null) {
            front = rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
    }

    public void displayList() {
        Node current = front;
        while (current != null) {
            System.out.print(current.value + " ");
            current = current.next;
        }
    }

    public static void main(String[] args) {
        TwoEndedLinkedList list = new TwoEndedLinkedList();
        list.insertAtEnd(5);
        list.insertAtEnd(15);
        list.insertAtEnd(25);
        list.displayList(); // Output: 5 15 25
    }
}

Sorted Linked List Implementation

A sorted linked list manitains its elements in ascending order. When inserting a new element, the list automatically places it in the correct position to preserve the sorted order.

class OrderedLinkedList {
    private Node first;

    private static class Node {
        int value;
        Node next;

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

    public void insert(int value) {
        Node newNode = new Node(value);
        if (first == null || first.value >= newNode.value) {
            newNode.next = first;
            first = newNode;
        } else {
            Node current = first;
            while (current.next != null && current.next.value < newNode.value) {
                current = current.next;
            }
            newNode.next = current.next;
            current.next = newNode;
        }
    }

    public void displayList() {
        Node current = first;
        while (current != null) {
            System.out.print(current.value + " ");
            current = current.next;
        }
    }

    public static void main(String[] args) {
        OrderedLinkedList list = new OrderedLinkedList();
        list.insert(30);
        list.insert(10);
        list.insert(20);
        list.displayList(); // Output: 10 20 30
    }
}

Doubly Linked List Implementation

A doubly linked list is a more complex structure where each node contains references to both the previous and next nodes. This allows for bidirectional traversal of the list.

class BidirectionalLinkedList {
    private Node beginning;
    private Node end;

    private static class Node {
        int value;
        Node predecessor;
        Node successor;

        Node(int value) {
            this.value = value;
            this.predecessor = null;
            this.successor = null;
        }
    }

    public void add(int value) {
        Node newNode = new Node(value);
        if (beginning == null) {
            beginning = end = newNode;
        } else {
            end.successor = newNode;
            newNode.predecessor = end;
            end = newNode;
        }
    }

    public void displayForward() {
        Node current = beginning;
        while (current != null) {
            System.out.print(current.value + " ");
            current = current.successor;
        }
    }

    public void displayBackward() {
        Node current = end;
        while (current != null) {
            System.out.print(current.value + " ");
            current = current.predecessor;
        }
    }

    public static void main(String[] args) {
        BidirectionalLinkedList list = new BidirectionalLinkedList();
        list.add(100);
        list.add(200);
        list.add(300);
        list.displayForward(); // Output: 100 200 300
        System.out.println();
        list.displayBackward(); // Output: 300 200 100
    }
}

Conclusion

This article has presented four common linked list implementations in Java: singly linked lists, double-ended linked lists, sorted linked lists, and doubly linked lists. Each structure has its unique characteristics and use cases. Singly linked lists offer simplicity for basic data storage; double-ended linked lists are efficient for insertions at both ends; sorted linked lists maintain ordered data collections; and doubly linked lists support bidirectional traversal for more complex applications. Through these examples, you should now have a better understanding of linked list structures and their implementations in Java.