1. Definition

A Linked List is a linear data structure where elements (called nodes) are connected using pointers (references) instead of being stored in contiguous memory (like arrays).

Each node has:

• Data → the actual value.
• Pointer (next) → a reference to the next node.

👉 This allows dynamic memory allocation (grow/shrink easily) unlike arrays.

---

2. Basic Structure (Java Example)

class Node {
    int data;       // Value
    Node next;      // Pointer to next node
    Node(int d) {   // Constructor
        data = d;
        next = null;
    }
}

---

🏷️ Types of Linked Lists

1. Singly Linked List

• Each node has data + pointer to next node.
• Traversal is only in one direction (forward).
• Last node points to null.

✅ Pros: Simple, less memory than doubly list.
❌ Cons: No backward traversal.

Illustration:
[10|next] → [20|next] → [30|null]

---

2. Doubly Linked List

• Each node has 3 parts: data, prev (pointer to previous node), and next (pointer to next node).
• Traversal possible in both directions.

✅ Pros: Fast insertion/deletion in both directions.
❌ Cons: Extra memory for prev pointer.

Illustration:
null ← [10|prev,next] ⇄ [20|prev,next] ⇄ [30|prev,next] → null

---

3. Circular Linked List

• Last node points back to the first node instead of null.
• Can be singly circular (only next connects in a loop) or doubly circular (both prev and next connect in a loop).

✅ Pros: Good for cyclic tasks (e.g., round-robin scheduling).
❌ Cons: Infinite loop possible if not careful.

Illustration (Singly Circular):
[10|next] → [20|next] → [30|next] → back to [10]

---

📌 Quick Comparison

Type	Traversal	Memory Use	Last Node Points To	Use Case
Singly	Forward only	Less	null	Simple dynamic lists
Doubly	Forward & Backward	More (extra pointer)	null (both sides)	Editors (undo/redo), navigation
Circular	Forward (or both if doubly)	Moderate	First node	CPU scheduling, buffers

---

👉 So, in short:

• Singly → Simple, lightweight.
• Doubly → Flexible navigation.
• Circular → Useful for loops/cycles.

---

LinkedList Implementation (Singly)

public class LinkedList {

    private Node head;
    private Node tail;
    private int length;

    class Node {
        int value;
        Node next;

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

    public LinkedList(int value) {
        Node newNode = new Node(value);
        head = newNode;
        tail = newNode;
        length = 1;
    }

    public Node getHead() { return head; }
    public Node getTail() { return tail; }
    public int getLength() { return length; }

    public void printList() {
        Node temp = head;
        while (temp != null) {
            System.out.println(temp.value);
            temp = temp.next;
        }
    }

    public void printAll() {
        if (length == 0) {
            System.out.println("Head: null");
            System.out.println("Tail: null");
        } else {
            System.out.println("Head: " + head.value);
            System.out.println("Tail: " + tail.value);
        }
        System.out.println("Length:" + length);
        System.out.println("\nLinked List:");
        if (length == 0) {
            System.out.println("empty");
        } else {
            printList();
        }
    }

    public void makeEmpty() {
        head = null;
        tail = null;
        length = 0;
    }

    public void append(int value) {
        Node newNode = new Node(value);
        if (length == 0) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            tail = newNode;
        }
        length++;
    }

    public Node removeLast() {
        if (length == 0) return null;
        Node temp = head;
        Node pre = head;
        while (temp.next != null) {
            pre = temp;
            temp = temp.next;
        }
        tail = pre;
        tail.next = null;
        length--;
        if (length == 0) {
            head = null;
            tail = null;
        }
        return temp;
    }

    public void prepend(int value) {
        Node newNode = new Node(value);
        if (length == 0) {
            head = newNode;
            tail = newNode;
        } else {
            newNode.next = head;
            head = newNode;
        }
        length++;
    }

    public Node removeFirst() {
        if (length == 0) return null;
        Node temp = head;
        head = head.next;
        temp.next = null;
        length--;
        if (length == 0) tail = null;
        return temp;
    }

    public Node get(int index) {
        if (index < 0 || index >= length) return null;
        Node temp = head;
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        return temp;
    }

    public boolean set(int index, int value) {
        Node temp = get(index);
        if (temp != null) {
            temp.value = value;
            return true;
        }
        return false;
    }

    public boolean insert(int index, int value) {
        if (index < 0 || index > length) return false;
        if (index == 0) { prepend(value); return true; }
        if (index == length) { append(value); return true; }
        Node newNode = new Node(value);
        Node temp = get(index - 1);
        newNode.next = temp.next;
        temp.next = newNode;
        length++;
        return true;
    }

    public Node remove(int index) {
        if (index < 0 || index >= length) return null;
        if (index == 0) return removeFirst();
        if (index == length - 1) return removeLast();
        Node prev = get(index - 1);
        Node temp = prev.next;
        prev.next = temp.next;
        temp.next = null;
        length--;
        return temp;
    }

    public void reverse() {
        Node temp = head;
        head = tail;
        tail = temp;
        Node after;
        Node before = null;

        for (int i = 0; i < length; i++) {
            after = temp.next;
            temp.next = before;
            before = temp;
            temp = after;
        }
    }
}

Notes & Tips

• Singly list keeps both head and tail for O(1) addLast.
• Doubly list uses sentinel (dummy) head/tail nodes to simplify edge cases (no null checks when linking/unlinking).
• Circular list stores only tail (so head == tail.next) for O(1) addFirst and addLast.