作者：孙玉昌，昵称【一一哥】，别的【壹壹哥】也是我哦

千锋教育高档教研员、CSDN博客专家、万粉博主、阿里云专家博主、优质作者

前言

除了一些算法之外，咱们还有掌握一些常见的数据结构，比如数组、链表、栈、行列、树等结构。在之前的文章中，壹哥已经带着咱们学习了Java里的一维数组和多维数组，所以对此我就不再细述了。接下来我会给咱们讲解一下线性结构中的链表，期望你能喜爱哦。

——————————前戏已做完，精彩即开端—————————-

全文大约【3200】 字，不说废话，只讲能够让你学到技能、明白原理的纯干货！本文带有丰厚的事例及配图视频，让你更好地了解和运用文中的技能概念，并能够给你带来具有足够启迪的考虑……

配套开源项目资料

Github：GitHub – SunLtd/LearnJava

Gitee：一一哥/从零开端学Java

一. 链表简介

1. 概念

线性表能够说是一种最根底最简略的数据结构，它表明的是一种线性结构，比较常见的线性结构包含数组和链表等。

所谓的链表，望文生义，便是链式的线性表，即链表也是一种线性表。与数组不同的是，链表采用的是链式存储，这种链式结构是非接连、非次序的内存空间。链表中的每一个独立的元素被称为结点，故链表由一系列的结点组成。

其间链式存储的意义如下：

假如咱们需求寄存一堆物品，但没有足够大的空间将一切的物品一次性放下，此时该怎么既放下一切的物品，又能简略的找到一切的物品方位呢？咱们能够测验采用如下解决方案：寄存物品时，每放置一件物品就在该物品上贴一个小纸条，标明下一件物品放在哪里。这样，咱们只需求记住第一件物品的方位，从第一件物品上的小纸条，就能够找到第二件物品，再依据第二件物品纸条的内容就找到第三件物品。按照这个方法顺次类推，咱们便能够找到一切的物品，这便是所谓的链式存储。

2. 表明方法

链表中的每个结点都由两部分组成：数据域、指针域。数据域用来寄存当时结点需求存储的数据内容，指针域用于寄存当时结点的下一个结点的地址。如下图所示：

图1-链表的结构示意图

上图所示的节点细节如下：

• 首个结点中next1寄存的是第二结点的内存地址，因而用一个箭头指向第二个结点，就能够表明两个结点之间的关系。
• 最终一个结点的后边不再有其他结点，因而最终结点的next5指针域中没有地址内容，编程中能够用null表明。

3. 特点

经过上文所述，壹哥就能够给咱们总结出链表的主要特点：

(1). 从内存结构来看，链表的内存结构是不接连的内存空间，是将一组零星的内存块串联起来，然后进行数据存储的数据结构；

(2). 链表由一系列结点组成，每个结点包含两个部分，一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。链表中数据元素的逻辑次序便是经过地址指针实现的；

(3). 链表和数组相比，内存空间耗费更大，由于每个存储数据的结点都需求额外的空间存储地址指针。

二. 链表分类

在工作实践中，开发者接触到的链表主要有三种：单向链表、双向链表、循环链表。下面壹哥给咱们逐一进行介绍一下。

1. 单向链表

单向链表的每一个结点包含两部分，一部分是寄存数据的变量data，另一部分是指向下一个结点的指针next。 单链表只能单向读取，其结构如下所示：

图2-单向链表结构示意图

咱们以Java为例，给出单向链表的结构界说：

class Node{
    Object value;
    Node next;
}

2. 双向链表

双向链表，表明链表结点由三部分组成：数据域、下一结点指针域、前一结点指针域。 在双向链表结构中，既能够从首个结点动身，依据下一结点指针域顺次找到一切结点；同理，也能够从指定的某个结点，依据结点中的前一结点指针地址，向前顺次得到前面的结点。具体地，双向链表的结构示意图如下所示：

图3-双向链表结构示意图

如上图所示：

• 第1个结点作为整个链表的首结点，该结点的prev1指针内容为null，表明没有前一个结点。
• 第5个结点作为整个链表的最终结点，next5指针内容为null，表明后续没有下一个结点。
• 除此之外，中心三个结点，next指针和prev指针别离指向下一个结点和前一个结点，能够实现双向查找。

使用Java进行双向链表的结点结构界说如下：

class Node{
    Object value;
    Node next;
    Node prev;
}

3. 循环链表

假如，咱们将链表的最终结点的next指针域做下修正，由原来的指向null修正为指向第1个结点，则整个链表就变成了一个环路。以单向链表进行操作，如下图所示：

图4-单向循环链表明意图

