第三章 链表（Linked List）

算法演示地址

动态数组有个明显的缺点：

• 可能会造成内存空间的大量浪费。

能否用到多少就申请多少内存呢？

• 链表可以办到

链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的

链表的设计

链表的接口设计

由于链表的大部分接口和动态数组一致，我们抽取出一个共同的 List 接口

package cn.xx.java;/*** @author xiexu* @create 2021-07-13 9:59 上午*/
public interface List<E> {static final int ELEMENT_NOT_FOUND = -1;/*** 清除所有元素*/void clear();/*** 元素的数量** @return*/int size();/*** 是否为空** @return*/boolean isEmpty();/*** 是否包含某个元素** @param element* @return*/boolean contains(E element);/*** 添加元素到尾部** @param element*/void add(E element);/*** 获取index位置的元素** @param index* @return*/E get(int index);/*** 设置index位置的元素** @param index* @param element* @return 原来的元素ֵ*/E set(int index, E element);/*** 在index位置插入一个元素** @param index* @param element*/void add(int index, E element);/*** 删除index位置的元素** @param index* @return*/E remove(int index);/*** 查看元素的索引** @param element* @return*/int indexOf(E element);
}

再将一些通用的字段与方法放到一个抽象类中，无论是动态数组还是链表都只需要继承这个抽象类即可

