1. 内容大纲
本章节的代码：https://github.com/wicksonZhang/data-structure/tree/main/2-LinkedList/src/main/java/com/wickson/linkedlist/cycle
2. 基础知识
2.1. 循环链表是什么
循环链表也是在链表的基础上面发展出来的，核心就是将最后一个节点指向第一个节点，形成一个闭环。
2.2. 循环链表优缺点
优点
- 循环遍历： 由于循环链表形成了一个闭环，可以更方便地循环遍历整个链表。
- 插入和删除操作： 在循环链表中，插入和删除节点可能比常规链表更简单高效，因为不需要考虑头尾节点的特殊情况。
- 空间效率： 循环链表可能在某些情况下节省一些内存。
缺点
- 代码复杂度上升： 循环链表的插入和删除导致了代码的复杂性，需要考虑的点会更加复杂。
- 难以确定结束点： 在循环链表中，由于没有明确的结束节点，确定遍历何时结束可能需要额外的逻辑。
2.3. 生活中的例子
- 日历系统： 周期性地循环，一年中的日子按照月份和星期循环。
- 生态系统中的食物链： 生物之间的食物链循环，猎物被捕食者捕食，形成一个循环。
- 天气季节： 春夏秋冬的循环，每一年都以相似的方式重复。
3. 单项循环链表-代码实现
如下图情况就是一个简单的单项循环链表。
单向循环链表是基于单向链表进行开发，所以唯一不同的点只有 add(int index, E element) 和 remove(int index) 这两个方法。
3.1. 添加元素到指定位置
注意：单向循环链表添加元素需要考虑的点比较多，具体需要注意一下三种情况：
- 往中间或者最后一个位置添加元素
- 往首节点添加元素
- 当只有一个元素的情况
case1：往中间或者最后一个位置添加元素
1
2
3
4
5
6
7
8
9
10
| @Override
public void add(int index, E element) {
rangeAddChecked(index);
Node<E> prevNode = node(index - 1);
prevNode.next = new Node<>(element, prevNode.next);
size++;
}
|
case2：往首节点添加元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| @Override
public void add(int index, E element) {
rangeAddChecked(index);
if (index == 0) {
Node<E> node = new Node<>(element, first);
first = node;
Node<E> lastNode = node(size - 1);
lastNode.next = node;
} else {
Node<E> prevNode = node(index - 1);
prevNode.next = new Node<>(element, prevNode.next);
}
size++;
}
|
case3：当只有一个元素的情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| @Override
public void add(int index, E element) {
rangeAddChecked(index);
if (index == 0) {
Node<E> node = new Node<>(element, first);
first = node;
if (size == 0) {
node.next = node;
} else {
Node<E> lastNode = node(size - 1);
lastNode.next = node;
}
} else {
Node<E> prevNode = node(index - 1);
prevNode.next = new Node<>(element, prevNode.next);
}
size++;
}
|
3.2. 删除指定元素
与上面的思路保持一致，需要注意一下三种情况：
- 删除中间或者最后一个位置元素
- 删除首节点元素
- 当只有一个节点元素
case1：删除中间或者最后一个位置元素
1
2
3
4
5
6
7
8
9
| public E remove(int index) {
rangeChecked(index);
Node<E> prevNode = node(index - 1);
Node<E> removeNode = prevNode.next;
prevNode.next = removeNode.next;
size--;
return removeNode.element;
}
|
case2：删除首节点元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public E remove(int index) {
rangeChecked(index);
Node<E> node = first;
if (index == 0) {
first = node.next;
Node<E> lastNode = node(size - 1);
lastNode.next = first;
} else {
Node<E> prevNode = node(index - 1);
Node<E> removeNode = prevNode.next;
prevNode.next = removeNode.next;
return removeNode.element;
}
size--;
return node.element;
}
|
case3：当只有一个节点元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| public E remove(int index) {
rangeChecked(index);
Node<E> node = first;
if (index == 0) {
if (size == 1) {
first = null;
} else {
first = node.next;
Node<E> lastNode = node(size - 1);
lastNode.next = first;
}
} else {
Node<E> prevNode = node(index - 1);
Node<E> removeNode = prevNode.next;
prevNode.next = removeNode.next;
size--;
return removeNode.element;
}
size--;
return node.element;
}
|
3.3. 单元测试
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public class SingleCycleLinkedListTest {
@Test
public void testAddRemoveElements() {
SingleCycleLinkedList<Integer> list = new SingleCycleLinkedList<>();
list.add(0, 10);
list.add(1, 20);
list.add(2, 30);
assertEquals(Integer.valueOf(20), list.remove(1));
assertEquals(2, list.size());
assertEquals(Integer.valueOf(30), list.get(1));
assertEquals(Integer.valueOf(10), list.remove(0));
assertEquals(1, list.size());
assertEquals(Integer.valueOf(30), list.get(0));
}
}
|
4. 双向循环链表-代码实现
如下是双向循环链表的示例图。
双向循环链表是基于双向链表进行开发，所以唯一不同的点只有 add(int index, E element) 和 remove(int index) 这两个方法。
4.1. 添加元素到指定位置
注意：双向循环链表添加元素需要考虑的点比较多，具体需要注意一下三种情况：
- 往中间或者最后一个位置添加元素
- 往尾节点添加元素
- 当只有一个元素的情况
- index = 0，size = 1
case1：往中间位置添加元素
1
2
3
4
5
6
7
8
9
10
11
| @Override
public void add(int index, E element) {
rangeAddChecked(index);
Node<E> nextNode = node(index);
Node<E> prevNode = nextNode.prev;
Node<E> node = new Node<>(prevNode, element, nextNode);
prevNode.next = node;
nextNode.prev = node;
size++;
}
|
case2：往尾节点添加元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| @Override
public void add(int index, E element) {
rangeAddChecked(index);
if (index == size) {
Node<E> lastNode = last;
last = new Node<>(lastNode, element, first);
lastNode.next = last;
first.prev = last;
} else {
Node<E> nextNode = node(index);
Node<E> prevNode = nextNode.prev;
Node<E> node = new Node<>(prevNode, element, nextNode);
prevNode.next = node;
nextNode.prev = node;
}
size++;
}
|
case3：当只有一个元素的情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| @Override
public void add(int index, E element) {
rangeAddChecked(index);
if (index == size) {
Node<E> lastNode = last;
last = new Node<>(lastNode, element, first);
if (lastNode == null) {
first = last;
first.prev = first;
first.next = first;
} else {
lastNode.next = last;
first.prev = last;
}
} else {
Node<E> nextNode = node(index);
Node<E> prevNode = nextNode.prev;
Node<E> node = new Node<>(prevNode, element, nextNode);
prevNode.next = node;
nextNode.prev = node;
}
size++;
}
|
case4：index = 0，size = 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| @Override
public void add(int index, E element) {
rangeAddChecked(index);
if (index == size) {
Node<E> lastNode = last;
last = new Node<>(lastNode, element, first);
if (lastNode == null) {
first = last;
first.prev = first;
first.next = first;
} else {
lastNode.next = last;
first.prev = last;
}
} else {
Node<E> nextNode = node(index);
Node<E> prevNode = nextNode.prev;
Node<E> node = new Node<>(prevNode, element, nextNode);
prevNode.next = node;
nextNode.prev = node;
if (nextNode == last) {
last = node;
}
}
size++;
}
|
4.2. 删除指定元素
与上面的思路保持一致，需要注意一下三种情况：
- 删除中间元素
- 当 size == 1 的情况
- 当只有一个节点元素
- index = 0, size = 2
case1：删除中间元素
1
2
3
4
5
6
7
8
9
10
11
12
| @Override
public E remove(int index) {
rangeChecked(index);
Node<E> node = node(index);
Node<E> prevNode = node.prev;
Node<E> nextNode = node.next;
prevNode.next = nextNode;
nextNode.prev = prevNode;
size--;
return node.element;
}
|
case2：当 size == 1 的情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| @Override
public E remove(int index) {
rangeChecked(index);
Node<E> node = first;
if (size == 1) {
first = null;
last = null;
} else {
node = node(index);
Node<E> prevNode = node.prev;
Node<E> nextNode = node.next;
prevNode.next = nextNode;
nextNode.prev = prevNode;
}
size--;
return node.element;
}
|
case3：index = 0, size = 2；
case4：index = 1，size = 2；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| @Override
public E remove(int index) {
rangeChecked(index);
Node<E> node = first;
if (size == 1) {
first = null;
last = null;
} else {
node = node(index);
Node<E> prevNode = node.prev;
Node<E> nextNode = node.next;
prevNode.next = nextNode;
nextNode.prev = prevNode;
if (node == first) {
first = nextNode;
}
if (node == last) {
last = prevNode;
}
}
size--;
return node.element;
}
|
4.3. 单元测试
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| public class CycleLinkedListTest {
@Test
public void testAddAndGetElement() {
CycleLinkedList<Integer> list = new CycleLinkedList<>();
assertTrue(list.isEmpty());
assertEquals(0, list.size());
list.add(0, 10);
assertEquals(1, list.size());
assertEquals(Integer.valueOf(10), list.get(0));
list.add(1, 20);
assertEquals(2, list.size());
assertEquals(Integer.valueOf(20), list.get(1));
}
@Test
public void testRemoveElement() {
CycleLinkedList<Character> list = new CycleLinkedList<>();
list.add(0, 'a');
list.add(1, 'b');
list.add(2, 'c');
assertEquals(Character.valueOf('b'), list.remove(1));
assertEquals(2, list.size());
assertEquals(Character.valueOf('c'), list.get(1));
}
}
|
5. 参考博文
wechat
alipay
