封面画师：ツチヤ封面ID：80796376

本文参考视频：小马哥教育(SEEMYGO) 2019年恋上数据结构与算法（第一季）

源码仓库：mofan212/data-structure-and-algorithm (github.com)

辅助学习网址：数据结构和算法动态可视化

1. 单向链表

1.1 简介

动态数组有一个明显的缺点：持续添加元素到容量不够时，动态数组会进行扩容（假设扩容 1.5 倍），扩容后的空间也不一定能全部用完，甚至可能出现只用了一点空间的情况，这个时候就 会造成内存空间的大量浪费 。

那么可以做到用多少空间就申请多少空间吗？

当然是可以的！😎

链表（Linked List）就可以做到这一点。链表是一种 链式存储 的线性表，其中元素的内存地址 不一定 是连续的。

结构图：

1.2 链表的设计

/**
 * @author 默烦
 * @date 2020/6/24
 */
public class LinkedList<E> {
    private int size;
    private Node<E> first;

    private static class Node<E> {
        E element;
        Node<E> next;

        public Node(E element, Node<E> next) {
            this.element = element;
            this.next = next;
        }
    }
}

1.3 接口设计

链表和动态数组都属于线性表，它们存在相同点。比如，它们的对外接口是类似的。

因此可以编写一个接口，该接口定义了线性表的操作规范：

/**
 * @author 默烦
 * @date 2020/6/24
 */
public interface List<E> {
    // 清除所有元素
    void clear();

    // 元素的数量
    int size();

    // 判断是否为空
    boolean isEmpty();

    // 判断是否包含某个元素
    boolean contains(E element);

    // 添加元素到尾部
    void add(E element);

    // 获取index位置的元素
    E get(int index);

    // 设置index位置的元素
    E set(int index, E element);

    // 向index位置添加一个元素 且默认支持插入空数据null
    void add(int index, E element);

    // 删除index位置的元素
    E remove(int index);

    // 查看元素的索引
    int indexOf(E element);

}

既然有了这样的接口，那么可以让动态数组和链表都实现它：

1	public class ArrayList<E> implements List<E> { ... }

1	public class LinkedList<E> implements List<E> { ... }

在编写代码时又会发现 ArrayList 与 LinkedList 还有部分代码是可以共用的，那么应该怎么做呢？

可以创建一个抽象的父类，抽象类实现 List 接口，而 ArrayList 与 LinkedList 继承这个父类：

/**
 * 抽取公共代码
 * @author 默烦
 * @date 2020/6/24
 */
public abstract class AbstractList<E> implements List<E> {

    // 元素的数量
    protected int size;

    public int size() {
        return size;
    }


    public boolean isEmpty() {
        return size == 0;
    }

    public boolean contains(E element) {
        return indexOf(element) != ELEMENT_NOT_FOUND ;
    }

    public void add(E element) {
        add(size,element);
    }

    // 越界异常封装
    protected void outOfBounds(int index) {
        throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }

    // 普通范围检查
    protected void rangeCheck(int index) {
        if (index < 0 || index >= size) {
            outOfBounds(index);
        }
    }

    // 添加元素的范围检查
    // 允许index = size，当index等于size时，相当于在数组末尾添加元素
    protected void rangeCheckForAdd(int index) {
        if (index < 0 || index > size) {
            outOfBounds(index);
        }
    }
}

此时 List 接口也会发生变化，需要添加static final int ELEMENT_NOT_FOUND = -1;。

/**
 * @author 默烦
 * @date 2020/6/24
 */
public interface List<E> {
    // 接口中的变量与方法默认都是公共的
    // 为什么要将ELEMENT_NOT_FOUND放在接口中，因为放在接口中外界可以访问
    static final int ELEMENT_NOT_FOUND = -1;

	... 
}

为什么要把这个常量添加在 List 接口中呢？而不添加在父类 AbstractList 中呢？

