// Week 10 – Doubly linked list (with Head and End pointers)
// Run: java DoublyLinkedList.java
public class DoublyLinkedList {

    static class Node {
        int value;
        Node prev, next;
        Node(int v) { value = v; }
    }

    Node head, tail; // both are null in an empty list
    int size;

    void insertFirst(int x) {          // O(1)
        Node n = new Node(x);
        n.next = head;
        if (head != null) head.prev = n;
        else tail = n;                  // the list was empty
        head = n;
        size++;
    }

    void insertLast(int x) {           // O(1) – thanks to the End pointer
        Node n = new Node(x);
        n.prev = tail;
        if (tail != null) tail.next = n;
        else head = n;
        tail = n;
        size++;
    }

    // Insertion after element p – O(1)
    void insertAfter(Node p, int x) {
        if (p == tail) {
            insertLast(x);
            return;
        }
        Node n = new Node(x);
        n.prev = p;
        n.next = p.next;
        p.next.prev = n;
        p.next = n;
        size++;
    }

    // Deleting element p – O(1): we know both neighbours!
    void remove(Node p) {
        if (p.prev != null) p.prev.next = p.next;
        else head = p.next;             // deleting the first element
        if (p.next != null) p.next.prev = p.prev;
        else tail = p.prev;             // deleting the last element
        size--;
    }

    int removeLast() {                  // O(1) – it was O(n) in a singly linked list!
        int x = tail.value;
        remove(tail);
        return x;
    }

    Node find(int x) {
        for (Node p = head; p != null; p = p.next) if (p.value == x) return p;
        return null;
    }

    String forward() {
        StringBuilder sb = new StringBuilder("[");
        for (Node p = head; p != null; p = p.next) sb.append(p.value).append(p.next != null ? " <-> " : "");
        return sb.append("]").toString();
    }

    String backward() {                 // backward traversal
        StringBuilder sb = new StringBuilder("[");
        for (Node p = tail; p != null; p = p.prev) sb.append(p.value).append(p.prev != null ? " <-> " : "");
        return sb.append("]").toString();
    }

    public static void main(String[] args) {
        DoublyLinkedList l = new DoublyLinkedList();
        l.insertLast(2);
        l.insertLast(3);
        l.insertFirst(1);
        l.insertLast(5);
        System.out.println("forward:  " + l.forward());
        System.out.println("backward: " + l.backward());
        l.insertAfter(l.find(3), 4);
        System.out.println("insertAfter(3, 4): " + l.forward());
        l.remove(l.find(3));
        System.out.println("remove(3):         " + l.forward());
        System.out.println("removeLast() = " + l.removeLast() + " -> " + l.forward() + ", size = " + l.size);

        // Java's LinkedList is a doubly linked list
        java.util.LinkedList<String> jl = new java.util.LinkedList<>(java.util.List.of("b", "c"));
        jl.addFirst("a");
        jl.addLast("d");
        System.out.println("java.util.LinkedList: " + jl + ", removeLast = " + jl.removeLast());
    }
}