Doubly Linked-List Examples:

Java
Java
Python
Python
PHP
PHP
C#
C#
C++
C++
TypeScript
TypeScript
▸ Doubly Linked-List Quick Review

Doubly-Linked-List in Java

import java.util.*;

public class DoublyLinkedList<T> implements Iterable<T>{

// Doubly linked node class.
private static class Node<T> {
    public T value;
    public Node<T> next;
    public Node<T> prev;
    
    public Node(T value, Node<T> next, Node<T> previous) {
        this.value = value;
        this.next = next;
        this.prev = previous;
    }
}

// The head (first) node of the linked list.
private Node<T> head;
// The tail (last) node of the linked list.
private Node<T> tail;
// The size of the linked list.
private int size;

public DoublyLinkedList() {
    head = null;
    tail = null;
    size = 0;
}

public boolean isEmpty() {
    return size <= 0;
}

public int size() {
    return size;
}

public boolean contains(T value) {
    if(isEmpty()) {
        return false;
    }
    Node<T> tmp = head;
    while(tmp != null) {
        if(tmp.value.equals(value)) {
            return true;
        }
        tmp = tmp.next;
    }
    return false;
}

public T get(int index) {
    // Ensure the index is within limits.
    if(index > size || isEmpty()) {
        throw new IndexOutOfBoundsException();
    }
    // Neat trick: worst case can be half the size of the list by storing size.
    if(index > size / 2) {
        index = (size - 1) - index;
        Node<T> tmp = tail;
        while(index > 0) {
            tmp = tmp.prev;
            index--;
        }
        return tmp.value;
    }
    else {
        Node<T> tmp = head;
        while(index > 0) {
            tmp = tmp.next;
            index--;
        }
        return tmp.value;
    }
    
}

public T getFirst() {
    if(head != null) {
        return head.value;
    }
    return null;
}

public T getLast() {
    if(tail != null) {
        return tail.value;
    }
    return null;
}

public void addLast(T value) {
    // In the empty case, assign head and tail.
    if(isEmpty()) {
        Node<T> tmp = new Node<T>(value, null, null);
        head = tmp;
        tail = tmp;
        size++;
        return;
    }
    Node<T> tmp = tail;
    tmp.next = new Node<T>(value, null, tmp);
    tail = tmp.next;
    size++;
}

public void addFirst(T value) {
    // head and tail check
    if(isEmpty()) {
        Node<T> tmp = new Node<T>(value, null, null);
        head = tmp;
        tail = tmp;
        size++;
        return;
    }
    Node<T> tmp = head;
    tmp.prev  = new Node<T>(value, tmp, null);
    head = tmp;
    size++;
}

public void addAfter(T key, T toAdd) {
    if(isEmpty()) {
        throw new NoSuchElementException();
    }
    Node<T> tmp = head;
    while(tmp != null) {
        if(tmp.value.equals(key)) {
            Node<T> newNode = new Node<T>(toAdd, tmp.next, tmp);
            tmp.next = newNode;
            // Contrived looking, but necessary. 
            if(newNode.next != null) newNode.next.prev = newNode;
            else tail = newNode;
            size++;
            return;
        }
        tmp = tmp.next;
    }
    // End of list iterated: element DNE.
    throw new NoSuchElementException();
    
}

public void addBefore(T key, T toAdd) {
    if(isEmpty()) {
        throw new NoSuchElementException();
    }
    Node<T> tmp = head;
    while(tmp != null) {
        if(tmp.value.equals(key)) {
            Node<T> newNode = new Node<T>(toAdd, tmp, tmp.prev);
            tmp.prev = newNode;
            if(newNode.prev != null) {
                newNode.prev.next = newNode;
                
            } else {
                head = tmp;
            }
            
            size++;
            return;
        }
        tmp = tmp.next;
    }
    
    throw new NoSuchElementException();
    
}

public void remove(T value) {
    if(isEmpty()) {
        return;
    }
    Node<T> tmp = head;
    while(tmp != null) {
        if(tmp.value.equals(value)) {
            if(tmp.prev != null) tmp.prev.next = tmp.next;
            else head = tmp.next;
            if(tmp.next != null) tmp.next.prev = tmp.prev;
            else tail = tmp.prev;
            size--;
            return;
        }
        tmp = tmp.next;
    }
    return;
}

public void removeFirst() {
    if(isEmpty()) {
        return;
    }
    if(size == 1) {
        head = null;
        tail = null;
        size--;
        return;
    }
    head = head.next;
    head.prev = null;
    size--;
}

public void removeLast() {
    if(isEmpty()) {
        return;
    }
    if(size == 1) {
        head = null;
        tail = null;
        size--;
        return;
    }
    tail = tail.prev;
    tail.next = null;
    size--;
}

public int indexOf(T value) {
    int index = 0;
    Node<T> tmp = head;
    while(tmp != null) {
        if(tmp.value.equals(value)) {
            return index;
        }
        tmp = tmp.next;
        index++;
    }
    return -1;
}

public void clear() {
    this.size = 0;
    this.head = null;
    this.tail = null;
}

public String toString() {
    String res = "{";
    // Define a temporary node.
    Node<T> tmp = head;
    // Iterate the linked list.
    while(tmp != null) {
        // Append the string representation of the node value, comma separated.
        res += tmp.value.toString();
        if(tmp.next != null) res += ", ";
        tmp = tmp.next;
    }
    res += "}";
    return res;
}


public static void main(String[] args) {
    DoublyLinkedList<Integer> ll = new DoublyLinkedList<Integer>();
    ll.addFirst(1);
    ll.removeFirst();
    ll.addFirst(1);
    ll.addLast(2);
    ll.addLast(3);
    int index = ll.indexOf(3);
    System.out.println(ll.get(index));
    System.out.println("LinkedList = " + ll.toString());
    ll.clear();
    System.out.println("LinkedList = " + ll.toString());
}

@Override
public Iterator<T> iterator() {
      return new ListIterator();
   }

  private class ListIterator  implements Iterator<T> {
     private Node<T> tokenNode;

     public ListIterator() {
         tokenNode = head;
     }

     public boolean hasNext() {
        return tokenNode != null;
     }

     public T next() {
        if (!hasNext()) throw new NoSuchElementException();
        T res = tokenNode.value;
        tokenNode = tokenNode.next;
        return res;
     }

     public void remove() { 
         throw new UnsupportedOperationException(); 
     }
  }

}

Find any bugs in the code? let us know!