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();
}
}