可以肯定的是，该常量必须添加在 List 接口或抽象类 AbstractList 中，因为 AbstractList 中使用了这个常量，同时希望用户也可以使用这个常量，而 AbstractList 仅仅是用来抽取公共代码的，用户在使用时不需要关心父类 AbstractList。此次之外，由于关键词 abstract 的存在，不能使用 new 关键词来创建一个 AbstractList 对象，因此可以将这个常量放在接口中，使用时直接 List.ELEMENT_NOT_FOUND 就可以了。

LinkedList 类的基本结构：

/**
 * @author 默烦
 * @date 2020/6/24
 */
public class LinkedList<E> extends AbstractList<E> {

    private Node<E> first;

    @Override
    public void clear() { ... }

    @Override
    public E get(int index) { ... return null;}

    @Override
    public E set(int index, E element) { ... return null;}

    @Override
    public void add(int index, E element) { ... }

    @Override
    public E remove(int index) { ... return null;}

    @Override
    public int indexOf(E element) { ... return 0;}

    private static class Node<E>{
        E element;
        Node<E> next;

        public Node(E element, Node<E> next) {
            this.element = element;
            this.next = next;
        }
    }
}

可以看到 LinkedList 中并没有显式定义构造方法，而 ArrayList 中却定义了，这是为什么呢？

原因很简单，使用 ArrayList 时，允许传递一个参数作为 ArrayList 的容量，但 LinkedList 是不需要的，对于 LinkedList 来说，插入一个新节点就会开辟一个新空间。

1.4 清空链表

设计思想

要达成清空的目的，首先链表的元素数量必须设置为 0，即：size = 0。

仅仅 size = 0 是远远不够的，还需要将申请的链表空间清空，即：清空每个结点。依次将每个结点清空？

只需要将指向首节点的地址清空就可以了，即：first = null。使用这种方式，首节点无人使用，会被垃圾回收机制处理，然后导致第二个结点无人使用，进而又会被垃圾回收机制处理，这样一步步下去，就可以使整个链表的节点都清空。

代码实现

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

1.5 添加元素

设计思想

假设有一个链表，其中有 4 个节点，将它们分别标号为：1、2、3、4。这个时候想在 3 的位置添加一个节点 x，那么需要先将节点 x 的 next 指向 3，再将 2 的 next 指向 x 就可以了（顺序不能反过来，否则链表就断了）。

在链表节点 A-C 之间插入节点 B 的详细步骤如下：

获取添加位置上一个节点 A
创建一个新节点 B
将 B 的 next 指向 C
将 A 的 next 指向 B
size 加一

代码实现

// 获取某个位置的节点对象
private Node<E> node(int index) {
    rangeCheck(index);
    Node<E> node = first;
    for (int i = 0; i < index; i++) {
        node = node.next;
    }
    return node;
}
// 添加节点到某个位置
public void add(int index, E element) {
   /*
    * 最好:O(1)
    * 最坏:O(n)
    * 平均:O(n)
    * */
    rangeCheckForAdd(index);
    // 判断插入位置是否是第一个位置
    if (index == 0) {
        first = new Node<>(element, first);
    } else {
        // 获取添加位置上一个节点
        Node<E> prev = node(index - 1);
        // 创建需要添加的节点，并将前一个节点的next指向新节点
        prev.next = new Node<>(element, prev.next);
    }
    size++;
}

根据已有的 node() 方法，可以将 get() 和 set() 方法一并实现：

// 获取某个位置节点的值
public E get(int index) {
   /*
    * 最好:O(1)
    * 最坏:O(n)
    * 平均:O(n)
    * */
    return node(index).element;
}

// 设置某个位置节点的值
public 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;
}

1.6 删除元素

设计思想

假设有一个链表，其中有 4 个节点，将它们分别标号为：1、2、3、4。如果想删除节点 2，那么可以直接将 1 的 next 指向 3 就可以了。

删除链表节点 A-B-C 中的 B 的详细步骤如下：

获取删除位置前一个节点 A
将 A 的 next 指向 C
size 减一

