## 单向循环链表
单向循环链表的尾节点的 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)

数据结构 | 循环链表 CircleLinkedList