说明

这是一个完善了但又不完善的笔记，或许以后会更新

可以参考但请务必超越

源文件

笔记
源文件

Tools

Typora
PicGo

数据结构：顺序表和链表

雾草？为什么直接就开始了顺序表和链表？

刚搞明白数组以及类和对象，那么应该整合起来去用一用，熟悉熟悉

所以就先开始了顺序表和链表

首先先说明一下

1. 顺序表和链表，都是属于数据结构的一部分
2. C的数据结构和Java的数据结构有什么不一样？注意，数据结构是一个单独的学科，和语言没有关系。数据结构是用不同的语言，实现一样的逻辑
3. 数据结构，是逻辑非常严谨的一门学科。要想学好数据结构必须做到以下三点
   多画图、多写代码、不要抄代码！
4. 很多人学不好数据结构的原因就是眼高手低，看懂了不去写。

顺序表和链表，是数据基础的基础。非常重要！

1.线性表

线性表很简单，我们写的字符串就是

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

2.顺序表

2.1 概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

注意哦是数组存储，并不是数组。光写一个数组是不能面向对象的。

数组只是作为一个属性，你得提供方法什么的写成一个类，然后以后需要用的时候再new对象，通过对象调用方法操作数组才行。哎这就面向对象了。

• 什么是顺序表：其实底层就是一个数组。对数组进行【增删查改】

Q：那为什么还要写一个顺序表，直接用数组就好了嘛？

A：不一样，写到类里面就可以面向对象

写一个顺序表（首先提出想法）

现在有一个数组，里面是空的，我们在有12、23、34、45、56...依次向后，准备放进去

我们先放3个

那么我的有效元素（在这里可以是有效数据，有效数字）usedSize我们自己知道是3个，那电脑程序怎么知道呢？那就遍历嘛，usedSize++遇到0就停止。那如果就有一个0呢？

是不是就不能通过0来判断有效数据了，单独的数组肯定是完成不了计算的

这时，我们应该思考，写一个类，实现一个动态顺序表，提供接口，从而完成我们对数组的操作

构思轮廓框架

既然是类，使用的话肯定要new一下，那么这个类我们应该再写一个文件。

这里因为是要写顺序表，那么就起名MyArrayList。可以文档注释一下Description：顺序表

然后创建数组elem，写下构造方法，当然在构造方法中我们可以给elem开辟10个int的空间，再把我们前面的usedSize也创建好。

public int[] elem;
public int usedSize;//有效的数据个数

public MyArrayList() {
    //构造方法肯定得写
        this.elem = new int[10];
    //底层是数组，通过new对象，调用下面的一堆方法来操作数组
    //给10个int的空间
}

这时我们可以new一个对象了

MyArrayList myArrayList = new MyArrayList();

可以画图看一下现在的情况

2.2 接口实现

我们在使用Scanner的时候就可以看到，Java为我们提供了很多接口，通过文档查询我们可以看到Java提供的所有类以及接口

那么现在，我们就要实现我们自己顺序表的接口了。

既然要操作数组，那么无非就是需要写添加，插入，删除，查找，获取位置等等的方法。当然最后使用完了我们再清空掉这个顺序表

这里我们一个一个来整理，记住多画图多写代码。可以写的不一样，但是一定要多练习

在pos位置添加一个元素

现在有了框架，肯定得先添加有效数据才能操作吧

那么首先我们肯定不能在-1这样的位置放，而且如果要跳一个位置放，那肯定也不行，得保证前面是有一个元素的。其次如果空间满了，是不是就得扩容。最后如果要插入到中间，那后面的元素都需要移动。所以

1. pos不能小于0。
2. pos不能大于usedSize。
3. usedSize等于顺序表长度就需要扩容。
4. 插入需要移动元素

判断位置

if (pos < 0 || pos > usedSize) {
    System.out.println("pos 位置不合法！");
    return;
}

如果当前没有数据，usedSize就是0嘛。位置就是合法的

扩容

这里我们可以使用Arrays.copyOf()，之前数组拷贝有讲

首先判断满没满，满了就返回ture

public boolean isFull() {
    return this.usedSize == this.elem.length;
}

如果满了，扩容

if (isFull()) {
    this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
    //记得扩容后得让elem接收
}

插入

如果要插入到pos位置，后面的元素就得依次向后移动。具体的话应当是末尾位置i向前走也就是i--，然后把元素移动到i+1里面去。直到i走到pos的前面，把你要插入的数据data放到pos位置。当然别忘了usedSize++

for (int i = this.usedSize-1; i >= pos; i--) {
    this.elem[i + 1] = this.elem[i];
}
this.elem[pos] = data;
this.usedSize++;

刚开始没数据那就不进入for循环嘛，直接就放进去了

总合起来

把前面3个合起来，看一下需要接收pos和想要放入的数据这2个参数。当然只是放进去，那就不需要返回值了。

public void add(int pos, int data) {
    if (pos < 0 || pos > usedSize) {
        System.out.println("pos 位置不合法！");
        return;
    }
    if (isFull()) {
        this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
    }
    for (int i = this.usedSize-1; i >= pos; i--) {
        this.elem[i + 1] = this.elem[i];
    }
    this.elem[pos] = data;
    this.usedSize++;
}

这就是添加以及插入的方法了。我们顺序表的第一个类的方法就写好了。

如果放到奇怪的地方，就会提示位置不合法

这里我们先添加几个数据，当然如果不打印什么都显示不出来。接下来我们就写一下打印的方法。

打印顺序表

public void display() {
    for (int i = 0; i < this.usedSize; i++) {
        System.out.print(this.elem[i]+" ");
    }
    System.out.println();
}

打印就很简单了，依次打印就好了

获取顺序表长度

注意哦必须是有效数据长度，别搞混。很简单，直接return

public int size() {
    return this.usedSize;
}

判定是否包含某个元素

既然是判断，那只能是返回true和false。for循环遍历数组，要寻找的数据toFind如果等于elem[i]那就是包含，返回true，没有就返回false。

public boolean contains(int toFind) {
    for (int i = 0; i < this.usedSize; i++) {
        if (this.elem[i]==toFind) {
            return true;
        }
    }
    return false;
}

查找某个元素对应的位置

那自然是，找到返回下标 找不到返回-1。就和上面的一样，遍历查找然后返回，只不过返回的是下标

