线性表1：数组与链表
线性表（Linear List）
线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。
数组
数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
连续空间和相同数据类型这两个特性赋予了数组随机访问的能力，因为内存连续和数据类型相同使得我们可以在知晓数组起始位置的情况下通过index直接访问到数据。但是这也使得数组元素的插入与删除需要做大量的数据搬移工作。比如，删除index=i的元素，需要将i以后的数据都向前移动一个单位，插入index=i的元素，需要将原本index=i及以后的数据都向后移动一个单位。
随机访问实现
首先内存是连续的，也就是说，在构建数组的时候，整个数组是一个物理上的整体。
|0|1|2|3|4|5|6|7|8|9|
|_|_|_|_|_|_|_|_|_|_|如上我们有十个单位长度的数组，他们在一个连续的内存上面。而数组所存储的数据类型是一样的，也就是说每个单位的大小是统一且固定的。
这就使得我们可以通过index计算出该index在内存中具体的位置，假设这是一个容量为10的int数组
int[] a = new int[10]该数组的起始位置为10086，我们知道int长度是4byte，当我们需要访问index为5的元素的时候，我们可以计算出该元素的起始位置是
a[5] = 10086 + 4byte × 5结束位置是
end = 10086 + 4byte × 5 + 4byte这样我们就可以在不遍历的情况下，通过index直接访问到数据。也就是说通过index查找元素的时间复杂度是O(1)。
如何优化插入与删除
还是以上面的数组为例子，我们假设index = 0 到 8都是有数据的，我们在需要将元素插入到index=5的位置上的时候，通常需要将原本的index = 5，6，7，8元素都向后移动一位。如果我们不在乎数组的顺序，那么我们可以直接将原本index=5这个元素直接放到index=9这个位置。即：
a[9] = a[5];
a[5] = item;删除也是同理，如果我们不在乎顺序，则可以将index = 8的元素直接覆盖掉index=5，即：
a[5] = a[8]
// length - 1在另一些情况下，我们并不一定要立即执行删除操作，而是先标记好需要删除的元素，当需要删除的元素累计到一定量后再触发统一的删除操作，或者周期性触发，这就使得多次删除操作的数据移动可以合并为一次。JVM垃圾回收算法的标记清除算法就用到了这样的思想。
还是上面的例子，如果我们需要删除0，2，4位置的元素，我们可以先标记这个几个位置的元素为已删除，然后在合适的时机统一删除这三个元素，这样，我们的数据移动就大大减少了。
数组访问越界和容器
在古早的语言比如C中，访问数组是可以超过数组的最大长度的，也就是说可能访问到数组以外的数据，而Java在访问前会预先检查，如果超出了数组长度，则抛出ArrayIndexOutOfBoundsException
我们在实际使用中也是优先使用功能更强，动态扩展的容器比如ArrayList实现具体业务。只有在某些特定的情况下才考虑使用数组
- 元素只能是int这样的基本数据类型的时候，因为目前Java容器不支持基本数据类型。（Valhalla项目在解决这个问题，也许在后续更新的某个jdk版本会支持）
多维数组比容器的容器更加直观反映数据结构:
Integer [][]
List<List<Integer>>链表
前文提到数组需要连续内存，插入和删除的时间复杂度是O(n)。有时候，我们的内存可能无法获取到大块的连续内存，也需要频繁增删数据，这时候使用链表是一个不错的选择。
操作系统在管理内存的时候也无法保证给应用程序申请到足够大的物理内存。但是应用程序无法感知这一点。操作系统在逻辑上屏蔽了这些细节，逻辑地址到物理地址的映射过程对于应用程序来说是透明的。相较于数组，链表不需要连续的内存，它通过节点的指针串成一个线性表结构。
我们知道，数组的插入与删除是一个耗时的操作时间复制度是O(n)。而链表的特性刚好相反，由于无法通过公式直接获取到数据的位置，链表只能从头节点（head）或者尾节点（tail）遍历查找具体的节点，时间复杂度是O(n)，而在知晓位置节点的情况下由于不需要有数据搬移操作，链表的插入和删除要快很多，时间复杂度是O(n)。
- 插入节点：
nextNode = preNode.next
prevNode.next = node
node.next = nextNode
nextNode.prev = node
node.prev = prevNdde- 删除节点
node.prev.next = node.next
node.next.prev = node.prev
node.prev = null
node.next = null注意： 你可能也意识到了，不论是数组还是链表，我们对其的插入和删除操作都首先需要查找到具体的节点信息才能对其进行操作，比如对于数组来说，需要首先获取到index才能操作，对于链表来说需要获取到合适位置的节点信息才能操作。而他们的具体查找过程时间复杂度通常是一样的（都是O(n)），我们很少有机会可以直接获取到节点的index，对其进行操作。 对于数组来说获取到了具体的index就可以直接操作了，这是数组最大的优势，而对于链表来说，只有获取到了具体的node才能直接操作。
链表主要有以下几种实现：单链表、双向链表和循环链表。
为了较为方便的实现链表定义接口如下：
package cn.lishiyuan.algorithm.list;
/**
* 链表
* @param <T>
*/
public interface LeeList<T> {
void addFirst(T data);
void addLast(T data);
void add(int index, T data);
T removeFirst();
T removeLast();
T remove(int index);
T get(int index);
int indexOf(T data);
boolean contains(Object data);
int size();
boolean isEmpty();
}单链表
单链表是一种简单的数据结构，只有一个方向，在实际应用很少使用到。
单链表实现如下：
package cn.lishiyuan.algorithm.list;
import java.util.Objects;
/**
* 单链表实现
* @param <T>
*/
public class SingleLinkedList<T> implements LeeList<T>{
private Node<T> head = null;
private int size = 0;
public static class Node<T>{
T data;
Node<T> next;
}
public SingleLinkedList(){}
public SingleLinkedList(T data){
this.head = newNode(data);
this.size = 1;
}
@Override
public void addFirst(T data){
Node<T> node = newNode(data);
if (!isEmpty()) {
// 本节点的后继是之前的头节点
node.next = head;
}
// 本节点是新的头节点
head = node;
size++;
}
@Override
public void addLast(T data){
Node<T> node = newNode(data);
if(isEmpty()) {
// 本节点是第一个节点
head = node;
}else {
// 获取最后一个节点
Node<T> preNode = findNode(size - 1);
preNode.next = node;
}
size++;
}
@Override
public void add(int index, T data){
if(index < 0 || index > size) {
throw new IndexOutOfBoundsException();
}
// 第一个元素
if(index == 0){
addFirst(data);
return; }
// 最后一个元素
if(index == size){
addLast(data);
return; }
Node<T> newNode = newNode(data);
// 该位置的前一个节点
Node<T> preNode = findNode(index-1);
// 该位置的当前节点
if(Objects.isNull(preNode)){
throw new IllegalStateException("数据异常");
}
Node<T> nextNode = preNode.next;
// 前一个节点的后继设置为新节点
preNode.next = newNode;
// 新节点的后一个节点是当前节点
newNode.next = nextNode;
size++;
}
@Override
public T removeFirst(){
if(isEmpty()){
return null;
}
T data = head.data;
head = head.next;
size--;
return data;
}
@Override
public T removeLast(){
if(isEmpty()){
return null;
}
if(size == 1){
// 只有一个节点也就是头节点
return removeFirst();
}
// 此时最少有两个节点
// 最后一个节点的前节点
Node<T> preNode = findNode(size - 2);
if(Objects.isNull(preNode)){
throw new IllegalStateException("数据异常");
}
// 最后一个节点
Node<T> node = preNode.next;
if(Objects.isNull(node)){
throw new IllegalStateException("数据异常");
}
preNode.next = node.next;
node.next = null;
size --;
return node.data;
}
@Override
public T remove(int index){
if(isEmpty()){
return null;
}
if(index < 0 || index >= size){
throw new IndexOutOfBoundsException();
}
if(index == 0){
// 只有一个节点也就是头节点
return removeFirst();
}
if(index == (size - 1) ){
return removeLast();
}
// 此时最少有两个节点
// 查找目标位置的前一个节点
Node<T> preNode = findNode(index - 1);
if(Objects.isNull(preNode)){
throw new IllegalStateException("数据异常");
}
Node<T> node = preNode.next;
if(Objects.isNull(node)){
throw new IllegalStateException("数据异常");
}
preNode.next = node.next;
size --;
return node.data;
}
@Override
public T get(int index){
Node<T> node = findNode(index);
if(Objects.isNull(node)){
return null;
}else {
return node.data;
}
}
@Override
public int indexOf(T data){
int nowIndex = 0;
// 查找某个index的元素
for(Node<T> cur = head; cur != null; cur = cur.next){
// 查找某个data的元素
if(Objects.equals(data, cur.data)){
return nowIndex;
}else {
nowIndex ++ ;
}
}
return -1;
}
@Override
public boolean contains(Object data){
Node<T> node = findNode(data);
return Objects.nonNull(node);
}
@Override
public int size(){
return size;
}
@Override
public boolean isEmpty(){
return head == null;
}
private Node<T> findNode(int index){
if(index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
if(index == 0){
return head;
}
int nowIndex = 0;
// 查找某个index的元素
for(Node<T> cur = head; cur != null; cur = cur.next){
if(index == nowIndex){
return cur;
}else {
nowIndex++;
}
}
return null;
}
private Node<T> findNode(Object data){
// 查找某个index的元素
for(Node<T> cur = head; cur != null; cur = cur.next){
// 查找某个data的元素
if(Objects.equals(data, cur.data)){
return cur;
}
}
return null;
}
// 构建节点
private Node<T> newNode(T data){
Node<T> node = new Node<>();
node.data = data;
return node;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("size = ").append(size).append("; list = ");
builder.append("[");
Node<T> cur = head;
while(cur != null){
builder.append(cur.data);
cur = cur.next;
if(cur != null){
builder.append(",");
}
}
builder.append("]");
return builder.toString();
}
}单链表是一种使用上很不方便的结构，由于只有一个方向，在处理的时候通常需要获取目标位置的前一个节点。但是，由于只需要维护一个方向的指针（引用），在实现上又是方便的。
// 获取尾节点的前一个节点
Node<T> preNode = findNode(size - 2);
// 获取目标节点的前一个节点
Node<T> preNode = findNode(index - 1); 双向链表
双向链表通常是标准库的标准实现，Java的LinkedList就是一个双向链表。链表最常使用的实现就是双向链表。相较于单链表，它的节点维护两个方向的指针（引用），使得链表易于使用，不论是请进还是后退都很方便。也就意味着在处理的时候不再需要在目标节点的前一个位置就停下。
我们的反转链表通常也是要求我们实现双向链表的反转（涉及的引用更多）。现定义反转链表接口如下：
package cn.lishiyuan.algorithm.list;
public interface Reverse {
void reverse();
}package cn.lishiyuan.algorithm.list;
import java.util.Objects;
/**
* 双向链表
* @param <T>
*/
public class LinkedList<T> implements LeeList<T> , Reverse{
private Node<T> head = null;
private Node<T> tail = null;
private int size = 0;
public final static class Node<T>{
Node<T> prev = null;
T data;
Node<T> next = null;
}
public LinkedList(){}
public LinkedList(T data){
Node<T> node = newNode(data);
this.head = node;
this.tail = node;
this.size = 1;
}
@Override
public void addFirst(T data){
Node<T> node = newNode(data);
if (isEmpty()) {
tail = node;
}else {
// 本节点的后继是之前的头节点
node.next = head;
head.prev = node;
}
// 本节点是新的头节点
head = node;
size++;
}
@Override
public void addLast(T data){
Node<T> node = newNode(data);
if(isEmpty()) {
// 本节点是第一个节点
head = node;
}else {
// 最后一个节点
tail.next = node;
node.prev = tail;
}
tail = node;
size++;
}
@Override
public void add(int index, T data){
if(index < 0 || index > size) {
throw new IndexOutOfBoundsException();
}
// 第一个元素
if(index == 0){
addFirst(data);
return; }
// 最后一个元素
if(index == size){
addLast(data);
return; }
// 最起码有两个元素
Node<T> newNode = newNode(data);
// 该位置的当前节点
Node<T> node = findNode(index);
if(Objects.isNull(node)){
throw new IllegalStateException("数据异常");
}
// 前一个节点的后继设置为新节点
node.prev.next = newNode;
newNode.prev = node.prev;
// 新节点的后一个节点是当前节点
newNode.next = node;
node.prev = newNode;
size++;
}
@Override
public T removeFirst(){
if(isEmpty()){
return null;
}
T data = head.data;
// 如果只有一个节点
if(size == 1){
head = tail = null;
}else {
head = head.next;
head.prev = null;
}
size--;
return data;
}
@Override
public T removeLast(){
if(isEmpty()){
return null;
}
if(size == 1){
// 只有一个节点也就是头节点
return removeFirst();
}
T data = tail.data;
tail = tail.prev;
tail.next = null;
size --;
return data;
}
@Override
public T remove(int index){
if(isEmpty()){
return null;
}
if(index < 0 || index >= size){
throw new IndexOutOfBoundsException();
}
if(index == 0){
// 只有一个节点也就是头节点
return removeFirst();
}
if(index == (size - 1) ){
return removeLast();
}
// 此时最少有两个节点
// 找到该节点
Node<T> node = findNode(index);
if(Objects.isNull(node)){
throw new IllegalStateException("数据异常");
}
// 当前上个节点的下个节点是当前节点的下个节点
node.prev.next = node.next;
// 当前节点的下个节点的上个节点当前节点的上个节点
node.next.prev = node.prev;
// 其他节点不指向当前节点，当前节点也不指向其他节点
node.prev = null;
node.next = null;
size --;
return node.data;
}
@Override
public T get(int index){
Node<T> node = findNode(index);
if(Objects.isNull(node)){
return null;
}else {
return node.data;
}
}
@Override
public int indexOf(T data){
int nowIndex = 0;
// 查找某个index的元素
for(Node<T> cur = head; cur != null; cur = cur.next){
// 查找某个data的元素
if(Objects.equals(data, cur.data)){
return nowIndex;
}else {
nowIndex ++ ;
}
}
return -1;
}
@Override
public boolean contains(Object data){
Node<T> node = findNode(data);
return Objects.nonNull(node);
}
private Node<T> findNode(int index){
if(index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
if(index == 0){
return head;
}
if(index == (size-1)){
return tail;
}
// 正向还是逆向查找
int distance = size - index;
if(index > distance){
// 逆向查找
int nowIndex = size - 1;
for(Node<T> cur = tail; cur != null; cur = cur.prev){
if(index == nowIndex){
return cur;
}else {
nowIndex--;
}
}
}else {
// 正向查找
int nowIndex = 0;
for(Node<T> cur = head; cur != null; cur = cur.next){
if(index == nowIndex){
return cur;
}else {
nowIndex++;
}
}
}
return null;
}
private Node<T> findNode(Object data){
// 查找某个index的元素
for(Node<T> cur = head; cur != null; cur = cur.next){
// 查找某个data的元素
if(Objects.equals(data, cur.data)){
return cur;
}
}
return null;
}
// 构建节点
private Node<T> newNode(T data){
Node<T> node = new Node<>();
node.data = data;
return node;
}
public int size(){
return size;
}
public boolean isEmpty(){
return head == null;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("size = ").append(size).append("; list = ");
builder.append("[");
Node<T> cur = head;
while(cur != null){
builder.append(cur.data).append(",");
cur = cur.next;
}
builder.append("]");
return builder.toString();
}
@Override
public void reverse() {
if(size < 2){
return;
}
Node<T> cur = tail;
while (cur != null){
// 保存当前节点的上一个节点
Node<T> temp = cur.prev;
// 当前节点的上一个节点指向当前节点的下一个节点
cur.prev = cur.next;
// 当前节点的下一个节点指向当前节点的上一个节点
cur.next = temp;
// 此时当前节点的指针已经处理完成，而上一个节点的指针为变化，该节点的下一个节点依然指向当前节点
// 上一个节点就是下一个要处理的节点
cur = temp;
}
Node<T> t = tail;
tail = head;
head = t;
}
}这里的实现我维护了头节点（head）和尾节点（tail），在只有一个节点的时候他们是通过一个节点，在为空的时候他们都为null。所以我们在根据index查找链表节点的时候就可以根据目标index到头和尾的距离选择一个更优的遍历方向。
由于维护了head和tail，所以我们要时刻维护这两个节点的定义，在各个方法都需要注意它们。同理这里的size字段也是一样的，在每个add方法都需要size++，在每个remove都需要size--；
由于通常情况下，算法题是只给出head节点要求你反转链表与这边的实现从tail节点处理不一样，这里给出从head节点处理的方法。
@Override
public void reverse() {
if(size < 2){
return;
}
Node<T> newHead = head
Node<T> cur = head;
while (cur != null){
Node<T> temp = cur.next;
cur.next = cur.prev;
cur.prev = temp;
newHead = cur
cur = temp;
}
head = newHead;
}
循环链表
循环链表将尾节点的next指针（引用）指向头节点将链变成环。这样的结构在实现上不再依赖next指针为null判断链表已经到达尾部，可以使用next指针指向head作为判断也可以使用size判断是否到达最后一个节点。
循环链表在处理特定问题的时候是有优势的（成环的问题的模拟算法解决思路），比如解决约瑟夫问题，下面是该问题的描述：
**问题描述**
有 `n` 个人围成一圈，编号为 `1, 2, ..., n`。从编号为 `1` 的人开始报数，数到 `k` 的那个人被淘汰出局。接着从下一个人重新开始报数，再次数到 `k` 的人被淘汰。重复此过程，直到所有人被淘汰。**求最后幸存者的初始编号**。
#### **关键特性**
1. **环形结构**：人围成一圈，形成循环。
2. **固定步长淘汰**：每次从当前位置数 `k` 步，淘汰该位置的人。
3. **动态调整**：每淘汰一人后，从下一人重新计数，剩余人数减一。我们可以使用循环链表模拟这个淘汰过程，最后得到结果。当然，这是一种比较低效的算法，最优解是使用动态规划实现。
为了解决约瑟夫问题，现定义接口如下：
package cn.lishiyuan.algorithm.list;
/**
* 解决约瑟夫问题
* @param <T>
*/
public interface Josephus<T> {
T josephus(int step);
}单循环链表实现：
package cn.lishiyuan.algorithm.list;
import java.util.Objects;
/**
* 单循环链表
* @param <T>
*/
public class SingleCycleLinkedList<T> implements LeeList<T>,Josephus<T>{
private Node<T> head = null;
private Node<T> tail = null;
private int size = 0;
public static class Node<T>{
T data;
Node<T> next = null;
}
public SingleCycleLinkedList(){}
public SingleCycleLinkedList(T data){
Node<T> newNode = newNode(data);
head = newNode;
tail = newNode;
tail.next = head;
size = 1;
}
@Override
public void addFirst(T data){
Node<T> node = newNode(data);
if (isEmpty()) {
head = node;
tail = node;
tail.next = head;
}else {
// 本节点的后继是之前的头节点
node.next = head;
tail.next = node;
// 本节点是新的头节点
head = node;
}
size++;
}
@Override
public void addLast(T data){
Node<T> node = newNode(data);
if(isEmpty()) {
// 本节点是第一个节点
head = node;
tail = node;
tail.next = head;
}else {
// 获取最后一个节点
tail.next = node;
node.next = head;
tail = node;
}
size++;
}
@Override
public void add(int index, T data){
if(index < 0 || index > size) {
throw new IndexOutOfBoundsException();
}
// 第一个元素
if(index == 0){
addFirst(data);
return; }
// 最后一个元素
if(index == size){
addLast(data);
return; }
Node<T> newNode = newNode(data);
// 该位置的前一个节点
Node<T> preNode = findNode(index-1);
if(Objects.isNull(preNode)){
throw new IllegalStateException("数据异常");
}
// 该位置的当前节点
Node<T> nextNode = preNode.next;
// 前一个节点的后继设置为新节点
preNode.next = newNode;
// 新节点的后一个节点是当前节点
newNode.next = nextNode;
size++;
}
@Override
public T removeFirst(){
if(isEmpty()){
return null;
}
if(size == 1){
T data = head.data;
head = null;
tail = null;
size = 0;
return data;
}
Node<T> node = head;
T data = node.data;
head = node.next;
tail.next = head;
node.next = null;
size--;
return data;
}
@Override
public T removeLast(){
if(isEmpty()){
return null;
}
if(size == 1){
// 只有一个节点也就是头节点
return removeFirst();
}
// 此时最少有两个节点
Node<T> preNode = findNode(size - 2);
if(Objects.isNull(preNode)){
throw new IllegalStateException("数据异常");
}
// 最后一个节点
Node<T> node = preNode.next;
preNode.next = node.next;
tail = preNode;
node.next = null;
size --;
return node.data;
}
@Override
public T remove(int index){
if(isEmpty()){
return null;
}
if(index < 0 || index >= size){
throw new IndexOutOfBoundsException();
}
if(index == 0){
// 只有一个节点也就是头节点
return removeFirst();
}
if(index == (size - 1) ){
return removeLast();
}
// 此时最少有两个节点
// 最后一个节点的前节点
Node<T> preNode = findNode(index - 1);
if(Objects.isNull(preNode)){
throw new IllegalStateException("数据异常");
}
// 最后一个节点
Node<T> node = preNode.next;
preNode.next = node.next;
node.next = null;
size --;
return node.data;
}
@Override
public T get(int index){
Node<T> node = findNode(index);
if(Objects.isNull(node)){
return null;
}else {
return node.data;
}
}
@Override
public int indexOf(T data){
int nowIndex = 0;
// 查找某个index的元素
for(Node<T> cur = head; nowIndex < size; cur = cur.next , nowIndex ++){
// 查找某个data的元素
if(Objects.equals(data, cur.data)){
return nowIndex;
}
}
return -1;
}
@Override
public boolean contains(Object data){
Node<T> node = findNode(data);
return Objects.nonNull(node);
}
private Node<T> findNode(int index){
if(index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
if(index == 0){
return head;
}
int nowIndex = 0;
// 查找某个index的元素
for(Node<T> cur = head; nowIndex < size; cur = cur.next){
if(index == nowIndex){
return cur;
}else {
nowIndex++;
}
}
return null;
}
private Node<T> findNode(Object data){
int nowIndex = 0;
// 查找某个index的元素
for(Node<T> cur = head; cur != null && nowIndex < size; cur = cur.next ,nowIndex++){
// 查找某个data的元素
if(Objects.equals(data, cur.data)){
return cur;
}
}
return null;
}
// 构建节点
private Node<T> newNode(T data){
Node<T> node = new Node<>();
node.data = data;
return node;
}
public int size(){
return size;
}
public boolean isEmpty(){
return head == null;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("size = ").append(size).append("; list = ");
builder.append("[");
Node<T> cur = head;
for( int nowIndex = 0; cur != null && nowIndex < size; nowIndex ++){
builder.append(cur.data);
cur = cur.next;
if(cur != null){
builder.append(",");
}
}
builder.append("]");
return builder.toString();
}
@Override
public T josephus(int step) {
if(step <= 0){
throw new IllegalArgumentException("step <= 0");
}
if(isEmpty()){
return null;
}
if(step == 1){
tail.next = tail;
head = tail;
return tail.data;
}
// 从 -1 index开数
// 比如 [1,2,3],要从尾部开始走第一步
Node<T> cur = tail;
// 非唯一节点
while (cur != cur.next){
// 比如你要走三步，那你应该在第二步停下
for(int index = 0; index < (step - 1); index++){
// 走n步
cur = cur.next;
}
// 需要删除的节点
Node<T> node = cur.next;
// 删除当前节点
cur.next = cur.next.next;
// 处理head和tail
// 如果node是head节点，则设置head为下一个节点
if(node == head){
head = cur.next;
}
// tail是当前节点的上个节点
if(node == tail){
tail = cur;
}
size--;
}
return cur.data;
}
}循环链表通常用于解决特定问题，在大多是时候我们是使用不到该数据结构的。
上面解决约瑟夫问题的时候需要注意：
- 我们的初始位置是从-1开始（这里也就是从tail节点开始），当我们走第一步的时候才会到index=0的位置（也就是head节点）
- 我们应该在目标位置的前一个节点停下，比如步长为3，那应该在2停下，因为这是一个单向链表，进行淘汰的时候需要将需要淘汰节点的上一个节点的next指针指向需要淘汰节点的下一个节点。
评论已关闭