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.

---

Implementation

Awesome—here are complete, production‑ready Java implementations of all three: Singly, Doubly, and Circular (singly) linked lists, plus a tiny Main to demo them. Each class is generic (<T>), includes common operations, and is self‑contained.

You can drop all of these into one file named Main.java. Only Main is public; the list classes use package visibility so the file compiles cleanly.

---

// Main.java
import java.util.Iterator;
import java.util.NoSuchElementException;

public class Main {
    public static void main(String[] args) {
        // === Singly Linked List ===
        SinglyLinkedList<Integer> sll = new SinglyLinkedList<>();
        sll.addLast(10); sll.addLast(20); sll.addFirst(5); sll.add(2, 15);
        System.out.println("SLL: " + sll);              // [5, 10, 15, 20]
        sll.remove(Integer.valueOf(10));
        System.out.println("SLL after remove 10: " + sll);
        sll.reverse();
        System.out.println("SLL reversed: " + sll);

        // === Doubly Linked List ===
        DoublyLinkedList<String> dll = new DoublyLinkedList<>();
        dll.addLast("A"); dll.addLast("B"); dll.addFirst("Z"); dll.add(2, "X");
        System.out.println("DLL: " + dll);              // [Z, A, X, B]
        dll.removeAt(1);                                // remove "A"
        System.out.println("DLL after removeAt(1): " + dll);
        System.out.println("DLL get(1): " + dll.get(1));

        // === Circular Singly Linked List ===
        CircularLinkedList<Integer> cll = new CircularLinkedList<>();
        cll.addLast(1); cll.addLast(2); cll.addLast(3);
        System.out.println("CLL: " + cll);             // [1, 2, 3] (circular)
        cll.addFirst(0);
        System.out.println("CLL after addFirst(0): " + cll);
        cll.removeLast();
        System.out.println("CLL after removeLast(): " + cll);
        System.out.println("CLL contains(2)? " + cll.contains(2));
    }
}

/* ===========================================================
 *  Singly Linked List (Generic)
 *  Time (avg): get O(n), addFirst O(1), addLast O(1) amortized (if tail kept), add(index) O(n)
 *  removeFirst O(1), remove(index/value) O(n)
 *  Space: O(n)
 * =========================================================== */
class SinglyLinkedList<T> implements Iterable<T> {
    private static class Node<T> {
        T data;
        Node<T> next;
        Node(T d) { data = d; }
    }

    private Node<T> head, tail;
    private int size;

    public int size() { return size; }
    public boolean isEmpty() { return size == 0; }
    public void clear() { head = tail = null; size = 0; }

    public void addFirst(T val) {
        Node<T> n = new Node<>(val);
        n.next = head;
        head = n;
        if (tail == null) tail = head;
        size++;
    }

    public void addLast(T val) {
        Node<T> n = new Node<>(val);
        if (tail == null) {
            head = tail = n;
        } else {
            tail.next = n;
            tail = n;
        }
        size++;
    }

    public void add(int index, T val) {
        checkPositionIndex(index); // allow index == size
        if (index == 0) { addFirst(val); return; }
        if (index == size) { addLast(val); return; }
        Node<T> prev = nodeAt(index - 1);
        Node<T> n = new Node<>(val);
        n.next = prev.next;
        prev.next = n;
        size++;
    }

    public T get(int index) {
        checkElementIndex(index);
        return nodeAt(index).data;
    }

    public T set(int index, T val) {
        checkElementIndex(index);
        Node<T> n = nodeAt(index);
        T old = n.data;
        n.data = val;
        return old;
    }

    public T removeFirst() {
        if (head == null) throw new NoSuchElementException("List is empty");
        T val = head.data;
        head = head.next;
        if (head == null) tail = null;
        size--;
        return val;
    }

    public T removeLast() {
        if (head == null) throw new NoSuchElementException("List is empty");
        if (head == tail) {
            T val = head.data;
            head = tail = null;
            size--;
            return val;
        }
        Node<T> prev = head;
        while (prev.next != tail) prev = prev.next;
        T val = tail.data;
        prev.next = null;
        tail = prev;
        size--;
        return val;
    }

    public T removeAt(int index) {
        checkElementIndex(index);
        if (index == 0) return removeFirst();
        Node<T> prev = nodeAt(index - 1);
        Node<T> target = prev.next;
        prev.next = target.next;
        if (target == tail) tail = prev;
        size--;
        return target.data;
    }

    public boolean remove(T value) {
        if (head == null) return false;
        if (equalsVal(head.data, value)) {
            removeFirst(); return true;
        }
        Node<T> prev = head, cur = head.next;
        while (cur != null) {
            if (equalsVal(cur.data, value)) {
                prev.next = cur.next;
                if (cur == tail) tail = prev;
                size--;
                return true;
            }
            prev = cur; cur = cur.next;
        }
        return false;
    }

    public int indexOf(T value) {
        int i = 0;
        for (Node<T> n = head; n != null; n = n.next, i++) {
            if (equalsVal(n.data, value)) return i;
        }
        return -1;
    }