public int search(int toFind) {
    for (int i = 0; i < this.usedSize; i++) {
        if (this.elem[i]==toFind) {
            return i;
        }
    }
    return -1;
}

获取pos位置的元素

既然是pos，那就和前面一样，需要先判断位置的合法性。注意，我们需要判断有效数据是否为0。

这里就先分开写，其实可以写的更好

位置合法且顺序表不为空，那么返回elem[pos]就可以了

public int getPos(int pos) {
    if (pos < 0 || pos >= this.usedSize) {
        System.out.println("pos 位置不合法！");
    return -1;
        //这里说明一下，业务上的处理我们就先返回-1了，这里不考虑太多 后期可以抛异常
    }
    if (isEmpty()) {
        System.out.println("顺序表为空！");
        return -1;
    }
    return this.elem[pos];
}
//判断顺序表是否为空
public boolean isEmpty() {
    return this.usedSize == 0;
}

给pos位置的元素设为/更新为value

啊，就很简单。和前面一样，先判断，然后赋值就可以了

public void setPos(int pos, int value) {
    if (pos < 0 || pos >= this.usedSize) {
        System.out.println("pos 位置不合法！");
    }
    if (isEmpty()) {
        System.out.println("顺序表为空！");
        return;
    }
    this.elem[pos] = value;
}

可以看到正常改变了

那要是不正常

删除第一次出现的关键字key

终于到了删除，那么按部就班来

1. 判断顺序表是否为空
2. 查找要删的数字toRemove，他的位置是index
3. 把后面的元素依次向前移动。
   注意：i向前移动也就是i = i + 1，然后i++依次向前。但是只能i只能移动到倒数第二个有效数字。如果是倒数第一的话，假设原本空间是满的，i+1就会越界。所以i需要小于usedSize-1

public void remove(int toRemove) {
    if (isEmpty()) {
        System.out.println("顺序表为空！");
        return;
    }
    int index = search(toRemove);
    if (index == -1) {
        System.out.println("没有你要删除的数字！");
        return;
    }
    for (int i = index; i < this.usedSize - 1; i++) {
        this.elem[i] = this.elem[i + 1];
    }
    this.usedSize--;
    //this.elem[usedSize] = null;//如果数组当中是引用数据类型
}

在Java当中就很方便，这样就算是删掉了，末尾的引用也可以不置空。

那么我们来删删看

清空顺序表

注意，我们现在所讲的顺序表，其实是Java当中自带的ArrayList

我们可以自己打开ArrayList查看一下

按住ctrl点击打开，然后alt + 7查看

找到clear

那我们自己实现就是模拟原码实现嘛

注意，这个顺序表因为usedSize是有效元素所以可以直接改成0来达到清空的效果

public void clear() {
    this.usedSize = 0;
    /*for (int i = 0; i < usedSize; i++) {
        this.elem[i] = null;
    }*/
    this.usedSize = 0;
}

还有，如果存放的是引用类型，就必须使用 for循环遍历，依次删除。

2.3 顺序表的问题和思考

现在我们的这个顺序表其实是有很多问题的

1. 效率：插入和删除元素，必须要移动元素，时间复杂度可以达到O(N)
   那我们能不能在不考虑查找的情况下，不去移动元素，做到O(1)。
2. 扩容：因为是二倍扩容，那么假设，我们现在是10个容量，放满了，想放第11个。一扩容就是2倍，20个容量，那我们就放11个，以后都不放了，岂不是浪费了9个。
   能不能做到随用随取？放1个给一个空间，放2个给两个空间。（链表，满足了顺序表的缺点）

想一想，为什么会有这么多的数据结构呢？

数据结构，那就是数据加结构
结构，那就是描述和组织数据的
数据结构的种类不同，说明描述和组织数据的方式是不一样的。

顺序表，物理上和逻辑上都是连续的。链表，物理上不一定连续，但是逻辑上是连续的。

3.链表

以上看到的顺序表，当我们需要插入，添加的时候，需要移动元素。效率较低

扩容也是问题。

这时，就可以使用到链表来解决问题

从链表及以后开始，随着你知识面的增加，代码也会有很多种写法

3.1 概念及结构

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。

翻译一下就是，通过引用链接

实际中链表的结构非常多样，一下情况组合起来就有8种链表结构

• 单向、双向
• 带头、不带头
• 循环、非循环

单向带头循环、单向带头非循环、单向不带头循环、单向不带头非循环。

双向带头循环、双向带头非循环、双向不带头循环、双向不带头非循环。

本篇文章讲述的是，单向不带头非循环和双向不带头非循环。一般链表都是这样的，其他的也有但是很少。这里就以这2种来讲述。

节点

（节点和结点，没区别，节就是一节一节。结就是数据结构的结，打结的结）

我们直接来看链表的组成

链表一个一个的节点组成的

每一个节点都有一个数据域val，还有下一个节点的地址域next。

通过记录下一个节点的地址，就可以形成链表

最后一个节点不知道是谁，那就是null

head里面存储的就是第一个节点，也就是头结点的地址。那么最后一个自然就是尾节点

那么head.next存储的就是下一个节点的地址

尾节点的.next域是一个null

这个链表就是单向不带头非循环链表

写一个链表（首先实例化一个节点）

和前面的顺序表一样

我们直接开始写，先写单向的，之后再写双向的

起名MyLinkedList。可以文档注释一下Description：单链表

每一个节点都有2个域，那么我们再写一个类ListNode来代表节点

//ListNode代表一个节点
class ListNode {
    public int val;
    public ListNode next;

    //构造方法
    public ListNode(int val) {
        this.val = val;
        //设定实例化对象输入参数val对应的实体是对象中的val
    }
}

public class MyLinkedList {
    public ListNode head;
    //链表的头引用
}

这里注意next的类型是ListNode。因为存储的是下一个节点的地址嘛。head永远是属于链表的头引用，不是节点的头引用，所以定义在MyListedList里面

构造方法，我们设定val就可以了

那么ListNode这个类的写法是什么样的效果呢？

我们实例化一个节点并写个参数

ListNode listNode = new ListNode(1);

我们来看这个实例化，应该这样子的

现在next还是空的，我们不在构造方法里写next也是因为压根就没有下一个节点嘛。我们后面实现头插法和尾插法，就可以将他们一个一个串联起来了

这样使用next来指向下一个节点，只会朝一个方向去走，就是单向的，那么双向也就顾名思义是两边都能走

带头和循环，我们接下来慢慢讲