package cn.xx.java;/*** @author xiexu* @create 2021-07-13 10:08 上午*/
public abstract class AbstractList<E> implements List<E> {protected int size; //元素的数量/*** 元素的数量** @return*/public int size() {return size;}/*** 是否为空** @return*/public boolean isEmpty() {return size == 0;}/*** 是否包含某个元素** @return*/public boolean contains(E element) {return indexOf(element) != ELEMENT_NOT_FOUND;}/*** 添加元素到尾部** @param element*/public void add(E element) {add(size, element);}//抛出异常protected void outOfBounds(int index) {throw new IndexOutOfBoundsException("Index：" + index + ", Size：" + size);}/*** 检查范围** @param index*/protected void rangeCheck(int index) {if (index < 0 || index >= size) {outOfBounds(index);}}/*** 检查添加到指定位置元素的范围** @param index*/protected void rangeCheckForAdd(int index) {if (index < 0 || index > size) {outOfBounds(index);}}}

单向链表（SingleLinkedList）

单向链表的结构如下图所示：

public class SingleLinkedList<E> extends AbstractList<E> {private Node<E> first;//Node内部类private static class Node<E> {E element; //节点元素Node<E> next; //节点指向下一个节点public Node(E element, Node<E> next) {this.element = element;this.next = next;}}}

清空元素 – clear( )

next 不需要设置为 null，因为 first 指向了 null，后面的 Node 没有被指向，在 Java 中会自动被垃圾回收。

@Override
public void clear() {size = 0;first = null;
}
1014

添加元素 – add(int index, E element)

添加元素尤其要注意 0 位置，给空链表添加第一个节点是个特殊情况

@Override
public void add(int index, E element) {rangeCheckForAdd(index);if (index == 0) { //在链表头部进行插入Node<E> newNode = new Node<>(element, first);first = newNode;} else { //在链表中间或者尾部进行插入Node<E> prev = node(index - 1); //获取上一个节点Node<E> newNode = new Node<>(element, prev.next);prev.next = newNode;}size++;
}

删除元素 – remove(int index)

@Override
public E remove(int index) {rangeCheck(index);Node<E> node = first;if (index == 0) { //删除0位置的元素first = first.next;} else {Node<E> prev = node(index - 1); //获取上一个节点node = prev.next;prev.next = node.next;}size--;return node.element;
}

查看元素的索引 - indexOf(E element)

/*** 查看元素的索引** @param element* @return*/
@Override
public int indexOf(E element) {Node<E> node = first;//null值的判断if (element == null) {for (int i = 0; i < size; i++) {if (node.element == null) {return i;}node = node.next;}} else {for (int i = 0; i < size; i++) {if (element.equals(node.element)) {return i;}node = node.next;}}return ELEMENT_NOT_FOUND; //找不到就返回-1
}

单向链表完整源码

package cn.xx.java.single;import cn.xx.java.AbstractList;/*** @author xiexu* @create 2021-07-13 9:52 上午*/
public class SingleLinkedList<E> extends AbstractList<E> {private Node<E> first;@Overridepublic void clear() {size = 0;first = null;}@Overridepublic E get(int index) {/*** 最好：O(1)* 最坏：O(n)* 平均：O(n)*/return node(index).element;}@Overridepublic E set(int index, E element) {/*** 最好：O(1)* 最坏：O(n)* 平均：O(n)*/Node<E> node = node(index);E old = node.element;node.element = element;return old;}@Overridepublic void add(int index, E element) {/*** 最好：O(1)* 最坏：O(n)* 平均：O(n)*/rangeCheckForAdd(index);if (index == 0) {Node<E> newNode = new Node<>(element, first);first = newNode;} else {Node<E> prev = node(index - 1); //获取上一个节点Node<E> newNode = new Node<>(element, prev.next);prev.next = newNode;}size++;}@Overridepublic E remove(int index) {/*** 最好：O(1)* 最坏：O(n)* 平均：O(n)*/rangeCheck(index);Node<E> node = first;if (index == 0) { //删除0位置的元素first = first.next;} else {Node<E> prev = node(index - 1); //获取上一个节点node = prev.next;prev.next = node.next;}size--;return node.element;}/*** 查看元素的索引** @param element* @return*/@Overridepublic int indexOf(E element) {Node<E> node = first;//null值的判断if (element == null) {for (int i = 0; i < size; i++) {if (node.element == null) {return i;}node = node.next;}} else {for (int i = 0; i < size; i++) {if (element.equals(node.element)) {return i;}node = node.next;}}return ELEMENT_NOT_FOUND; //找不到就返回-1}/*** 获取index位置对应的结点** @param index* @return*/private Node<E> node(int index) {rangeCheck(index);Node<E> node = first;for (int i = 0; i < index; i++) {node = node.next;}return node;}//Node内部类private static class Node<E> {E element;Node<E> next;public Node(E element, Node<E> next) {this.element = element;this.next = next;}}@Overridepublic String toString() {StringBuilder string = new StringBuilder();string.append("size = ").append(size).append(", [");Node<E> node = first;for (int i = 0; i < size; i++) {if (i != 0) {string.append(", ");}string.append(node.element);node = node.next;}string.append("]");return string.toString();}
}

练习题

练习 - 删除链表中的节点

LeetCode 237_删除链表中的节点：https://leetcode-cn.com/problems/delete-node-in-a-linked-list/

package 链表;/*** https://leetcode-cn.com/problems/delete-node-in-a-linked-list/** @author xiexu* @create 2021-07-14 8:59 下午*/
public class _237_删除链表中的节点 {public class ListNode {int val;ListNode next;ListNode(int x) {val = x;}}public void deleteNode(ListNode node) {node.val = node.next.val;node.next = node.next.next;}
}

练习 - 反转链表

LeetCode 206_反转链表：https://leetcode-cn.com/problems/reverse-linked-list/

递归解法

package 链表;/*** https://leetcode-cn.com/problems/reverse-linked-list/** @author xiexu* @create 2021-07-14 9:09 下午*/
public class _206_反转链表 {//递归解法public ListNode reverseList(ListNode head) {if (head == null || head.next == null) {return head;}ListNode newHead = reverseList(head.next);head.next.next = head;head.next = null;return newHead;}
}

package 链表;/*** @author xiexu* @create 2021-07-14 9:10 下午*/
public class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) {this.val = val;}ListNode(int val, ListNode next) {this.val = val;this.next = next;}
}

非递归解法

//非递归解法
public ListNode reverseList1(ListNode head) {ListNode newHead = null;while (head != null) {ListNode tmp = head.next;head.next = newHead;newHead = head;head = tmp;}return newHead;
}

练习 - 判断链表是否有环（快慢指针）

LeetCode 141_环形链表：https://leetcode-cn.com/problems/linked-list-cycle/

package 链表;/*** https://leetcode-cn.com/problems/linked-list-cycle/** @author xiexu* @create 2021-07-14 9:42 下午*/
public class _141_环形链表 {public boolean hasCycle(ListNode head) {if (head == null || head.next == null) {return false;}ListNode slow = head;ListNode fast = head.next;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {return true;}}return false;}
}

package 链表;/*** @author xiexu* @create 2021-07-14 9:10 下午*/
public class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) {this.val = val;}ListNode(int val, ListNode next) {this.val = val;this.next = next;}
}

练习 - 移除链表元素

LeetCode 203_移除链表元素 https://leetcode-cn.com/problems/remove-linked-list-elements/

package 链表;/*** @author xiexu* @create 2021-07-14 10:47 下午*/
public class _203_移除链表元素 {public ListNode removeElements(ListNode head, int val) {//删除值相同的头结点后，可能新的头结点也值相等，用循环解决while (head != null && head.val == val) {head = head.next;}if (head == null) {return head;}ListNode prev = head;while (prev.next != null) {if (prev.next.val == val) {prev.next = prev.next.next;} else {prev = prev.next;}}return head;}
}

package 链表;/*** @author xiexu* @create 2021-07-14 9:10 下午*/
public class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) {this.val = val;}ListNode(int val, ListNode next) {this.val = val;this.next = next;}
}

