双向链表

双向链表，又称为双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

public class DoublyLinkedList<E> {



  private static class Node<E> {


    private E element;


    private Node<E> prev;


    private Node<E> next;


    public Node(E e, Node<E> p, Node<E> n) {
      element = e;
      prev = p;
      next = n;
    }



    public E getElement() { return element; }


    public Node<E> getPrev() { return prev; }


    public Node<E> getNext() { return next; }



    public void setPrev(Node<E> p) { prev = p; }


    public void setNext(Node<E> n) { next = n; }
  }



  private Node<E> header;


  private Node<E> trailer;


  private int size = 0;


  public DoublyLinkedList() {
    header = new Node<>(null, null, null);
    trailer = new Node<>(null, header, null);
    header.setNext(trailer);
  }



  public int size() { return size; }


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


  public E first() {
    if (isEmpty()) return null;
    return header.getNext().getElement();
  }


  public E last() {
    if (isEmpty()) return null;
    return trailer.getPrev().getElement();
  }



  public void addFirst(E e) {
    addBetween(e, header, header.getNext());
  }


  public void addLast(E e) {
    addBetween(e, trailer.getPrev(), trailer);
  }


  public E removeFirst() {
    if (isEmpty()) return null;
    return remove(header.getNext());
  }


  public E removeLast() {
    if (isEmpty()) return null;
    return remove(trailer.getPrev());
  }



  private void addBetween(E e, Node<E> predecessor, Node<E> successor) {

    Node<E> newest = new Node<>(e, predecessor, successor);
    predecessor.setNext(newest);
    successor.setPrev(newest);
    size++;
  }


  private E remove(Node<E> node) {
    Node<E> predecessor = node.getPrev();
    Node<E> successor = node.getNext();
    predecessor.setNext(successor);
    successor.setPrev(predecessor);
    size--;
    return node.getElement();
  }


  public String toString() {
    StringBuilder sb = new StringBuilder("(");
    Node<E> walk = header.getNext();
    while (walk != trailer) {
      sb.append(walk.getElement());
      walk = walk.getNext();
      if (walk != trailer)
        sb.append(", ");
    }
    sb.append(")");
    return sb.toString();
  }
}