单向带头非循环链表

那么带头又是什么样的呢？

我们先画出来对比一下

可以看到，其实就是多了一个固定的节点。可以理解为，哨兵，标志节点，val值无所谓，不具备参考意见

这时如果使用头插法要加入一个新的节点

• 那么不带头的链表，就会把head向前指向新的节点（head一直在变）
• 带头的链表就会在head和下一个中间插入（head一直不变，非常简单）

有一些书上，会把带头链表的这个head节点，叫做傀儡节点，也就是没用的意思。但注意他不是真的没用，是val域没用

带头的话就太简单了，所以一般都讲不带头的

带头和不带头没有好坏，只有简单和不简单，方便和不方便。工作项目中一般也都是带头的

循环

就很好理解，最后一个节点的next域指向第一个节点。带头链表就指向第一个数据节点而不是傀儡节点

带环

只有部分节点在循环，就是带环。当然整个链表的循环也是带环，这个确实没什么好讲的。

重要的问题，会在后面的面试题中讲。

面试题很重要

3.2 链表的实现

前面顺序表开辟了空间后可以直接进行操作

那么链表的话，为了讲述和理解，我们先用穷举的方式（枚举法，穷举法）创建一个链表。这种方法显然太low了，所以只是暂时使用。后面再讲头插和尾插

比较low的创建方法

首先肯定得先使用一组数据吧

就不用管那么多，直接实例化然后连在一起

public void createList() {
    ListNode listNode1 = new ListNode(12);
    ListNode listNode2 = new ListNode(23);
    ListNode listNode3 = new ListNode(34);
    ListNode listNode4 = new ListNode(45);
    ListNode listNode5 = new ListNode(56);
}

我们现在实例化了5个节点，当然因为没有连接，所以next都是空的

连接的话，这样看就很简单

listNode1.next = listNode2;
listNode2.next = listNode3;
listNode3.next = listNode4;
listNode4.next = listNode5;

从listNode1.next开始依次指向就可以了。注意哦，前面节点刚讲了ListNode这个类的构造方法，所以不要问什么listNode5为什么不赋值null

那么listNode1就是头引用，我们把他赋值给head

this.head = listNode1;

现在的话，应该可以很好的理解next是什么样的了

打印链表

打印，现在链表已经有了，那遍历就好了嘛

注意哦，这个地方可是有坑的

我们前面将节点连起来是不是上一个节点的next等于下一个节点，也就是把下一个节点的地址赋值给上一个节点的next

那么如果要遍历，我们是不是head = head.next就可以了呀，head是头引用一定在最前面，那么head.next不就是下一个节点的地址吗。所以一直循环将下一个节点的地址赋值给当前的节点，那不就可以遍历完了。

事实确实如此

但是这样就踩坑了...

错误的写法

public void display() {
    while (this.head != null) {
        System.out.print(this.head.val+" ");
        this.head = this.head.next;
    }
    System.out.println();
}

并不是方法或操作出现了问题，关键是head一直在往后走，直到为null。

这特么，head用完一次就没了，那这链表不就寄了。啊？一次性链表？

而且还要注意一点，从图上来看

如果要使用while循环打印的话，判断条件应该写this.head != null，而不是this.head.next != null。

public void display() {
    while (this.head.next != null) {
        System.out.print(this.head.val+" ");
        this.head = this.head.next;
    }
    System.out.println();
}

如果使用this.head.next的话会少打印一个。而且图这样画，注意next，他是在节点里面的！指向的是下一个，但是next是在当前节点里面的

千万要注意

head只是写在了下面，用来表示头引用，所在的节点是头节点。千万可不能搞混，后面的引用都会这样写，方便表示。可不能把head.next误会成head！打印的时候用while循环写出this.head.next != null可是会少一个的。

正确的写法

我们为了不让head消失，使用一个cur来进行遍历等操作

public void display() {
    //this.head.next != null
    ListNode cur = this.head;
    while (cur != null) {
        System.out.print(cur.val+" ");
        cur = cur.next;
    }
    System.out.println();
}

查找

查找是否包含关键字key，关键字key是否在单链表中

前面我们刚讲了遍历的一些问题，那么就顺着来看需要遍历的方法

查找嘛，就一个一个去找

遍历，cur去找

public boolean contains(int key) {
    ListNode cur = this.head;
    while (cur != null) {
        if (cur.val == key) {
            return true;
        }
        cur = cur.next;
    }
    return false;
}

长度

得到单链表的长度

当然也是遍历，也很简单

public int size() {
    int count = 0;
    ListNode cur = this.head;
    while (cur != null) {
        count++;
        cur = cur.next;
    }
    return count;
}

头插法

前面我们创建链表，确实是比较low的创建方法

然后打印，查找和求链表长度这3种基本方法也有了

那么接下来就来讲一下头插法和尾插法，替换掉之前的创建方法

首先既然是方法，而且要输入数据，那肯定得有参数

public void addFirst(int data) {
    //我们设置输入的参数为data
}

注意，这里较为困难一点，我们画图来看

因为我们是单向不带头非循环，所以使用头插法的话head是要向前移动的对吧

好，那么现在我们要插入一个新的节点node，注意哦这个节点的引用是node，我们把他new出来

ListNode node = new ListNode(data);

我们应该要把head移动到前面对吧，当然node先要和head链接起来

这个时候，我们画仔细一点

这样看，就很清晰了

既然要先链接，那就是node.next = head

然后head向前移动head = node

这样看，是不是就很清楚了

万万不可以先head = node，不然的话head首先移动了，这个新的节点就找不到原本的节点了

千万要注意

一定记住，绑定位置的时候，一定要先绑定后面。

这样才不会丢失链表

正确的写法

那么我们的头插法也就很好写了

public void addFirst(int data) {
    ListNode node = new ListNode(data);
    node.next = this.head;
    this.head = node;
//    if (this.head == null) {
//        this.head = null
//    } else {
//        node.next = this.head;
//        this.head = node;
//    }
}

如果原本就没有链表，head = null，那么就相当于创建一个新链表嘛。

新链表就是先创建一个节点嘛，那next就是null，所以我们不用判断head是否为null。

注意看，因为是后面的插在前面，所以顺序是倒着的

下面查找和求长度也都可以用

尾插法

看过前面的头插法，尾插法就很简单了

首先我们需要用cur来遍历，从head开始遍历到最后发现cur.next == null，说明当前的节点就是末尾的节点了

