【6】单向循环链表
- 1、单向循环链表
- 2、add(int index, E element)
- 3、删除
1、单向循环链表
🖊 在单向链表的基础上,尾节点的 next
指向头节点
2、add(int index, E element)
🖊 往尾部添加的代码不用修改(和单向链表一样的)
🖊 往头节点位置添加元素的时候,要用尾节点的 next
指向新的头节点
/**
* 往索引位置添加元素
*/
@Override
public void add(int index, E element) {
checkIndex4Add(index);
if (index == 0) { // 添加元素到头节点的位置
// 创建新节点
Node<E> newFirst = new Node<>(element, first);
// 获取到【尾】节点
// 如果size==0: 新添加的头节点就是尾节点
Node<E> tail = (size == 0) ? newFirst : node(size - 1);
// 尾节点的next指向新的头节点
tail.next = newFirst;
first = newFirst;
} else {
Node<E> prev = node(index - 1);
prev.next = new Node<>(element, prev.next);
}
size++;
}
3、删除
🖊 删除尾节点依然不用考虑
🖊 删除头节点的时候,要修改尾节点的 next
指针的指向
/**
* 删除索引位置的元素
*
* @return 被删除的元素
*/
@Override
public E remove(int index) {
checkIndex(index);
Node<E> node = first;
if (index == 0) { // 删除头节点
if (size == 1) { // 只有一个节点
first = null;
} else {
// 获取到尾节点
Node<E> tail = node(size - 1);
first = first.next;
// 尾节点的next指向新的头节点
tail.next = first;
}
} else {
Node<E> prev = node(index - 1);
node = prev.next;
prev.next = node.next;
}
size--;
return node.element;
}
🖊 删除的时候,要考虑只有一个节点的时候的情况
🍀 单向循环链表完整代码