[Java] Doubly Linked List

Reference: https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html

The time complexity of remove() method of java.util.LinkedList is O(n) because Java standard LinkedList class does not expose the internal Node details for clients.

Therefore, we implement a custom DoublyLinkedList class for competitive programming. In this implementation, both time complexity of add() and of remove() are O(1).

    
    public class DoublyLinkedList<V> {
        private int size;
        private Node<V> head;
        private Node<V> tail;

        public DoublyLinkedList() {
            this.size = 0;
            this.head = new Node<V>();
            this.tail = new Node<V>();
            this.head.next = this.tail;
            this.tail.prev = this.head;
        }
        
        public void addFirst(Node<V> node) {
            this.size++;
            node.next = this.head.next;
            node.next.prev = node;
            node.prev = this.head;
            node.prev.next = node;
        }
        
        public void addLast(Node<V> node) {
            this.size++;
            node.prev = this.tail.prev;
            node.prev.next = node;
            node.next = this.tail;
            node.next.prev = node;
        }
        
        public void remove(Node<V> node) {
            if (node.prev != null && node.next != null) {
                this.size--;
                node.next.prev = node.prev;
                node.prev.next = node.next;
                node.prev = node.next = null;
            }
        }
        
        public Node<V> getFirst() {
            return isEmpty() ? null : this.head.next;
        }

        public Node<V> getLast() {
            return isEmpty() ? null : this.tail.prev;
        }
        
        public int size() {
            return this.size;    
        }
        
        public boolean isEmpty() {
            return this.size == 0;
        }
        
        @Override
        public String toString() {
            StringBuilder builder = new StringBuilder();
            Node<V> curr = this.head.next;
            while (curr != this.tail) {
                builder.append(curr.getValue());
                builder.append(" -> ");
                curr = curr.next;
            }
            builder.append("END \n");
            return builder.toString();
        }
    }

    public class Node<V> {
        private V value;
        private Node prev;
        private Node next;

        public Node(V value) {
            this.value = value;
        }

        public Node() {
            this.value = null;
        }
        
        public V getValue() {
            return this.value;
        }
        
        @Override
        public String toString() {
            return this.value == null ? null : this.value.toString();
        }
    }