注意，如果原本没有链表，那cur.next就会等于null，出现空指针异常。所以如果是创建新的链表，也就是尾插法的第一次插入，必须得判断，然后head直接等于node

头插法是后面输入的插入到前面，是逆序。尾插法，自然就是顺序的

public void addLast(int data) {
    ListNode node = new ListNode(data);
    if (this.head == null) {
        this.head = node;
    } else {
        ListNode cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }
}

任意位置插入

链表不一定是紧挨在一起的，所以我们人为的规定一下，第一个数据节点也就是头引用head为0号位置，然后1号下标，2号下标...

假设我们现在要在1和2中间插入，那么看图应该是这个样子

如果想要插进去，是需要操作前面的节点cur的next来存储node

可以看到，我们要插入到位置index = 2，就需要绑定前面cur和后面cur.next

绑定位置，一定要先绑定后面，这样才不会丢失链表

所以，也就很简单了

先node.next = cur.next把后面的绑定上，然后cur.next = node，插入新的节点

//首先确定cur
public ListNode findIndex(int index) {
    ListNode cur = this.head;
    while (index - 1 != 0) {
        cur = cur.next;
        index--;
    }
    return cur;
}
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index, int data) {
    if (index < 0 || index > size()) {
        System.out.println("index位置不合法");
        return;
    }
    if (index == 0) {
        //如果在最前面，头插
        addFirst(data);
        return;
    }
    if (index == size()) {
        //如果在最后面，尾插
        addLast(data);
        return;
    }
    ListNode cur = findIndex(index);
    ListNode node = new ListNode(data);
    node.next = cur.next;
    cur.next = node;
}

插入成功且长度加一

删除第一次出现关键字为key的节点

首先分析一下，其实和前面的任意位置插入一样

都需要使用前面一个节点cur的next

那么我们来思考一下会出现的情况

1. 当cur.next.val == key的时候，cur的下一个节点del就是要删除的节点
2. 当cur走到最后发现cur.next == null，那么说明没有要删除的元素。这时cur.next.val为空就不能使用了，否则会空指针异常
3. 当删除的是头节点的时候，cur.next.val判断不上，所以头节点要另外判断

//首先确定cur
public ListNode searchPerv(int key) {
    ListNode cur = this.head;
    while (cur.next != null) {
        if (cur.next.val == key) {
            return cur;
        }
        cur = cur.next;
    }
    return null;
}
//删除第一次出现关键字为key的节点
public void remove(int key) {
    if(this.head == null) {
        System.out.println("单链表为空，不能删除！");
        return;
    }
    if(this.head.val == key) {
        this.head = this.head.next;
        return;
    }
    ListNode cur = searchPerv(key);
    if (cur == null) {
        System.out.println("没有你要删除的节点！");
        return;
    }
    ListNode del = cur.next;
    cur.next = del.next;
}

可以看到头尾和中间都可以成功删除，最后长度为3

删除所有值为key的节点

既然有删除第一次出现的，那么就有删除全部的

注意，要求遍历链表一遍，删除所有值为key的节点

要求遍历一遍，这就上升到面试笔试的难度了

首先，需要删除的节点cur还是需要前一个节点prev

那么我们也来分析一下会出现的情况

1. 如果cur == key，那么prev.next = cur.next即可。注意这时prev不敢动。cur = cur.next继续走
2. 如果往下走发现cur != key，那么prev就可以安全的向下走了
3. 如果cur == null，那就是走到了末尾删完了
4. 如果头节点也要删，那么最后判断一下再来删除就好了。如果一开始就判断会比较麻烦，因为还有别的引用需要使用嘛

public ListNode removeAllKey(int key) {
    if (this.head == null) {
        return null;
    }
    ListNode prev = this.head;
    ListNode cur = this.head.next;
    
    while (cur != null) {
        if (cur.val == key) {
            prev.next = cur.next;
            cur = cur.next;
        } else {
            prev = cur;
            cur = cur.next;
        }
    }
    //最后处理头
    if (this.head.val == key) {
        this.head = this.head.next;
    }
    return this.head;
}

在Java中删除元素

在顺序表删除的时候，就说过了Java可以直接删掉不用置空引用

链表也一样，不需要像C语言那样，malloc开辟了空间需要free

以及后面的双链表

只要一个节点没人去引用了，那就是删除了

和局部变量一样，当一个引用cur走到最后等于null了，因为也是局部变量，所以都会回收的我们不用管

清空链表

虽然程序结束后，每一个节点都会被回收

但是如果是做项目，那项目大了去了，肯定有链表。如果是在程序运行中那肯定都浪费掉了，所以我们该怎么把每一个节点都回收掉呢

粗暴的做法

直接head = null

头节点没有引用了，那就被回收了，接着下一个节点也就没有引用了，就接着回收下去

温柔的做法

那就是一个一个节点释放喽

既然要删除，和前面操作的时候一样，肯定是需要由前一个节点的next来依次向后删除。所以说需要一个curNext先来保存，然后cur就可以放心的去了。那么既然是从头开始删除，也就不需要cur了，直接使用head

public void clear() {
    //this.head = null;//粗暴的做法
    while (this.head != null) {
        ListNode curNext = head.next;
        this.head.next = null;
        this.head = curNext;
    }
}

调式查看

一般在项目中也建议一个一个释放，我们可以来看一下运行时会产生的数据

有很多种方式可以查看，我这里就用其中一种

首先打断点，我们这里在创建好5个数据的链表处打断点，然后开启调试

可以看到我们已经开启了调试，不急着点停止，此时.class就已经在文件中产生

我们使用管理员权限打开命令提示符终端。CMD也好powershell也好，我这里用windows terminal操作

输入jps查看当前用户下Java的进程pid以及基本信息

可以看到我写的test的pid为27680

再使用jmap -histo pid查看对象的创建数量，当然可以重定向到其他文本里，我这里就直接在终端窗口打开了

第一次点回车没反应正常，我们回到idea向下走一步走过断点

此时在终端窗口就会弹出信息了，我们找一下我们写的ListNode

可以依次看到序号、实例数量、字节、类名

5个实例对应创建的5个节点，这时就可以明白确实是有在存储的

当然清空后就找不了

3.2 链表面试题

呀呀呀，数据结构，链表什么的题可太多了

我们需要着重去练习，里面的知识点也很多，尤其是重复节点的删除、回文结构等

