单向循环链表

单向循环链表的尾节点的 next 指针不再是 null，而是指向链表的头节点，以形成环

实现单向循环链表

相比单向链表，单向循环链表需要重写插入节点、删除节点两个方法

插入节点

对于插入节点，需要特别关注插入头节点的情况，此时需要拿到尾节点，然后将其 next 指向新的头节点

public void add(int index,E ele) {
    checkRangeForAdd(index);
    // 如果是向头节点插入，需要维护尾节点的 next，其他情况保持和单向链表的插入操作相同
    if(index == 0) {
        Node<E> newFirst = new Node<>(ele,first);
        // 如果插入新头节点时链表非空，正常调用 getNode()
        // 如果是空链表，不可调用 getNode，此时的尾节点就是要插入的新节点
        Node<E> last = size==0 ? newFirst : getNode(size-1);
        // 尾节点的 next 指向新的头节点
        last.next = newFirst;
        first = newFirst;
    }else {
        // 对于尾节点的插入自动维护了 next
        Node<E> prev = getNode(index-1);
        prev.next = new Node<>(ele,prev.next);
    }
    size++;
}

删除节点

如果删除的是头节点，删除后需让last指向新的头节点。
当只有一个节点并删除时, first指向null。

public E remove(int index) {
    checkRange(index);
    Node<E> node;
    if(index == 0) {
        // 取出头节点
        node = first;
        if(size==1) {
            // 如果链表只有一个元素，直接置空first指针即可
            first = null;
        }else {
            // 如果链表不知一个元素，要拿到尾节点
            // 注意：因为getNode()方法是从first位置开始向后遍历的，所以不能先修改first的值
            getNode(size-1).next = first.next;
            first = first.next;
        }
    }else {
        Node<E> prev = getNode(index-1);
        node = prev.next;
        prev.next = node.next;
    }
    size--;
    return node.element;
}

双向循环链表

双向循环链表的头节点的 prev 不再是 null，而是指向尾节点
双向循环链表的尾节点的 next 不再是 null，而是指向头节点

实现双向循环链表

相比双向链表，双向循环链表需要重写插入节点、删除节点两个方法

插入节点

插入节点需要对添加第一个节点和添加尾节点进行特殊处理

// 添加元素
public void add(int index,E ele) {
    checkRangeForAdd(index);
    // 向链表尾部添加元素
    if(index==size) {
        // 取出原最后一个节点
        Node<E> oldLast = last;
        // 新的last的next不再是null，而是指向first
        last = new Node<>(oldLast,ele,first);
        // 如果原链表是空的，即要添加的元素是第一个元素
        if(oldLast==null) {
            last.next = last;
            last.prev = last;
            first = last;
        }else {
            oldLast.next = last;
            first.prev = last;
        }
    // 向链表其他位置添加元素
    }else {
        // 原来位置的节点作为后继
        Node<E> next = getNode(index);
        // 原来位置的节点的前驱作为新节点的前驱
        Node<E> prev = next.prev;
        // 创建新节点
        Node<E> node = new Node<>(prev,ele,next);
        // 非空循环链表，节点的next一定不为空
        next.prev = node;
        // 非空循环链表，节点的prev一定不为空
        prev.next = node;
        // 如果插入到第一个位置，也就是说 index==0
        // 即要插入节点next是之前的first，插入后要修改新的first
        if(next==first) {
            first = node;
        }
    }
    size ++;
}

删除节点

• 删除节点，就是在环上去掉某一个节点，然后根据删除的节点是头节点或者尾节点来处理first 和 last
• 链表只有一个节点时同样需要特殊处理

  // 删除元素
  public E remove(int index) {
      checkRange(index);
      // 获取要删除的节点
      Node<E> node = getNode(index);
      // 如果链表只有一个节点，其前驱和后继都是自己本身，重新设置不会断掉引用
      if(size==1) {
          first = null;
          last = null;
      // 链表不只一个节点
      }else {
          Node<E> prev = node.prev;
          Node<E> next = node.next;
          prev.next = next;
          next.prev = prev;
          // 如果删除的是头尾节点，还需要维护first或者last
          if(node == first) {
              first = next;
          }
          if(node == last) {
              last = prev;
          }
      }
      size --;
      return node.element;
  }

参考

• 恋上数据结构与算法（第一季）
• 小码哥《恋上数据结构与算法》笔记（四）：循环链表