单向循环链表

循环链表是一种链式存储结构，它的最后一个结点指向头结点，形成一个环。因此，从循环链表中的任何一个结点出发都能找到任何其他结点。循环链表的操作和单链表的操作基本一致，差别仅仅在于算法中的循环条件有所不同。

public class CircularlyLinkedList<E> {


  private static class Node<E> {


    private E element;


    private Node<E> next;


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



    public E getElement() { return element; }


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



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



  private Node<E> tail = null;


  private int size = 0;


  public CircularlyLinkedList() { }



  public int size() { return size; }


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


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


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



  public void rotate() {
    if (tail != null)
      tail = tail.getNext();
  }


  public void addFirst(E e) {
    if (size == 0) {
      tail = new Node<>(e, null);
      tail.setNext(tail);
    } else {
      Node<E> newest = new Node<>(e, tail.getNext());
      tail.setNext(newest);
    }
    size++;
  }


  public void addLast(E e) {
    addFirst(e);
    tail = tail.getNext();
  }


  public E removeFirst() {
    if (isEmpty()) return null;
    Node<E> head = tail.getNext();
    if (head == tail) tail = null;
    else tail.setNext(head.getNext());
    size--;
    return head.getElement();
  }


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