要注意的点就是在线OJ的话后台会自动部署好一些代码，不需要我们操心

我们只需要保证代码的正确性和时间效率即可，当然如果出错了也没关系，可以根据测试用例多查看思索下，因为肯定不会只用一组数据内容来测试代码嘛

3.2.1 删除链表中等于给定值val的所有节点

删除链表中等于给定值val的所有节点

刚刚上面就写过

3.2.2 反转一个单链表

反转链表

思路：使用一个prev来记录下来前一个节点的位置，然后把prev给到下一个节点cur的next里。之后依次操作即可

当cur = null的时候就反转完成了

public ListNode reverseList() {
    if (this.head == null) {
        return null;
    }
    ListNode cur = this.head;
    ListNode prev = null;
    while (cur != null) {
        ListNode curNext = cur.next;
        cur.next = prev;
        prev = cur;
        cur = curNext;
    }
    return prev;
}

相当于一个头插法，只不过是把原来链表里的节点放到前面去。

注意，应当需要一个curNext来保存一下cur.next的位置，不然的话移动一个节点过后就会缺失cur.next

从指定头节点开始进行打印

我们现在完成了链表的反转，但是有一个问题，我们的打印方法是从头节点开始打印的，那么现在我们的头节点改变了，所以就不可以打印了

这里，我们就重新写一个display1来从指定的头节点开始打印

public void display1(ListNode newHead) {
    //this.head.next != null
    ListNode cur = newHead;
    while (cur != null) {
        System.out.print(cur.val+" ");
        cur = cur.next;
    }
    System.out.println();
}

ListNode ret = myLinkedList.reverseList();
myLinkedList.display1(ret);

3.2.3 返回中间节点

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

首先，链表长度除以2肯定是不行的，因为需要考虑测试用例中，技术和偶数的长度。还要考虑遍历次数等其他情况，因为求长度的size方法已经遍历了一遍嘛

注意，如果要达到面试的高度，那么你只能遍历单链表一遍。也就是说不能用长度方法

思路：快慢引用（快慢指针）
使用一个fast引用和一个slow引用，fast一次走2步，slow一次走1步。用物理的说法就是，匀速直线运动，时间不变，路程和速度成正比。这道题类比追及问题，移动次数一样，fast的速度是slow速度的两倍，那么fast移动的节点就是slow移动节点的二倍。fast到结尾了，slow就是在中间位置。

• 从head开始走，fast == null时，slow就在中间

这样的话链表长度奇数偶数都可以使用，且只遍历一遍

这道题说如果只有２个节点就返回第二个，那么就可以直接写。如果说明选第一个，那么就再加一个判断如果fast已经等于null了那么直接return slow 即可。

注意可不能用fast.next.next == null来判断，因为fast你可以确定，但是fast.next不能确定是不是空指针，如果fast.next是空指针那么使用fast.next.next就会空指针异常

public ListNode middleNode() {
    if (this.head == null) {
        return null;
    }
    ListNode fast = this.head;
    ListNode slow = this.head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        /*//偶数长度返回第一个
        if(fast == null) {
        return slow;
        }
        */
        slow = slow.next;
    }
    return slow;
}

3.2.4 输入一个链表，输出该链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点

要找倒数第k个，那也就是说从前往后走长度减k。假设一共5个节点找倒数第四个，那不就是正数第二个吗，从头开始走5-4也就是1个。大部分人应该也都是这么想的，当然牵扯到长度size方法，那么肯定也就要多遍历一遍

那么，和前面返回中间节点要求一样，能不能遍历链表一遍就能知道倒数第k个节点？

思路：前后引用（前后指针），还是用2个指针
我们先来找规律

• 找倒数第三个，那么从倒数第3个，到倒数第1个，走了2步
• 找倒数第四个，那么从倒数第4个，到倒数第1个，走了3步
• 找倒数第k个，那么从倒数第k个，到倒数第1个，走了k-1步

结合前面一道题，就很容易理解了

这次fast先走k-1步，然后fast和slow一起走，那fast.next == null了，也就是说fast走到了最后一个节点，这时slow所指节点就是倒数第k个。fast和slow相差k-1个嘛，就符合规律了

这样找倒数第k个就和长度无关了

这里我们写一个使用size方法的代码，不用size的话就添加上注释里面的代码