练习 - 删除排序链表中的重复元素

LeetCode 82_删除排序链表中的重复元素 https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/

package 链表;/*** @author xiexu* @create 2021-07-15 8:01 上午*/
public class _83_删除排序链表中的重复元素 {public ListNode deleteDuplicates(ListNode head) {if (head == null) {return head;}ListNode tmp = head;while (tmp.next != null) {if (tmp.val == tmp.next.val) {tmp.next = tmp.next.next;} else {tmp = tmp.next;}}return head;}
}

练习 - 链表的中间结点

LeetCode 876_链表的中间结点 https://leetcode-cn.com/problems/middle-of-the-linked-list/

package 链表;/*** https://leetcode-cn.com/problems/middle-of-the-linked-list/** @author xiexu* @create 2021-07-15 8:12 上午*/
public class _876_链表的中间结点 {public ListNode middleNode(ListNode head) {if (head == null) {return head;}ListNode tmp = head;int size = 0;while (tmp != null) {size++;tmp = tmp.next;}int middle = size / 2;for (int i = 0; i < middle; i++) {head = head.next;}return head;}
}

带虚拟头结点的单向链表

有时候为了让代码更加精简，统一所有节点的处理逻辑，可以在最前面增加一个虚拟的头结点（不存储数据）

package cn.xx.java.single;import cn.xx.java.AbstractList;/*** 增加一个虚拟头结点** @author xiexu* @create 2021-07-13 9:52 上午*/
public class SingleLinkedList2<E> extends AbstractList<E> {private Node<E> first;public SingleLinkedList2() {first = new Node<>(null, null);}@Overridepublic void clear() {size = 0;first = null;}@Overridepublic E get(int index) {return node(index).element;}@Overridepublic E set(int index, E element) {Node<E> node = node(index);E old = node.element;node.element = element;return old;}@Overridepublic void add(int index, E element) {rangeCheckForAdd(index);Node<E> prev = index == 0 ? first : node(index - 1); //获取上一个节点Node<E> newNode = new Node<>(element, prev.next);prev.next = newNode;size++;}@Overridepublic E remove(int index) {rangeCheck(index);Node<E> prev = index == 0 ? first : node(index - 1); //获取上一个节点Node<E> node = prev.next;prev.next = node.next;size--;return node.element;}/*** 查看元素的索引** @param element* @return*/@Overridepublic int indexOf(E element) {Node<E> node = first;//null值的判断if (element == null) {for (int i = 0; i < size; i++) {if (node.element == null) {return i;}node = node.next;}} else {for (int i = 0; i < size; i++) {if (element.equals(node.element)) {return i;}node = node.next;}}return ELEMENT_NOT_FOUND; //找不到就返回-1}/*** 获取index位置对应的结点** @param index* @return*/private Node<E> node(int index) {rangeCheck(index);Node<E> node = first.next;for (int i = 0; i < index; i++) {node = node.next;}return node;}//Node内部类private static class Node<E> {E element;Node<E> next;public Node(E element, Node<E> next) {this.element = element;this.next = next;}}@Overridepublic String toString() {StringBuilder string = new StringBuilder();string.append("size = ").append(size).append(", [");Node<E> node = first.next;for (int i = 0; i < size; i++) {if (i != 0) {string.append(", ");}string.append(node.element);node = node.next;}string.append("]");return string.toString();}
}

动态数组、链表复杂度分析

数组的随机访问速度非常快：elements[n] 的效率与 n 是多少无关

双向链表（LinkedList）

双向链表可以提升链表的综合性能

双向链表只有一个元素的情况：first、last 指向同一个节点

双向链表 – node(int index)

/*** 获取index位置对应的结点** @param index* @return*/
private Node<E> node(int index) {rangeCheck(index);if (index < (size >> 1)) {Node<E> node = first;for (int i = 0; i < index; i++) {node = node.next;}return node;} else {Node<E> node = last;for (int i = size - 1; i > index; i--) {node = node.prev;}return node;}}

双向链表 - add(int index, E element)

@Override
public void add(int index, E element) {rangeCheckForAdd(index);if (index == size) { //往最后面添加元素Node<E> oldLast = last; //之前还未添加的lastlast = new Node<>(element, oldLast, null);if (oldLast == null) { //这是链表添加的第一个元素first = last;} else {oldLast.next = last;}} else {Node<E> next = node(index);Node<E> prev = next.prev;Node<E> node = new Node<>(element, prev, next);next.prev = node;if (prev == null) { //等价于index == 0first = node;} else {prev.next = node;}}size++;
}

双向链表 – remove(int index)

@Override
public E remove(int index) {rangeCheck(index);Node<E> node = node(index);Node<E> prev = node.prev;Node<E> next = node.next;if (prev == null) { //等价于index == 0first = next;} else {prev.next = next;}if (next == null) { //等价于 index == size - 1last = prev;} else {next.prev = prev;}size--;return node.element;
}

双向链表完整代码

package cn.xx.java;/*** @author xiexu* @create 2021-07-13 9:52 上午*/
public class LinkedList<E> extends AbstractList<E> {private Node<E> first;private Node<E> last;@Overridepublic void clear() {size = 0;first = null;last = null;}@Overridepublic E get(int index) {/*** 最好：O(1)* 最坏：O(n)* 平均：O(n)*/return node(index).element;}@Overridepublic E set(int index, E element) {/*** 最好：O(1)* 最坏：O(n)* 平均：O(n)*/Node<E> node = node(index);E old = node.element;node.element = element;return old;}@Overridepublic void add(int index, E element) {rangeCheckForAdd(index);if (index == size) { //往最后面添加元素Node<E> oldLast = last; //之前还未添加的lastlast = new Node<>(element, oldLast, null);if (oldLast == null) { //这是链表添加的第一个元素first = last;} else {oldLast.next = last;}} else {Node<E> next = node(index);Node<E> prev = next.prev;Node<E> node = new Node<>(element, prev, next);next.prev = node;if (prev == null) { //等价于index == 0first = node;} else {prev.next = node;}}size++;}@Overridepublic E remove(int index) {rangeCheck(index);Node<E> node = node(index);Node<E> prev = node.prev;Node<E> next = node.next;if (prev == null) { //等价于index == 0first = next;} else {prev.next = next;}if (next == null) { //等价于 index == size - 1last = prev;} else {next.prev = prev;}size--;return node.element;}/*** 查看元素的索引** @param element* @return*/@Overridepublic int indexOf(E element) {Node<E> node = first;//null值的判断if (element == null) {for (int i = 0; i < size; i++) {if (node.element == null) {return i;}node = node.next;}} else {for (int i = 0; i < size; i++) {if (element.equals(node.element)) {return i;}node = node.next;}}return ELEMENT_NOT_FOUND; //找不到就返回-1}/*** 获取index位置对应的结点** @param index* @return*/private Node<E> node(int index) {rangeCheck(index);if (index < (size >> 1)) { //索引小于一半从前往后找Node<E> node = first;for (int i = 0; i < index; i++) {node = node.next;}return node;} else { //索引大于一半从后往前找Node<E> node = last;for (int i = size - 1; i > index; i--) {node = node.prev;}return node;}}//Node内部类private static class Node<E> {E element;Node<E> prev;Node<E> next;public Node(E element, Node<E> prev, Node<E> next) {this.element = element;this.prev = prev;this.next = next;}@Overridepublic String toString() {StringBuilder sb = new StringBuilder();if (prev != null) {sb.append(prev.element);} else {sb.append("null");}sb.append("_").append(element).append("_");if (next != null) {sb.append(next.element);} else {sb.append("null");}return sb.toString();}}@Overridepublic String toString() {StringBuilder string = new StringBuilder();string.append("size = ").append(size).append(", [");Node<E> node = first;for (int i = 0; i < size; i++) {if (i != 0) {string.append(", ");}string.append(node);node = node.next;}string.append("]");return string.toString();}
}

双向链表 vs 单向链表

有了双向链表，单向链表是否就没有任何用处了？

• 并非如此，在哈希表的设计中就用到了单链表
• 至于原因，在哈希表章节中会讲到

双向链表 vs 动态数组

单向循环链表

单向循环链表 - 只有1个节点的情况：

单向循环链表 - add(int index, E element)

@Override
public void add(int index, E element) {rangeCheckForAdd(index);if (index == 0) {first = new Node<>(element, first);//拿到最后一个结点Node<E> last = (size == 0) ? first : node(size - 1);last.next = first;} else {Node<E> prev = node(index - 1); //获取上一个节点Node<E> newNode = new Node<>(element, prev.next);prev.next = newNode;}size++;
}

单向循环链表 - remove(int index)

@Override
public E remove(int index) {rangeCheck(index);Node<E> node = first;if (index == 0) { //删除0位置的元素if (size == 1) {first = null;} else {Node<E> last = node(size - 1); //拿到最后一个结点first = first.next;last.next = first;}} else {Node<E> prev = node(index - 1); //获取上一个节点node = prev.next;prev.next = node.next;}size--;return node.element;
}

单向循环链表完整代码

package cn.xx.java.circle;import cn.xx.java.AbstractList;/*** 单向循环链表** @author xiexu* @create 2021-07-13 9:52 上午*/
public class SingleCircleLinkedList<E> extends AbstractList<E> {private Node<E> first;@Overridepublic void clear() {size = 0;first = null;}@Overridepublic E get(int index) {/*** 最好：O(1)* 最坏：O(n)* 平均：O(n)*/return node(index).element;}@Overridepublic E set(int index, E element) {/*** 最好：O(1)* 最坏：O(n)* 平均：O(n)*/Node<E> node = node(index);E old = node.element;node.element = element;return old;}@Overridepublic void add(int index, E element) {rangeCheckForAdd(index);if (index == 0) {Node<E> newFirst = new Node<>(element, first);//拿到最后一个结点Node<E> last = (size == 0) ? newFirst : node(size - 1);last.next = newFirst;first = newFirst;} else {Node<E> prev = node(index - 1); //获取上一个节点Node<E> newNode = new Node<>(element, prev.next);prev.next = newNode;}size++;}@Overridepublic E remove(int index) {rangeCheck(index);Node<E> node = first;if (index == 0) { //删除0位置的元素if (size == 1) { //链表只有一个结点first = null;} else {Node<E> last = node(size - 1); //拿到最后一个结点first = first.next;last.next = first;}} else {Node<E> prev = node(index - 1); //获取上一个节点node = prev.next;prev.next = node.next;}size--;return node.element;}/*** 查看元素的索引** @param element* @return*/@Overridepublic int indexOf(E element) {Node<E> node = first;//null值的判断if (element == null) {for (int i = 0; i < size; i++) {if (node.element == null) {return i;}node = node.next;}} else {for (int i = 0; i < size; i++) {if (element.equals(node.element)) {return i;}node = node.next;}}return ELEMENT_NOT_FOUND; //找不到就返回-1}/*** 获取index位置对应的结点** @param index* @return*/private Node<E> node(int index) {rangeCheck(index);Node<E> node = first;for (int i = 0; i < index; i++) {node = node.next;}return node;}//Node内部类private static class Node<E> {E element;Node<E> next;public Node(E element, Node<E> next) {this.element = element;this.next = next;}@Overridepublic String toString() {StringBuilder sb = new StringBuilder();sb.append(element).append("_").append(next.element);return sb.toString();}}@Overridepublic String toString() {StringBuilder string = new StringBuilder();string.append("size = ").append(size).append(", [");Node<E> node = first;for (int i = 0; i < size; i++) {if (i != 0) {string.append(", ");}string.append(node);node = node.next;}string.append("]");return string.toString();}
}

双向循环链表

双向循环链表 - 只有1个节点的情况：

双向循环链表完整代码

package cn.xx.java.circle;import cn.xx.java.AbstractList;/*** @author xiexu* @create 2021-07-13 9:52 上午*/
public class CircleLinkedList<E> extends AbstractList<E> {private Node<E> first;private Node<E> last;private Node<E> current;/*** 让current指向头结点first*/public void reset() {current = first;}/*** 让current往后走一步** @return*/public E next() {if (current == null) {return null;}current = current.next;return current.element;}/*** 删除current指向的结点，删除成功后让current指向下一个结点** @return*/public E remove() {if (current == null) {return null;}Node<E> next = current.next;E element = remove(current);if (size == 0) {current = null;} else {current = next;}return element;}@Overridepublic void clear() {size = 0;first = null;last = null;}@Overridepublic E get(int index) {/*** 最好：O(1)* 最坏：O(n)* 平均：O(n)*/return node(index).element;}@Overridepublic E set(int index, E element) {Node<E> node = node(index);E old = node.element;node.element = element;return old;}@Overridepublic void add(int index, E element) {rangeCheckForAdd(index);if (index == size) { //往最后面添加元素Node<E> oldLast = last; //之前的lastlast = new Node<>(element, oldLast, first);if (oldLast == null) { //这是链表添加的第一个元素first = last;first.next = last;first.prev = first;} else {oldLast.next = last;first.prev = last;}} else {Node<E> next = node(index);Node<E> prev = next.prev;Node<E> node = new Node<>(element, prev, next);next.prev = node;prev.next = node;if (index == 0) {first = node;}}size++;}@Overridepublic E remove(int index) {rangeCheck(index);return remove(node(index));}private E remove(Node<E> node) {if (size == 1) {first = null;last = null;} else {Node<E> prev = node.prev;Node<E> next = node.next;prev.next = next;next.prev = prev;if (node == first) { //等价于 index == 0first = next;}if (node == last) { //等价于 index == size - 1last = prev;}}size--;return node.element;}/*** 查看元素的索引** @param element* @return*/@Overridepublic int indexOf(E element) {Node<E> node = first;//null值的判断if (element == null) {for (int i = 0; i < size; i++) {if (node.element == null) {return i;}node = node.next;}} else {for (int i = 0; i < size; i++) {if (element.equals(node.element)) {return i;}node = node.next;}}return ELEMENT_NOT_FOUND; //找不到就返回-1}/*** 获取index位置对应的结点** @param index* @return*/private Node<E> node(int index) {rangeCheck(index);if (index < (size >> 1)) { //索引小于一半从前往后找Node<E> node = first;for (int i = 0; i < index; i++) {node = node.next;}return node;} else { //索引大于一半从后往前找Node<E> node = last;for (int i = size - 1; i > index; i--) {node = node.prev;}return node;}}//Node内部类private static class Node<E> {E element;Node<E> prev;Node<E> next;public Node(E element, Node<E> prev, Node<E> next) {this.element = element;this.prev = prev;this.next = next;}@Overridepublic String toString() {StringBuilder sb = new StringBuilder();if (prev != null) {sb.append(prev.element);} else {sb.append("null");}sb.append("_").append(element).append("_");if (next != null) {sb.append(next.element);} else {sb.append("null");}return sb.toString();}}@Overridepublic String toString() {StringBuilder string = new StringBuilder();string.append("size = ").append(size).append(", [");Node<E> node = first;for (int i = 0; i < size; i++) {if (i != 0) {string.append(", ");}string.append(node);node = node.next;}string.append("]");return string.toString();}
}

练习 - 约瑟夫问题

package cn.xx.java.circle;import cn.xx.java.AbstractList;/*** @author xiexu* @create 2021-07-13 9:52 上午*/
public class CircleLinkedList<E> extends AbstractList<E> {private Node<E> first;private Node<E> last;private Node<E> current;/*** 让current指向头结点first*/public void reset() {current = first;}/*** 让current往后走一步** @return*/public E next() {if (current == null) {return null;}current = current.next;return current.element;}/*** 删除current指向的结点，删除成功后让current指向下一个结点** @return*/public E remove() {if (current == null) {return null;}Node<E> next = current.next;E element = remove(current);if (size == 0) {current = null;} else {current = next;}return element;}@Overridepublic void clear() {size = 0;first = null;last = null;}@Overridepublic E get(int index) {/*** 最好：O(1)* 最坏：O(n)* 平均：O(n)*/return node(index).element;}@Overridepublic E set(int index, E element) {Node<E> node = node(index);E old = node.element;node.element = element;return old;}@Overridepublic void add(int index, E element) {rangeCheckForAdd(index);if (index == size) { //往最后面添加元素Node<E> oldLast = last; //之前的lastlast = new Node<>(element, oldLast, first);if (oldLast == null) { //这是链表添加的第一个元素first = last;first.next = last;first.prev = first;} else {oldLast.next = last;first.prev = last;}} else {Node<E> next = node(index);Node<E> prev = next.prev;Node<E> node = new Node<>(element, prev, next);next.prev = node;prev.next = node;if (index == 0) {first = node;}}size++;}@Overridepublic E remove(int index) {rangeCheck(index);return remove(node(index));}private E remove(Node<E> node) {if (size == 1) {first = null;last = null;} else {Node<E> prev = node.prev;Node<E> next = node.next;prev.next = next;next.prev = prev;if (node == first) { //等价于 index == 0first = next;}if (node == last) { //等价于 index == size - 1last = prev;}}size--;return node.element;}/*** 查看元素的索引** @param element* @return*/@Overridepublic int indexOf(E element) {Node<E> node = first;//null值的判断if (element == null) {for (int i = 0; i < size; i++) {if (node.element == null) {return i;}node = node.next;}} else {for (int i = 0; i < size; i++) {if (element.equals(node.element)) {return i;}node = node.next;}}return ELEMENT_NOT_FOUND; //找不到就返回-1}/*** 获取index位置对应的结点** @param index* @return*/private Node<E> node(int index) {rangeCheck(index);if (index < (size >> 1)) { //索引小于一半从前往后找Node<E> node = first;for (int i = 0; i < index; i++) {node = node.next;}return node;} else { //索引大于一半从后往前找Node<E> node = last;for (int i = size - 1; i > index; i--) {node = node.prev;}return node;}}//Node内部类private static class Node<E> {E element;Node<E> prev;Node<E> next;public Node(E element, Node<E> prev, Node<E> next) {this.element = element;this.prev = prev;this.next = next;}@Overridepublic String toString() {StringBuilder sb = new StringBuilder();if (prev != null) {sb.append(prev.element);} else {sb.append("null");}sb.append("_").append(element).append("_");if (next != null) {sb.append(next.element);} else {sb.append("null");}return sb.toString();}}@Overridepublic String toString() {StringBuilder string = new StringBuilder();string.append("size = ").append(size).append(", [");Node<E> node = first;for (int i = 0; i < size; i++) {if (i != 0) {string.append(", ");}string.append(node);node = node.next;}string.append("]");return string.toString();}
}

测试方法

static void josephus() {CircleLinkedList<Integer> list = new CircleLinkedList<>();for (int i = 1; i <= 8; i++) {list.add(i);}//让current指向头结点(指向1)list.reset();while (!list.isEmpty()) {list.next();list.next();System.out.println(list.remove());}
}

如何发挥循环链表的最大威力？

静态链表（了解）

ArrayList能否进一步优化？