datastructures2DoublyLinkedList

1package pkg3datastructures;2 3/*4 * datastructures2DoublyLinkedList.java5 * ---------------------6 * Each node has prev + next pointers, enabling O(1) insert/remove at both ends7 * and backward traversal.8 *9 * COMPLEXITY: addFirst/addLast/removeFirst/removeLast O(1); search O(n).10 * WHEN TO USE: deques, LRU caches, when you need bidirectional traversal.11 */12public class datastructures2DoublyLinkedList {13 14    static class Node {15        int val; Node prev, next;16        Node(int val) { this.val = val; }17    }18 19    private Node head, tail;20    private int size;21 22    void addFirst(int v) {23        Node n = new Node(v);24        if (head == null) { head = tail = n; }25        else { n.next = head; head.prev = n; head = n; }26        size++;27    }28 29    void addLast(int v) {30        Node n = new Node(v);31        if (tail == null) { head = tail = n; }32        else { n.prev = tail; tail.next = n; tail = n; }33        size++;34    }35 36    Integer removeFirst() {37        if (head == null) return null;38        int v = head.val;39        head = head.next;40        if (head == null) tail = null; else head.prev = null;41        size--; return v;42    }43 44    Integer removeLast() {45        if (tail == null) return null;46        int v = tail.val;47        tail = tail.prev;48        if (tail == null) head = null; else tail.next = null;49        size--; return v;50    }51 52    String forward() {53        StringBuilder sb = new StringBuilder("[");54        for (Node c = head; c != null; c = c.next) sb.append(c.val).append(c.next != null ? " <-> " : "");55        return sb.append("]").toString();56    }57 58    String backward() {59        StringBuilder sb = new StringBuilder("[");60        for (Node c = tail; c != null; c = c.prev) sb.append(c.val).append(c.prev != null ? " <-> " : "");61        return sb.append("]").toString();62    }63 64    public static void main(String[] args) {65        datastructures2DoublyLinkedList dll = new datastructures2DoublyLinkedList();66        dll.addLast(2); dll.addLast(3); dll.addFirst(1); dll.addLast(4);67        System.out.println("forward:  " + dll.forward() + " size=" + dll.size);68        System.out.println("backward: " + dll.backward());69        System.out.println("removeFirst=" + dll.removeFirst() + " removeLast=" + dll.removeLast());70        System.out.println("after removals: " + dll.forward());71    }72}