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