## 单向循环链表 单向循环链表的尾节点的 next 指针不再是 null，而是指向链表的头节点，以形成环  ## 实现单向循环链表 相比单向链表，单向循环链表需要重写**插入**节点、**删除**节点两个方法 ### 插入节点 对于插入节点，需要特别关注插入头节点的情况，此时需要拿到尾节点，然后将其 next 指向新的头节点 ```java public void add(int index,E ele) { checkRangeForAdd(index); // 如果是向头节点插入，需要维护尾节点的 next，其他情况保持和单向链表的插入操作相同 if(index == 0) { Node newFirst = new Node<>(ele,first); // 如果插入新头节点时链表非空，正常调用 getNode() // 如果是空链表，不可调用 getNode，此时的尾节点就是要插入的新节点 Node last = size==0 ? newFirst : getNode(size-1); // 尾节点的 next 指向新的头节点 last.next = newFirst; first = newFirst; }else { // 对于尾节点的插入自动维护了 next Node prev = getNode(index-1); prev.next = new Node<>(ele,prev.next); } size++; } ``` ### 删除节点 如果删除的是头节点，删除后需让last指向新的头节点。 当只有一个节点并删除时, first指向null。 ```java public E remove(int index) { checkRange(index); Node 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 prev = getNode(index-1); node = prev.next; prev.next = node.next; } size--; return node.element; } ``` ## 双向循环链表 双向循环链表的头节点的 prev 不再是 null，而是指向尾节点 双向循环链表的尾节点的 next 不再是 null，而是指向头节点  ## 实现双向循环链表 相比双向链表，双向循环链表需要重写**插入**节点、**删除**节点两个方法 ### 插入节点 插入节点需要对添加**第一个节点**和添加**尾节点**进行特殊处理 ```java // 添加元素 public void add(int index,E ele) { checkRangeForAdd(index); // 向链表尾部添加元素 if(index==size) { // 取出原最后一个节点 Node 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 next = getNode(index); // 原来位置的节点的前驱作为新节点的前驱 Node prev = next.prev; // 创建新节点 Node 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 * 链表只有一个节点时同样需要特殊处理 ```java // 删除元素 public E remove(int index) { checkRange(index); // 获取要删除的节点 Node node = getNode(index); // 如果链表只有一个节点，其前驱和后继都是自己本身，重新设置不会断掉引用 if(size==1) { first = null; last = null; // 链表不只一个节点 }else { Node prev = node.prev; Node 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; } ``` ## 参考 * [恋上数据结构与算法（第一季）](https://ke.qq.com/course/385223) * [小码哥《恋上数据结构与算法》笔记（四）：循环链表](https://juejin.im/post/5dfad5936fb9a0160b6381df)