代码实现

public E remove(int index) {
   /*
    * 最好:O(1)
    * 最坏:O(n)
    * 平均:O(n)
    * */
    rangeCheck(index);	// 防止刚创建链表就进行删除
    Node<E> node = first;
    if (index == 0) {
        first = first.next;
    } else {
        Node<E> prev = node(index - 1);
        node = prev.next;
        prev.next = node.next;
    }
    size--;
    // 返回删除的节点
    return node.element;
}

1.7 完整代码

/**
 * @author 默烦
 * @date 2020/6/24
 */
public class LinkedList<E> extends AbstractList<E> {

    private Node<E> first;

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

    // 获取某个位置节点的值
    @Override
    public E get(int index) {
        return node(index).element;
    }

    // 设置某个位置节点的值
    @Override
    public E set(int index, E element) {
        Node<E> node = node(index);
        E old = node.element;
        node.element = element;
        return old;
    }

    @Override
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        if (index == 0) {
            first = new Node<>(element, first);
        } else {
            // 获取添加位置上一个节点
            Node<E> prev = node(index - 1);
            // 创建需要添加的节点，并将前一个节点的next指向新节点
            prev.next = new Node<>(element, prev.next);
        }
        size++;
    }

    @Override
    public E remove(int index) {
        rangeCheck(index);
        Node<E> node = first;
        if (index == 0) {
            first = first.next;
        } else {
            Node<E> prev = node(index - 1);
            node = prev.next;
            prev.next = node.next;
        }
        size--;
        // 返回删除的节点
        return node.element;
    }

    @Override
    public int indexOf(E element) {
        // 处理空值
        if (element == null) {
            Node<E> node = first;
            for (int i = 0; i < size; i++) {
                if (node.element == null) return i;
                node = node.next;
            }
        } else {
            Node<E> node = first;
            for (int i = 0; i < size; i++) {
                if (element.equals(node.element)) return i;
                node = node.next;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    // 获取某个位置的节点对象
    private Node<E> node(int index) {
        rangeCheck(index);
        Node<E> node = first;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }

    @Override
    public String toString() {
        // 打印效果 size = 3, [99,88,77]
        StringBuilder builder = new StringBuilder();
        builder.append("size=").append(size).append(", [");
        Node<E> node = first;
        for (int i = 0; i < size; i++) {
            if (i != 0) {
                builder.append(", ");
            }
            builder.append(node.element);
            node = node.next;
        }
        builder.append("]");
        return builder.toString();
    }

    private static class Node<E> {
        E element;
        Node<E> next;

        public Node(E element, Node<E> next) {
            this.element = element;
            this.next = next;
        }
    }
}

1.8 虚拟头结点

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

使用了虚拟头结点，就可以不用再处理 index == 0 的情况。

需要添加一个构造函数：

// 添加虚拟头结点
public LinkedList2() {
    first = new Node<>(null, null);
}

修改 node() 和 toString() 方法的实现：

// 获取某个位置的节点对象
private Node<E> node(int index) {
    rangeCheck(index);
	// 修改前: Node<E> node = first;
    Node<E> node = first.next;
    for (int i = 0; i < index; i++) {
        node = node.next;
    }
    return node;
}
@Override
public String toString() {
    // 打印效果 size = 3, [99,88,77]
    StringBuilder builder = new StringBuilder();
    builder.append("size=").append(size).append(", [");
    // 修改前: Node<E> node = first;
    Node<E> node = first.next;
    for (int i = 0; i < size; i++) {
        if (i != 0) {
            builder.append(", ");
        }
        builder.append(node.element);
        node = node.next;
    }
    builder.append("]");
    return builder.toString();
}

修改 add() 和 remove() 方法的实现：

@Override
public void add(int index, E element) {
    rangeCheckForAdd(index);
    // 获取添加位置上一个节点
    Node<E> prev = index == 0 ? first : node(index - 1);
    // 创建需要添加的节点，并将前一个节点的next指向新节点
    prev.next = new Node<>(element, prev.next);
    size++;
}

@Override
public 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;
}

1.9 复杂度对比

2. 双向链表

2.1 简介

前文实现的链表属于单向链表，单向链表只能通过头结点向下遍历，双向链表则可以提升链表的综合性能。

2.2 接口设计

双向链表的接口设计与单向链表的接口设计一样，只是部分方法的实现需要发生改变，比如：clear()、add(int index, E element)、remove(int index)。

新建一个包 single，将单向链表的类重命名为 SingleLinkedList，并将其放置于 single 包中，然后复制单向链表的代码到当前目录，命名为 LinkedList，在 LinkedList 中对部分代码进行修改，完成双向链表的编写（JDK 中使用的就是双向链表）。

2.3 清空链表

设计思路

从结构图中得知，双向链表有两个指针：first 和 last，分别指向首节点和尾节点，如果需要清空链表，将这两个指针指向 null 即可。

代码实现

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

拓展分析

虽然将指针 first 和 last 设置为 null可以初步完成清空的目的，但根据结构图所示，每个结点都有 next 指针指向下一个节点，都有 prev 指针指向上一个节点，那么整个链表真的会被清空并被 GC 释放空间吗？

答案是肯定的。前面说了没被引用的对象会被“干掉”，但并不是说只要被引用了就不会被“干掉”，主要还是看被谁引用。在 Java 中，被 GC root 对象引用的对象不会被“干掉”，没被其引用的对象会被干掉。

GC root 对象包含被栈指针（局部变量）指向的对象，List<Integer> list = new LinkedList<>(); 中的 list 是局部变量，list 引用了 LinkedList 对象，它被认为是 GC root 对象。

当指针 first 和 last 设置为 null 时，每个节点虽然被其他节点循环引用，但并没有被 GC root 对象引用，因此最后还是会被 GC 清理掉。

在 JDK 中，双向链表 LinkedList 的清空链表方法如下：

public void clear() {
    // Clearing all of the links between nodes is "unnecessary", but:
    // - helps a generational GC if the discarded nodes inhabit
    //   more than one generation
    // - is sure to free memory even if there is a reachable Iterator
    for (Node<E> x = first; x != null; ) {
        Node<E> next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    first = last = null;
    size = 0;
    modCount++;
}

虽然整体操作差不多，但是还是有些区别。它不仅将指针 first 和 last 设置为了 null，还将每个节点的 next 和 prev 指针设置为 null。这又是为什么呢？

这与迭代器有关。当迭代器正在引用一个节点时，且这个迭代器也恰好是 GC root 对象时，虽然已经将指针 first 和 last 设置为 null，但链表并不会被清空。

2.4 添加元素

设计思路

假设一个双向链表有 4 个节点，分别是 A - B - C - D，然后在这个链表中添加元素。

通用情况下 插入的节点在链表中间 （假设在索引为 1 的位置插入一个节点）：

获取插入位置的节点 B 和插入位置的前一个节点 A
创建新节点 X，X 的 next 指向 B，X 的 prev 指向 A
B 的 prev 指向 X，A 的 next 指向 X
size 加一

那如果是 在索引为0的位置插入元素 呢？索引为 0 的节点的 prev 为 null，使用 first 指向 X 就可以了。

如果 在链表最后插入元素 呢？即：index == size

获取最后一个节点 D
创建一个新节点 X，X 的 next 设置为 null，X 的 prev 指向 D
将 last 指向节点 X，D 的 next 指向 X
size 加一

这时又会出现一个问题，如果链表原本就是空的，没有一个节点，是 第一次插入节点。这样的话就会出现空指针异常的问题，此时 first 和 last 都应该指向插入的节点。

使用了双向链表后，获取某个位置的节点的方法也要发生改变 。可以根据索引 index 与链表长度 size 之间的关系来判断遍历方式是从前往后还是从后往前的。

代码实现

// 获取某个位置的节点对象
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;
    }
}
@Override
public void add(int index, E element) {
    rangeCheckForAdd(index);
    if (index == size) { // 向最后一个位置插入节点
        Node<E> oldLast = last;
        last = new Node<>(element, null, oldLast);
        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, next, prev);
        next.prev = node;
        if (prev == null) { // index == 0
            first = node;
        } else {
            prev.next = node;
        }
    }
    size++;
}