如上图，每个结点有数据域和指针域两个部分，这种循环链表被称之为单向循环链表。在计算机领域中，单向循环链表又称约瑟夫环（Josephu Loop），这一点仅做了解即可。当然，双向链表也能够调整为循环的链表，被称之为双向循环链表，如下图所示：

图5-双向循环链表明意图

三. 存储原理

数组在内存中的存储方法是次序存储（接连存储），链表在内存中的存储方法则是随机存储，如下图所示：

图6-链表的内存存储示意图

链表的每一个结点散布在内存的不同方位，依托next指针关联起来。这样能够灵敏有效地利用零星的碎片空间。链表的第一个结点被称为头结点，没有任何结点的next指针指向它，它的前置结点为空null。头结点用来记载链表的基地址。有了它，就能够遍历得到整条链表的数据。链表的最终一个结点被称为尾结点，它的next指向为空null。

四. 链表常见操作

本篇文章内容，咱们以单向链表为例，介绍链表的常见操作，主要包含：查找结点、更新结点、刺进结点和删去结点等操作。

1. 查找结点

在查找元素时，链表只能从头结点开端向后，一个结点一个结点逐一查找，如下图所示：

图7-单向链表查找结点示意图

时刻复杂度剖析，分两种状况：

• 查找头结点：头结点是链表的第一个结点，直接就能得到结果，因而查找头结点时刻复杂度是O(1)。
• 查找非头结点：假如查找非头结点，则需求从头结点向后顺次查找，知道整个链表的结尾，因而查找非头结点的其他结点时，时刻复杂度是O(n)，最坏状况下时刻复杂度也是O(n)。

2. 更新结点

更新结点操作需求两个过程：

• 找到要更新的结点；
• 将旧数据替换成新数据。

如下图所示：

图8-单向链表更新结点数据操作示意图

与查找结点操作时刻复杂度状况相似，更新时刻复杂度分两种状况：

• 更新头结点：单向链表更新头结点的时刻复杂度是O(1)；
• 更新非头结点：更新其他结点的最坏状况时刻复杂度是O(n)。

3. 刺进结点

3.1 尾部刺进

尾部刺进即把最终一个结点的next指针指向新刺进的结点即可，如下图所示：

图9-单向链表尾部刺进结点示意图

时刻复杂度剖析：如上图所示，若尾部刺进结点，则需求从头开端遍历，因而单向链表增加尾结点的时刻复杂度是O(n)。

3.2 头部刺进

头部刺进新结点需求两个过程：

(1). 把新结点的next指针指向原先的头结点；

(2). 把新结点变为链表的头结点。

如下图所示：

图10-单链表头部刺进结点示意图

时刻复杂度剖析：由于直接将新节点的指针域指向头结点即可完结操作，因而增加头结点的时刻复杂度是O(1)。

3.3 中心刺进

在链表的中心方位刺进结点同样需求三步：

(1). 从头结点开端向后查找，找到要刺进的结点的方位；

(2). 新结点的next指针指向刺进方位的结点；

(3). 刺进方位前置结点的next指针指向新结点；

示意图如下：

图11-单向链表中心方位刺进结点

时刻复杂度剖析：若履行刺进结点操作，首要需求从头结点向后查找，找到要刺进的方位。很明显，与链表的规模有关，因而中心刺进结点操作的时刻复杂度是O(n)。

4. 删去结点

4.1 尾部删去

若期望删去链表的最终一个结点，只需求将倒数第二个结点的指针域指向null即可，如下图所示：

图12-单向链表尾部删去结点示意图

时刻复杂度剖析：由于要从头开端遍历，所以单向链表删去尾结点的时刻复杂度是O(n)。

4.2 头部删去

头部删去与头部刺进操作相似，只需求把链表的头结点设为原先头结点的next指针即可如图：

图13-单向链表头部删去结点示意图

时刻复杂度剖析：删去头结点的时刻复杂度也是O(1)。

4.3 中心删去

中心方位删去结点操作相似于中心刺进操作，需求三步：

(1). 从头结点开端向后，找到要删去结点的方位；

(2). 找到删去结点的前一个结点和后一个结点；

(3). 即将删去结点的前置结点的next指针，指向要删去元素的下一个结点；

如下所示：

图14-单向链表中心删去结点示意图

时刻复杂度剖析：由于需求从头结点开端进行查找，因而时刻复杂度与链表的规模有关，故单向链表删去中心方位结点的时刻复杂度是O(n)。

——————————正片已结束，来根事后烟—————————-

五. 结语

本篇文章，咱们一起学习了链表的概念，认识了单向链表、双向链表、循环链表等不同的链表类型。并以单向链表为例，剖析了链表中的结点炒作及对应的时刻复杂度剖析，不知道你现在对链表了解了吗？

别的假如你独自学习觉得有很多困难，能够参加壹哥的学习合作群，咱们一起交流学习。