Linked Lists

Definition

A linked list is a linear data structure consisting of elements (nodes) where each node contains two parts:

• Data: The information stored in the node (e.g., numbers, strings).
• Link: A reference to the next node in the list.

Basic Structure of a Linked List

class Node {
    int data;
    Node next;

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

Observations

• At the beginning, the head (starting node) is set to null, meaning the list is empty.
• Elements in the list are dynamic and created using Java's new operator.
• Each node occupies memory in the heap, rather than static memory allocation.
• The size of a pointer reference varies, but generally, a node storing an integer and a pointer will occupy 8 bytes (4+4).
• Traversal is done by following the links between nodes.

Diagram Representation of a Linked List

Each node in a linked list stores a reference to the next node. The last node points to null, indicating the end of the list.

    +------+     +------+------+     +------+------+     +------+------+
    |  *---+---> |  12  |  *---+---> |  46  |  *---+---> |  25  |  NULL|
    +------+     +------+------+     +------+------+     +------+------+

    

Operations on Linked Lists

• Creating a new node
• Adding an element at the end
• Adding an element at the beginning
• Traversing the list
• Deleting an element
• Inserting an element at a specific position

Creating a New Node

Nodes are dynamically allocated using the new operator:

Node p = new Node(12); // Creating a node with data 12
p.next = null; // It points to NULL as it is the last node
    

Adding an Element at the End of the List

To add an element at the end, we first traverse the list to find the last node. Then, we set its next reference to the new node.

class LinkedList {
    Node head;

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

Adding an Element at the Beginning of the List

To add an element at the beginning, we simply set the new node's next pointer to the current head and update the head reference.

public void addAtBeginning(int data) {
    Node newNode = new Node(data);
    newNode.next = head;
    head = newNode;
}
    

Traversing a Linked List

To traverse the list, we start from the head and iterate through each node using the next reference until we reach the end.

public void traverse() {
    Node temp = head;
    while (temp != null) {
        System.out.print(temp.data + " -> ");
        temp = temp.next;
    }
    System.out.println("NULL");
}
    

Deleting an Element from the List

To delete an element, we first locate the node before the target node and adjust its next reference to skip the target node.

public void delete(int key) {
    Node temp = head, prev = null;

    if (temp != null && temp.data == key) {
        head = temp.next;
        return;
    }

    while (temp != null && temp.data != key) {
        prev = temp;
        temp = temp.next;
    }

    if (temp == null) return;
    prev.next = temp.next;
}
    

Inserting an Element After a Given Node

To insert a node after a specific node, we update the next reference of the previous node to point to the new node.

public void insertAfter(Node prevNode, int data) {
    if (prevNode == null) {
        System.out.println("The given previous node cannot be null");
        return;
    }
    Node newNode = new Node(data);
    newNode.next = prevNode.next;
    prevNode.next = newNode;
}
    

Applications of Linked Lists

• Efficient insertion and deletion (compared to arrays)
• Implementation of stacks and queues
• Handling large data structures (e.g., graphs, hash maps)
• Efficient memory usage (nodes are dynamically allocated)

Diagram Representation of a Double-Linked List

    +------+     +------+------+------+     +------+------+------+     +------+------+------+
    |  *---+---> |NULL  |  12  |  *---+---> |      |  46  |  *---+---> |      |  25  |  NULL|
    |      |     |      |      |      |<----+---*  |      |      |<----+---*  |      |      | <--+
    +------+     +------+------+------+     +------+------+------+     +------+------+------+    |
    |      |                                                                                     |
    |  *---+-------------------------------------------------------------------------------------+
    +------+
 
    

Diagram Representation of a Circular Linked List

             
                      +-----------------------------------------------------+
                      |                                                     |
                      ↓                                                     |
     +------+     +------+------+     +------+------+     +------+------+   |
     |  *---+---> |  12  |  *---+---> |  46  |  *---+---> |  25  |  *---+---+
     +------+     +------+------+     +------+------+     +------+------+