2.5 删除元素

设计思路

假设一个双向链表有 4 个节点，分别是 A - B - C - D，需要在这个链表中删除元素，此时会有有三种情况：删除链表中间的元素、删除链表首节点、删除链表尾节点。

删除链表中间的元素（假设删除元素 C）：

获取删除位置的元素 C
获取删除位置前一个元素 B、后一个元素 D
将 B 的 next 指向 D，将 D 的 prev 指向 B
size 减一

删除首节点时：

获取删除位置的元素 A
获取删除位置后一个元素 B
将 first 指向 B，将 B 的 prev 设置为 null（或者说设置为删除元素 A 的 prev）
size 减一

删除尾节点时：

获取删除位置的元素 D
获取删除位置前一个元素 C
将 last 指向 C，将 C 的 next 设置为 null（或者说设置为删除元素 D 的 next）
size 减一

代码实现

@Override
public E remove(int index) {
    rangeCheck(index);
    Node<E> node = node(index);
    Node<E> next = node.next;
    Node<E> prev = node.prev;
    if (prev == null) {  // index == 0
        first = next;
    } else {
        prev.next = next;
    }
    if (next == null) {  // index = size - 1
        last = prev;
    } else {
        next.prev = prev;
    }
    size--;
    // 返回删除的节点
    return node.element;
}