public ListNode FindKthToTail(ListNode head, int k) {
    //if (k <= 0 || k == null)
    if (k <= 0 || k > size()) {
        return null;
    }
    ListNode fast = this.head;
    ListNode slow = this.head;
    while (k - 1 != 0) {
        fast = fast.next;
        /*if (fast == null) {
            return null;
            }
        //如果没有size，就需要再判断一下
        //还有head不能为空
        */
        k--;
    }
    while (fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

一般在OJ里面都是没有size的，而且一般面试也都是遍历一遍不用size

所以我们一定要注意

3.2.5 合并有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

很好理解，我们可以再画图看看

我们把上面的头引用叫做headA，那下面的就是headB

思路：我们可让他们进行比较， 从头引用开始，然后将小的放入新的头引用newHead，然后使用一个tmp来向后走，依次往后。直到headA或headB其中一个为null了，那么也就合并完了。

public ListNode mergeTwoLists(ListNode headA, ListNode headB) {
    ListNode newHead = new ListNode(-1);
    ListNode tmp = newHead;
    while (headA != null && headB != null) {
        if (headA.val < headB.val) {
            tmp.next = headA;
            headA = headA.next;
            tmp = tmp.next;
        } else {
            tmp.next = headB;
            headB = headB.next;
            tmp = tmp.next;
        }
    }
    if (headA != null) {
        tmp.next = headA;
    }
    if (headB != null) {
        tmp.next = headB;
    }
    return newHead.next;
}

使用的话传2个头节点即可

3.2.6 以给定值x为基准分割链表

现有一链表的头指针 ListNode pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

这是什么意思呢？画图理解一下。假设有一个无序的链表，然后假设给定x = 40

这个题该如何去做呢？看起来挺难，其实也蛮简单，只要画图去理解

我们可以先分成两段链表，然后把他们合起来。

前段链表使用before start和before end，简写成bs和be

那么后段链表使用after，也就是简写成as和ae

思路：现在通过bs、be、as和ae4个引用，就可以依次来构建链表
开始的时候，4个引用都是空的，第一次，我们从原链表的头引用开始给一个引用cur和x比较。如果比x小就给到bs，be也一起，如果比x大，就给到as和ae。然后cur = cur.next往下走。当bs和as第一次都有了，接下来就使用尾插开始向后进行。最后be.next = as连起来就好

这里，还要注意2个问题

1. 所有的数据都小于x吗？也就是说bs和be没动，数据全在后面
2. 原来链表的最后一个节点一定大于x吗？也就是说最后一个节点如果小于x，该怎么处理

如果所有数据都小于x，那我们直接返回as就可以。如果最后一个节点是小于x的，那应该会是这样的情况

原本末尾节点的next是null，放到了前段链表里有了新的地址，这没什么问题。但是原本末尾节点的前一个节点就有问题了，前一个节点的next原本就是末尾节点的地址，现在他成了末尾，那应该手动置空一下

好，搞明白所有的情况，就可以开始操作了

public ListNode partition(int x) {
    ListNode bs = null;
    ListNode be = null;
    ListNode as = null;
    ListNode ae = null;
    ListNode cur = head;
    while (cur != null) {
        if (cur.val < x) {
            if (bs == null) {
                //bs的第一次
                bs = cur;
                be = cur;
            } else {
                //bs不是第一次，尾插
                be.next = cur;
                be = be.next;
            }
            cur = cur.next;
        } else {
            if (cur.val > x) {
                //as的第一次
                as = cur;
                ae = cur;
            } else {
                //as不是第一次，尾插
                as.next = cur;
                ae = ae.next;
            }
            cur = cur.next;
        }
    }
    be.next = as;//如果全都小于x
    if (as != null) {
        //如果末尾节点小于x，没有这个判断的话，在OJ里就会报出超时的警告
        as.next = null;
    }
    return bs;
}

3.2.7 删除链表中重复的节点

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。

从题目中我们应该能读出几个点

1. 重复的元素不止一个
2. 重复的元素一定是紧挨在一起的
3. 如果末尾的节点也是重复的，那么前面的next就需要置空

注意，这道题思路很重要，一定要先理清

思路：

1. 重复的元素不止一个，那么使用一个cur开始走，cur != null说明没有删除完所有重复的元素。
2. 为了保证从head开始判断，使用一个虚拟节点newHead来打头，最后返回newHead.next，那么newHead的位置就是-1，使用一个引用tmp来进行操作。
3. 然后开始判断，cur从head往后走，当cur.val != cur.next.val并且cur.next != null时，说明没有遇到重复节点也没有结束。这时tmp.next = cur可以安全的向后移动。
4. 当cur.val == cur.next.val时，说明遇到了重复节点，这时cur接着往下走，tmp停下来。直到cur.val != cur.next.val或者cur.next = null，说明tmp和cur之间就都是重复的元素了。
5. 最后不要忘了如果末尾也是重复元素，需要将前面节点的next置空。

可以看到，cur不但需要符合条件，还要接着往下走，所以需要一个if来判断符不符合条件，还需要一个while来循环往下走

虽然比较长，但是只要理解了其实就很简单，可以画图来理解

末尾也是重复元素的情况如下

public ListNode deleteDuplication() {
    ListNode cur = head;
    ListNode newHead = new ListNode(-1);
    ListNode tmp = newHead;
    while (cur != null) {
        if (cur.next != null && cur.val == cur.next.val) {
            while (cur.next != null && cur.val == cur.next.val) {
                cur = cur.next;
            }
            cur = cur.next;
            //不要忘了cur还要再走一步
        } else {
            tmp.next = cur;
            tmp = tmp.next;
            cur = cur.next;
        }
    }
    tmp.next = null;
    //删除完tmp就指向了最后一个节点，置空他的next
    return newHead.next;
}

3.2.8 链表的回文结构

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

测试样例：

1->2->2->1

返回：true

这道题是字节跳动考过的一道原题

思路：

1. 首先，相关到中间节点，那么结合前面的题可以知道应该用快慢指针。fast在末尾，slow在中间
2. 其次，后半部分的判断，需要反转next的指向才能判断。且只能使用slow不能使用fast，因为如果是偶数长度fast最后就会变成null。还需要一个引用cur来指向需要反转的节点，和一个curNext来保存反转之前的cur.next
   
3. 最后，反转之后，slow从后往前走，head从前往后走。直到2个引用相遇，通过他们的值val就可以确定是否为回文结构了。当然还有长度为偶数情况，需要判断head.next == slow
   

那么写代码的大致步骤就是：

1. 找中间节点
2. 逆置
3. 判断回文：
   奇数长度情况

偶数长度情况

public boolean chkPalindrome(ListNode head) {
    if (head == null) {
        return true;
    }
    ListNode fast = head;
    ListNode slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    //进行到这里slow走到了中间位置，开始逆置
    ListNode cur = slow.next;
    while (cur != null) {
        ListNode curNext = cur.next;
        cur.next = slow;
        slow = cur;
        cur = curNext;
    }
    //逆置完成
    while (head != slow) {
        if (head.val != slow.val) {
            //奇数
            return false;
        }
        if (head.next == slow) {
            //偶数
            return true;
        }
        head = head.next;
        slow = slow.next;
    }
    return true;
}

3.2.9 找公共节点

输入两个链表，找出它们的第一个公共结点。

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。（意思就是不能改动链表）

既然是相交，那么首先来思考两个问题

1. 相交的形状是Y还是X
2. 是值域val一样还是next域一样

其实就很简单，肯定是next域一样才会相交，那next域都一样了，后面的节点不就都一样了嘛

那必然不能是X，都相交了只有一个引用还能穿过去不成？

思路：既然要找公共节点，那么最好的方式自然是2个链表的头引用一起走直到相遇，注意如果不相交都为null也是相等的，要判断一下。所以要考虑的问题就是，2个链表的长度。长度不同那么自然就有差值，可以先让最长的链表先走过他们的差值步，然后再同时走
我们设定pl 永远指向最长的链表，ps永远指向最短的链表。不知道谁长也没关系，再换就可以了

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) {
        return null;
    }
    ListNode pl = headA;
    ListNode ps = headB;
    int lenA = 0;
    int lenB = 0;
    while (pl != null) {
        lenA++;
        pl = pl.next;
    }
    pl = headA;//注意，求完长度pl此时为null，需要重新赋值
    while (ps != null) {
        lenB++;
        ps = ps.next;
    }
    ps = headB;//同样，求完长度ps此时为null，需要重新赋值
    int len = lenA - lenB;//差值步
    if (len < 0) {
        //通过len来判断谁长谁短
        pl = headB;
        ps = headA;
        len = lenB - lenA;
    }
    //现在pl永远指向了最长的链表，ps永远指向了最短的链表。且求到了差值len步
    //那么接下来pl走差值len步就好了
    while (len != 0) {
        pl = pl.next;
        len--;
    }
    //最后同时走，直到相遇
    while (pl != ps) {
        pl = pl.next;
        ps = ps.next;
    }
    return pl;
}

