Linked Lists in Java

Hello, young coders! Today, we’re going to explore the world of linked lists in Java. We’ll learn about singly linked lists, doubly linked lists, circular linked lists, and how we can use arrays for node-based storage. Let’s dive in!

What is a Linked List?

A linked list is a type of data structure used in computer science. It’s like a chain of nodes, where each node contains data and a reference (or link) to the next node in the sequence. This structure allows for efficient insertions and deletions.

class Node {
    int data;
    Node next;

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

Singly Linked Lists

A singly linked list is the simplest type of linked list. Each node has data and a link to the next node. The start of the list is referred to as the head. If the head is null, that means the list is empty.

class SinglyLinkedList {
    Node head;

    SinglyLinkedList() {
        this.head = null;
    }
}

Doubly Linked Lists

A doubly linked list is a bit more complex. Each node has data and two links: one to the next node and one to the previous node. This allows us to traverse the list in both directions.

class Node {
    int data;
    Node next;
    Node prev;

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

class DoublyLinkedList {
    Node head;

    DoublyLinkedList() {
        this.head = null;
    }
}

Circular Linked Lists

A circular linked list is a variation where the list is linked to form a circle. The last node points back to the first node.

class CircularLinkedList {
    Node head;

    CircularLinkedList() {
        this.head = null;
    }

    void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            newNode.next = head;
        } else {
            Node last = head;
            while (last.next != head) {
                last = last.next;
            }
            last.next = newNode;
            newNode.next = head;
        }
    }
}

Node-Based Storage with Arrays

Arrays can also be used to store nodes. This is useful when you need random access to elements. Each index of the array can hold a node.

Node[] nodeArray = new Node[10];
for (int i = 0; i < 10; i++) {
    nodeArray[i] = new Node(i);
}

Linked List Type	Description	Java Node Representation
Singly Linked List	A simple list where each node contains data and a pointer to the next node.	java class Node { int data; Node next; Node(int d) { data = d; next = null; } }
Doubly Linked List	A list where each node contains data, a pointer to the next node, and a pointer to the previous node.	java class Node { int data; Node next; Node prev; Node(int d) { data = d; next = null; prev = null; } }
Circular Linked List	A list where the last node points back to the first node, forming a circle.	java class Node { int data; Node next; Node(int d) { data = d; next = this; } }
Node-Based Storage with Arrays	Nodes can be stored in arrays when the maximum number of nodes is known in advance.	java Node[] nodes = new Node[10]; for (int i = 0; i < 10; i++) { nodes[i] = new Node(i); }

That’s it for today’s lesson on linked lists in Java. Remember, practice makes perfect. So, try to write your own linked lists and play around with them.