2.6 输出测试

为了在测试双向链表时能够清楚地看到使用了双向链表的结构，可以对 LinkedList 中的 toString() 和内部类 Node<E> 进行改写：

@Override
public String toString() {
    // 打印效果 size = 3, [99,88,77]
    StringBuilder builder = new StringBuilder();
    builder.append("size=").append(size).append(", [");
    Node<E> node = first;
    for (int i = 0; i < size; i++) {
        if (i != 0) {
            builder.append(", ");
        }
        // builder.append(node.element);
        builder.append(node);
        node = node.next;
    }
    builder.append("]");
    return builder.toString();
}

private static class Node<E> {
    E element;
    Node<E> next;
    Node<E> prev;

    public Node(E element, Node<E> next, Node<E> prev) {
        this.element = element;
        this.next = next;
        this.prev = prev;
    }

    // 新增内部类的toString()方法
    @Override
    public 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();
    }
}

测试代码：

public class Main {
    public static void main(String[] args) {
        List<Integer> list = new LinkedList<>();
        list.add(11);
        list.add(22);
        list.add(33);
        list.add(44);
        System.out.println(list);
        list.add(0,55);
        list.add(2,66);
        list.add(list.size(),77);
        System.out.println(list);

        list.remove(0);
        list.remove(2);
        list.remove(list.size() - 1);
        System.out.println(list);
        list.clear();
        System.out.println(list);
    }
}

输出结果：

2.7 总结

双向链表 VS 单向链表

粗略对比一下两者在删除元素时的节点遍历数量：

单向链表： 1 + 2 + 3 + … + n = n / 2 + n² / 2 ，除以 n 可得： 1 / 2 + n / 2
双向链表： 1 + 2 + 3 + … + n / 2 = n / 2 + n² / 4 ，除以 n 可得： 1 / 2 + n / 4
操作数量缩减了将近一半！

双向链表 VS 动态数组

动态数组：开辟、销毁内存空间的次数相对较少，但可能造成内存空间浪费（可以通过缩容解决）
双向链表：开辟、销毁内存空间的次数相对较多，但不会造成内存空间浪费

双向链表与动态数组的抉择：