3.2.10 环形链表

给定一个链表，判断链表中是否有环。

给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。

前面简单粗暴的讲了带环，因为真的就很容易理解

但是相关的题可是很重要的。就比如从这道题开始难度就加大了。

那么我们回到问题

现在这个图，后面就是一个带环，原本末尾节点的next不是null而是前面一个节点的地址

那么，代入现实中。圆形操场中，有的人跑的快，有的人跑的慢。假如一直跑下去，他们一定会相遇。这就说明操场是圆形嘛

但是，回到程序中。一个fast引用走的快，那也必须是停下来才能判断，不能说fast走一半了和较慢slow的就是相遇。有可能需要很长的时间才能相遇或者说根本无法相遇

假设有这么一个环，fast一次走3步，slow一次走1步。他们当然是都需要走相同的次数

那么fast和slow就永远无法相遇

思路：简单分析一下，就可以知道，首先slow就固定一步，fast一次走一步肯定不行，环都进不去就相遇了。那么fast最少就得一次走两步。走三步的话肯定就比两步相遇的次数多了

public boolean hasCycle(ListNode head) {
    if (head == null) {
        //虽然没说，但是我们还是应该判断下
        return false;
    }
    ListNode fast = head;
    ListNode slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) {
            return true;
            //break;
        }
    }
    /*if (fast == null || fast.next == null) {
        return false;
        }
    return true;*/
    return false;
}
//当然判断也可以写成注释内的方法，你的知识面广了怎么写都行

3.2.11 环形链表II

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。

上面一道题我们判断了是否有环，这道题我们要返回环的第一个节点。可以说这道题的难度又进一步的加大了，尤其是思路上

想一下，是否可以使用 O(1) 空间解决此题？

这道题的逻辑，很难，是一个物理数学逻辑。这道题的代码，不难

那么接下来，我们就一步一步来梳理（注意要一步不落，这是非常严谨且重要的逻辑）

画图

首先fast还是走2步，slow还是走1步

我们将前面画的图，变化成线图

注意，接下来的逻辑非常重要！

设定

可以看到上面的图简化的比较容易观察推导，标注了起始点、入口点和相遇点，而且有了X和Y2个值

那么我们先用数学的方法设定一下需要用到的值

设：

• 起始点到入口点的距离为X
• 相遇点到入口点的距离为Y
• 环的长度为C

那我们要求环的第一个节点也就是入口点

推导以及结论（很重要）

现在，我们先来算一下slow走的路程，应该是X+C-Y

同样，我们也要算一下fast走的路程，应该是X+C+C-Y。这里采用了较为极端的方法，fast一次走2步。所以这里第一圈肯定不会遇到，在第二圈遇到了

这时可能会有疑问，这用固定的条件来做逻辑，那万一fast和slow不是这样的情况呢？万一是很复杂的情况又要好多圈才相遇呢？没关系，接下来将使用一个更加严谨的逻辑来证明

fast一次2步，slow一次1步。是不是说明现在fast的速度，是slow的倍数，在这里是2倍，那么就可以列出等式

2*(X+C-Y) = X+C+C-Y 。也就是两倍的slow走的路程是fast所走的路程。这个是没问题的

将他计算下去

2*(X+C-Y) = X+C+C-Y

X+X+C+C-Y-Y = X+C+C-Y

X-Y = 0

X = Y

到这一步，其实就很清晰了。不管fast和slow他们的速度和所走路程是什么样的

fast和slow的比值（倍数）乘以slow走的路程，等于fast所走的路程

fast和slow速度已知，那等式简化后就一定是X = Y

这不就是物理的追及问题吗

那么还有问题就来了，那要是slow和fast就是要在环里转很多圈呢？

1. 思考一下，fast比较快，先进环了，slow还没进去。下一步slow就进去了，那fast会领先slow多少？也就是说当2个引用都在环里的时候，他们相差多少？
   是不是不可能差出一个圈的距离呀！

fast走的再快，他也还是在圈里，没办法和slow差出1个圈的距离吧，最极限的情况顶多也就是走的圈数要比slow多的多，相差距离非常接近一圈，但铁定是不会比这个圈大

1. 那么就又有一个等式了，假设fast的速度还是slow的二倍
   slow走的圈数和fast走的圈数抵消一下，假设fast比slow多走了N圈

2*(X+C-Y) = X+NC+C-Y
简化一下
X = (N-1)*C+Y
意思就很明显了，fast走了那么多圈，最后和slow相遇，把没意义的整圈整圈全部去掉，还是只剩下X = Y

实现

现在就很明朗了，通过物理的追及问题，以及数学的计算，推导出了X = Y

那么我们只要让2个引用分别从起始点和相遇点同时走，那么直到他们相遇的节点，就是入口点，也就是环的第一个节点

• 一个从相遇点开始，一个从头开始。一人一步走，最后相遇的地方就是入口点

public ListNode detectCycle(ListNode head) {
    if (head == null) {
        //虽然没说，但是我们还是应该判断下
        return null;
    }
    ListNode fast = head;
    ListNode slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) {
            break;
        }
    }
    if (fast == null || fast.next == null) {
        return null;
    }
    slow = head;//fast = head;都行
    while (fast != slow) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;//fast
}

3.2.12 其他

力扣链表题

力扣和牛客都还有很多的链表题，没什么好说的，刷就完事了

4.双链表

前面讲述了链表的大部分内容，还有单链表的内容

可以说相当的厚重...

接下来开始双链表，不是那么厚重，但也是很重要的

4.1 概念及结构

通过前面单链表的学习，那么其实很容易就能理解

现在在节点ListNode类中又添加了一个新的成员

前置域prev，用来保存前一个节点的地址

那这样的节点构成的链表就是双链表了

双向链表会多一个引用last，永远指向链表的最后一个节点

4.2 创建双链表