    public boolean contains(T value) { return indexOf(value) != -1; }

    public void reverse() {
        Node<T> prev = null, cur = head, next;
        tail = head;
        while (cur != null) {
            next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        head = prev;
    }

    private Node<T> nodeAt(int index) {
        Node<T> n = head;
        for (int i = 0; i < index; i++) n = n.next;
        return n;
    }

    private boolean equalsVal(T a, T b) { return (a == null) ? b == null : a.equals(b); }
    private void checkElementIndex(int index) {
        if (index < 0 || index >= size) throw new IndexOutOfBoundsException("index=" + index + ", size=" + size);
    }
    private void checkPositionIndex(int index) {
        if (index < 0 || index > size) throw new IndexOutOfBoundsException("index=" + index + ", size=" + size);
    }

    @Override public String toString() {
        StringBuilder sb = new StringBuilder("[");
        Node<T> n = head;
        while (n != null) {
            sb.append(n.data);
            n = n.next;
            if (n != null) sb.append(", ");
        }
        return sb.append("]").toString();
    }

    @Override public Iterator<T> iterator() {
        return new Iterator<T>() {
            Node<T> cur = head;
            @Override public boolean hasNext() { return cur != null; }
            @Override public T next() {
                if (cur == null) throw new NoSuchElementException();
                T val = cur.data; cur = cur.next; return val;
            }
        };
    }
}

/* ===========================================================
 *  Doubly Linked List (Generic, with sentinels)
 *  Time (avg): get O(n), add/remove at ends O(1), add/remove at index O(n)
 *  Space: O(n)
 * =========================================================== */
class DoublyLinkedList<T> implements Iterable<T> {
    private static class Node<T> {
        T data;
        Node<T> prev, next;
        Node() {}
        Node(T d) { data = d; }
    }

    private final Node<T> head; // sentinel before first
    private final Node<T> tail; // sentinel after last
    private int size;

    public DoublyLinkedList() {
        head = new Node<>();
        tail = new Node<>();
        head.next = tail;
        tail.prev = head;
        size = 0;
    }

    public int size() { return size; }
    public boolean isEmpty() { return size == 0; }
    public void clear() {
        head.next = tail; tail.prev = head; size = 0;
    }

    public void addFirst(T val) { linkBetween(new Node<>(val), head, head.next); }
    public void addLast(T val)  { linkBetween(new Node<>(val), tail.prev, tail); }

    public void add(int index, T val) {
        checkPositionIndex(index);
        if (index == size) { addLast(val); return; }
        Node<T> succ = nodeAt(index);
        linkBetween(new Node<>(val), succ.prev, succ);
    }

    public T get(int index) {
        checkElementIndex(index);
        return nodeAt(index).data;
    }

    public T set(int index, T val) {
        checkElementIndex(index);
        Node<T> n = nodeAt(index);
        T old = n.data;
        n.data = val;
        return old;
    }

    public T removeFirst() {
        if (size == 0) throw new NoSuchElementException("List is empty");
        return unlink(head.next);
    }

    public T removeLast() {
        if (size == 0) throw new NoSuchElementException("List is empty");
        return unlink(tail.prev);
    }

    public T removeAt(int index) {
        checkElementIndex(index);
        return unlink(nodeAt(index));
    }

    public boolean remove(T value) {
        for (Node<T> n = head.next; n != tail; n = n.next) {
            if ((value == null && n.data == null) || (value != null && value.equals(n.data))) {
                unlink(n); return true;
            }
        }
        return false;
    }

    public int indexOf(T value) {
        int i = 0;
        for (Node<T> n = head.next; n != tail; n = n.next, i++) {
            if ((value == null && n.data == null) || (value != null && value.equals(n.data))) return i;
        }
        return -1;
    }

    public boolean contains(T value) { return indexOf(value) != -1; }

    // Helpers
    private void linkBetween(Node<T> n, Node<T> prev, Node<T> next) {
        n.prev = prev; n.next = next;
        prev.next = n; next.prev = n;
        size++;
    }

    private T unlink(Node<T> n) {
        Node<T> prev = n.prev, next = n.next;
        prev.next = next; next.prev = prev;
        T val = n.data;
        n.prev = n.next = null; // help GC
        size--;
        return val;
    }

    private Node<T> nodeAt(int index) {
        // Traverse from nearer side
        if (index < (size / 2)) {
            Node<T> x = head.next;
            for (int i = 0; i < index; i++) x = x.next;
            return x;
        } else {
            Node<T> x = tail.prev;
            for (int i = size - 1; i > index; i--) x = x.prev;
            return x;
        }
    }

    private void checkElementIndex(int index) {
        if (index < 0 || index >= size) throw new IndexOutOfBoundsException("index=" + index + ", size=" + size);
    }
    private void checkPositionIndex(int index) {
        if (index < 0 || index > size) throw new IndexOutOfBoundsException("index=" + index + ", size=" + size);
    }