如果频繁在尾部进行添加、删除操作，动态数组、双向链表 都可以选择
如果频繁在头部进行添加、删除操作，建议选择使用 双向链表
如果有频繁的 在任意位置 进行添加、删除操作，建议选择使用 双向链表
如果有频繁的 查询操作，建议使用 动态数组

那有了双向链表就不需要单向链表了吗？

双向链表的性能比单向链表好，单向链表就一无是处了？

并非如此，在哈希表的设计中就使用到了单链表。

3. 单向循环链表

在单向循环链表中，最后一个节点的 next 不设置为 null，而是指向第一个节点。

可以在当前项目新建一个包 circle，然后将单向链表 SingleLinkedList 的代码复制一份到这个包中，并改名为 SingleCircleLinkedList。

因为单向循环链表的特殊性，需要对代码进行修改，但不用全部修改，只修改 add() 和 remove() 的实现即可。

3.1 添加元素

思路分析

对于单向循环链表来说，在链表中间添加元素和在链表末尾添加元素的思路与普通单向链表一样，但是在链表首部添加节点就存在差异了。

假设一个单向循环链表有 4 个节点，分别是 A - B - C - D - A，在这个链表中添加元素。

在链表首部添加节点：

创建需要添加的节点 X，X 的 next 指向 A
获取最后一个节点，并对 size 进行判断：
- 当 size == 0 时（这表示链表中没有任何节点），最后一个节点就是需要添加的节点 X
- 当 size != 0 时（这表示链表中还有其他节点），最后一个就是索引为 index - 1 的节点
最后一个节点的 next 指向节点 X
令 first 指向节点 X，最后 size 加一

注意：一定要先获取最后一个节点后，才可以改变 first 的指向。

代码实现

public 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);
        // 创建需要添加的节点，并将前一个节点的next指向新节点
        prev.next = new Node<>(element, prev.next);
    }
    size++;
}

3.2 删除元素

思路分析

对于单向循环链表来说，在链表中间删除元素和在链表末尾删除元素的思路与普通单向链表一样，但是在链表首部删除节点就存在差异了。

假设一个单向循环链表有 4 个节点，分别是A - B - C - D - A，在这个链表中删除元素。

在链表首部删除节点：

判断链表是否仅仅只有一个节点
- 只有一个节点（size == 1），直接令 first 等于null，然后 size 减一即可。
- 当存在多个节点时：
  - 获取最后一个节点 D
  - 将 first 指向 first 的 next（让 first 指向第二个节点）
  - 让 D 的 next 指向 first（这时候 first 已经指向了未删除节点前链表的第二个节点）
  - size 减一

注意：必须要先获取最后一个节点，才能动 first 的指向，否则可能造成越界。

代码实现