和前面单链表一样，我们写一个类MyLinkedList

唉？为什么前面单链表用了这个名字，双链表也要用呢？

这是因为，后面等到集合框架的时候，有一个集合类叫做LinkedList，他是由双向链表来组织的。所以前面单链表用这个名字其实还不太严谨

当然我这里因为都在一个项目里，所以双链表我都加一个2用来区分

4.3 实现

首先打印、求长度和查找都是一样的，就遍历嘛

我们这次就不用很low的创建方式了，直接使用头插法来创建

然后打印，求长度，查找

头插法

现在要从头新添加一个node节点

那情况就很简单，只有2种

1. 一开始没有链表，什么都没有的话，那么head和last一开始也是null，所以head和last都要移动到node这个起始位置
2. 如果现在是有链表的话，那么首先绑定后面node.next = head，原本head的prev指向node。这两步没有什么顺序，不过一般都是先绑后面，先串联起来别丢失比较重要嘛。然后就可以head = node改变头引用。当然last就不用动了

public void addFirst(int data) {
    ListNode2 node = new ListNode2(data);
    if (this.head == null) {
        this.head = node;
        this.last = node;
    }else {
        node.next = this.head;
        this.head.prev = node;
        this.head = node;
    }
}

尾插法

前面头插法正常是逆序的嘛，那么我们使用尾插法就是正序

写法当然也很类似，只不过这次操作的是last

public void addLast(int data) {
    ListNode2 node = new ListNode2(data);
    if (this.head == null) {
        this.head = node;
        this.last = node;
    } else {
        this.last.next = node;
        node.prev = this.last;
        this.last = node;
    }
}

删除第一次出现关键字为key的节点

相比单链表的删除，只不过多了一个prev

当然要删除一个节点，那么就必须找到这个节点的前驱

我们可以画图来看一下

1. 假设要删除cur节点，那么是不是就要修改前一个节点cur.prev的next和后一个节点cur.next的prev
2. 假设要删除头节点和尾节点，那cur.prev和cur.next不就空指针异常了吗。所以头节点直接head = head.next就好了
3. 只删除第一次出现关键字的节点，那删完就需要return出去
4. 假如只有一个节点。注意这个点可能会出现坑，因为可能会想不到。要删除仅有的一个节点，那prev和next都是null，使用的话就会出现空指针异常

public void remove(int key) {
    ListNode2 cur = this.head;
    while (cur!=null) {
        if (cur.val==key) {
            if (cur == head) {
                head = head.next;
                if(head != null) {
                    //如果只有一个节点
                    head.prev = null;
                }else {
                    //如果只有一个节点，last也要置空
                    last = null;
                }
            } else{
                cur.prev.next = cur.next;
                if (cur.next != null) {
                    //中间位置
                    cur.next.prev = cur.prev;
                } else {
                    last = last.prev;
                }
            }
            return;
            //干掉return就会删除所有值为key的节点
        }
        cur = cur.next;
    }
}
//当然写成else if也可以

这里关于删除，我们看到如果是要删除末尾的节点，那末尾节点的prev是不用管的，上面在Java中删除元素也说过。末尾节点没人引用了，cur是引用但也是局部变量，最后就都会被回收掉

删除所有值为key的节点

要删除所有的，就简单了嘛

前面是只删除第一个出现的，删除完就return了，那我们不return不就完事了

任意位置插入

任意位置插入，第一个数据节点为0号下标

根据前面的单链表来看

最前面插就是头插，最后面插就是尾插

那问题是在中间插入

看图得知我们需要修改4个位置

那现在我们要插入一个新的节点node，直接让cur走到要插入的位置就好了（插入完cur就变成后面的节点了嘛）

然后修改的顺序，当然是先把后面的绑上，那就是先改next，所以从1开始，然后是2。绑上之后就可以进行3和4了。当然也可以是其他顺序，不过一般推荐都是这样

//确定cur的位置
public ListNode2 searchIndex(int index) {
    ListNode2 cur = this.head;
    while (index != 0) {
        cur = cur.next;
        index--;
    }
    return cur;
}
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index, int data) {
    ListNode2 node = new ListNode2(data);
    if (index < 0 || index > size()) {
        System.out.println("index位置不合法！");
        return;
    }
    if (index == 0) {
        addFirst(data);
        return;
    }
    if (index == size()) {
        addLast(data);
        return;
    }
    ListNode2 cur = searchIndex(index);
    node.next = cur;//cur.prev.next
    cur.prev.next = node;
    node.prev = cur.prev;
    cur.prev = node;
}

清空链表

清空的话，那我们还是温柔的好！

操作的话也就很简单了，从head开始往后置空，当然需要一个curNext保存一下下一个节点位置。最后last置空

public void clear() {
    while (head != null) {
        ListNode2 curNext = head.next;
        head.prev = null;
        head.next = null;
        head = curNext;
    }
    last = null;
}

5. 顺序表和链表的区别及联系

一般面试会有如下的问题

1. 顺序表和链表的区别
2. 数组和链表的区别
3. ArrayList和LinkedList的区别

其实这就是一个问题

首先，ArrayList和LinkedList是集合框架当中的两个类。集合框架就是将所有的数据结构封装成了Java自己的类。那就方便了，以后如果需要用就直接用

目前的话当然还没有特别细致的完整了解，以后就都会知道了

那么这里，就有一个面试技巧了

当面试官问到什么和什么的区别的时候，一定记住要从共同点出发

因为共同点肯定只有一个嘛，那不是共同点就都是区别喽

组织

顺序表底层是一个数组，他是逻辑上和物理上（内存）都是连续的数据结构

链表是一个由若干节点组成的数据结构，逻辑上是连续的，但是在物理上（内存上）是不一定连续的

操作

顺序表适合查找相关的操作，因为可以直接使用下标获取某个位置的元素

链表适合频繁的插入和删除操作，只需要修改指向即可

总结一下

根据上面的好处，可以简单总结出来

顺序表：

• 好：空间连续、支持随机访问
• 坏：一是中间或前面部分的插入删除时间复杂度O(N)。二是增容的代价比较大。

链表：

• 好：一是任意位置插入删除时间复杂度为O(1)。二是没有增容问题，插入一个开辟一个空间（要用就new一个）。
• 坏：以节点为单位存储，不支持随机访问

小头图版权：《再生》by 紺屋鴉江 2021年11月7日下午2点20分 pid：93976900