    @Override public String toString() {
        StringBuilder sb = new StringBuilder("[");
        Node<T> n = head.next;
        while (n != tail) {
            sb.append(n.data);
            n = n.next;
            if (n != tail) sb.append(", ");
        }
        return sb.append("]").toString();
    }

    @Override public Iterator<T> iterator() {
        return new Iterator<T>() {
            Node<T> cur = head.next;
            @Override public boolean hasNext() { return cur != tail; }
            @Override public T next() {
                if (cur == tail) throw new NoSuchElementException();
                T val = cur.data; cur = cur.next; return val;
            }
        };
    }
}

/* ===========================================================
 *  Circular Singly Linked List (tail points to head)
 *  Time (avg): addFirst O(1), addLast O(1), removeFirst O(1), removeLast O(n),
 *              contains O(n), get(index) O(n)
 *  Space: O(n)
 * =========================================================== */
class CircularLinkedList<T> implements Iterable<T> {
    private static class Node<T> {
        T data; Node<T> next;
        Node(T d) { data = d; }
    }

    private Node<T> tail; // tail.next is head when non-empty
    private int size;

    public int size() { return size; }
    public boolean isEmpty() { return size == 0; }
    public void clear() { tail = null; size = 0; }

    private Node<T> head() { return (tail == null) ? null : tail.next; }

    public void addFirst(T val) {
        Node<T> n = new Node<>(val);
        if (tail == null) {
            tail = n; tail.next = tail; // self-loop
        } else {
            n.next = tail.next; // old head
            tail.next = n;      // new head
        }
        size++;
    }

    public void addLast(T val) {
        addFirst(val);
        tail = tail.next; // new node is at head; move tail to it
    }

    public T getFirst() {
        if (tail == null) throw new NoSuchElementException("List is empty");
        return tail.next.data;
    }

    public T getLast() {
        if (tail == null) throw new NoSuchElementException("List is empty");
        return tail.data;
    }

    public T removeFirst() {
        if (tail == null) throw new NoSuchElementException("List is empty");
        Node<T> head = tail.next;
        T val = head.data;
        if (head == tail) { // only one
            tail = null;
        } else {
            tail.next = head.next;
        }
        size--;
        return val;
    }

    public T removeLast() {
        if (tail == null) throw new NoSuchElementException("List is empty");
        Node<T> head = tail.next;
        if (head == tail) { // single node
            T val = tail.data; tail = null; size--; return val;
        }
        // find node before tail
        Node<T> prev = head;
        while (prev.next != tail) prev = prev.next;
        T val = tail.data;
        prev.next = tail.next; // link to head
        tail = prev;
        size--;
        return val;
    }

    public boolean contains(T value) { return indexOf(value) != -1; }

    public int indexOf(T value) {
        if (tail == null) return -1;
        Node<T> cur = tail.next; // head
        for (int i = 0; i < size; i++) {
            if ((value == null && cur.data == null) || (value != null && value.equals(cur.data))) return i;
            cur = cur.next;
        }
        return -1;
    }

    public void add(int index, T val) {
        checkPositionIndex(index);
        if (index == 0) { addFirst(val); return; }
        if (index == size) { addLast(val); return; }
        // find prev of index
        Node<T> prev = nodeAt(index - 1);
        Node<T> n = new Node<>(val);
        n.next = prev.next;
        prev.next = n;
        size++;
    }

    public T removeAt(int index) {
        checkElementIndex(index);
        if (index == 0) return removeFirst();
        Node<T> prev = nodeAt(index - 1);
        Node<T> target = prev.next;
        prev.next = target.next;
        if (target == tail) tail = prev;
        size--;
        return target.data;
    }

    public T get(int index) {
        checkElementIndex(index);
        return nodeAt(index).data;
    }

    public T set(int index, T val) {
        checkElementIndex(index);
        Node<T> n = nodeAt(index);
        T old = n.data; n.data = val; return old;
    }

    private Node<T> nodeAt(int index) {
        Node<T> cur = head();
        for (int i = 0; i < index; i++) cur = cur.next;
        return cur;
    }

    private void checkElementIndex(int index) {
        if (index < 0 || index >= size) throw new IndexOutOfBoundsException("index=" + index + ", size=" + size);
    }
    private void checkPositionIndex(int index) {
        if (index < 0 || index > size) throw new IndexOutOfBoundsException("index=" + index + ", size=" + size);
    }

    @Override public String toString() {
        StringBuilder sb = new StringBuilder("[");
        if (tail != null) {
            Node<T> cur = tail.next; // head
            for (int i = 0; i < size; i++) {
                sb.append(cur.data);
                cur = cur.next;
                if (i != size - 1) sb.append(", ");
            }
        }
        return sb.append("]").toString();
    }

    @Override public Iterator<T> iterator() {
        return new Iterator<T>() {
            int remaining = size;
            Node<T> cur = (tail == null) ? null : tail.next; // head
            @Override public boolean hasNext() { return remaining > 0; }
            @Override public T next() {
                if (remaining == 0) throw new NoSuchElementException();
                T val = cur.data;
                cur = cur.next;
                remaining--;
                return val;
            }
        };
    }
}

---

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.