@Override
public E remove(int index) {
    rangeCheck(index);
    Node<E> node = first;
    if (index == 0) {
        if (size == 1) {
            first = null;
        } else {
            /* 顺序不能换
             *  必须要先获取最后一个节点，才能动first的指向
             *  否则可能造成越界
             */
            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;
}

4. 双向循环链表

双向循环链表最后一个节点的 next 不设置为 null，而是指向第一个节点；第一个节点的 prev 不设置为 null，而是指向最后一个节点。

将双向链表 LinkedList 的代码复制一份到 circle 包中，并改名为 CircleLinkedList。

因为双向循环链表的特殊性，需要对代码进行修改，但是不用全部修改，只需修改 add() 和 remove() 的实现即可。

4.1 添加元素

思路分析

假设一个双向循环链表有 4 个节点，分别是 A - B - C - D - A，在这个链表中添加元素。

假设链表 长度大于 1 ，向最后一个位置插入节点时 ：

获取最后一个节点 D
创建添加的节点 X，X 的 nex t指向 first（第一个节点A），X 的 prev 指向节点 D
D 的 next 指向 X，first（第一个节点 A）的 prev 指向 X
size 加一

假设链表 长度等于 0 ，向最后一个位置插入节点时 ：

创建添加的节点 X
last 和 first 都要指向 X
X 的 next 和 last 指向自己本身
size 加一

在 其他位置插入节点 时（假设在节点 C 的位置插入节点 X）：

获取插入位置的节点 C，获取插入位置的前一个节点 B
创建新节点 X，X 的 next 指向 C，X 的 prev 指向 B
C 的 prev 指向 X，B 的 next 指向 X
如果是 向第一个位置插入节点 ，还需要将 first 指向 X
size 加一

代码实现

public void add(int index, E element) {
    rangeCheckForAdd(index);
    if (index == size) { // 向最后一个位置插入节点
        Node<E> oldLast = last;
        last = new Node<>(element, first, oldLast);
        if (oldLast == null) { // 插入第一个元素时
            first = last;
            first.next = first;
            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, next, prev);
        next.prev = node;
        prev.next = node;
        if (index == 0) { // index == 0
            first = node;
        }
    }
    size++;
}

4.2 删除元素

思路分析

当链表长度为 1 时：直接令 first 和 last 为 null，然后 size 减一即可。

当链表长度不为 1 时（假设删除节点 B）：

获取删除位置的节点 B，获取 B 的 next 指向的节点 A，获取 B 的 prev 指向的节点 C
A 的 prev 指向 C，C 的 next 指向 A
判断删除元素是否位于边界：
- 删除元素是第一个元素时，first 指向 A
- 删除元素是最后一个元素时，last 指向 C
size 减一

代码实现

public E remove(int index) {
    rangeCheck(index);
    Node<E> node = first;
    if (size == 1){
        first = null;
        last = null;
    } else {
        node = node(index);
        Node<E> next = node.next;
        Node<E> prev = node.prev;
        prev.next = next;
        next.prev = prev;
        if (node == first) {  // index == 0
            first = next;
        }
        if (node == last) {  // index = size - 1
            last = prev;
        }
    }
    size--;
    return node.element;    // 返回删除的节点
}

5. 约瑟夫问题

约瑟夫问题：假设有 8 个人，他们围成一圈，每人标号 1 - 8 。第一个人从 1 开始报数，报数为 3 的人被枪毙。然后剩下的人继续围成一个圈，从刚被枪毙的人的下一个开始从 1 报数，报数为 3 的人又被枪毙，直到只剩下一个人，那么最终这个人可以活下来。

约瑟夫问题可以使用循环链表来解决，在此选择双向循环链表。复制一份 CircleLinkedList 的代码到当前包，并命名为 Josephus。在这个类中增加一个成员变量、三个方法来发挥其最大威力：

current：用于指向某个节点

void reset()：让 current 指向头结点 first

E next()：让 current 往后走一步，也就是 current = current.next

E remove()：删除 current 指向的节点，删除成功后让 current 指向下一个节点

原本的类中 remove() 方法是根据传入的索引来删除节点，但在这里需要的是根据节点值来删除。可以根据 indexOf() 方法来进行删除，也可以对 remove() 方法进行改写。在此选择第二种：

public class Josephus<E> extends AbstractList<E> {
    private Node<E> current;

    @Override
    public 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> next = node.next;
            Node<E> prev = node.prev;
            prev.next = next;
            next.prev = prev;
            if (node == first) {  // index == 0
                first = next;
            }
            if (node == last) {  // index = size - 1
                last = prev;
            }
        }
        size--;
        // 返回删除的节点
        return node.element;
    }
    
    public void reset(){
        current = first;
    }

    public E next(){
        if (current == null) return null;
        current = current.next;
        return current.element;
    }

    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;
    }

    // --snip--
}

测试一下：

public class Main {

    static void josephusProblem(){
        Josephus<Integer> list = new Josephus<>();
        for (int i = 1; i <= 8; i++) {
            list.add(i);
        }
        // 指向头节点
        list.reset();
        while (!list.isEmpty()){
            list.next();
            list.next();
            System.out.print(list.remove()+" ");
        }
    }

    public static void main(String[] args) {
        josephusProblem();
    }
}