链表是一种物理存储单元上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列节点（链表中的每个元素称为节点）组成，节点可以在运行时动态生成。每个节点包括两部分：一个存储数据元素的数据域，另一个是存储下一个节点地址的指针域。相比于线性表顺序结构，链表操作略微复杂。由于不必按顺序存储，链表在插入的时候可以达到O(1)的时间复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。 使用链表可以解决数组需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了节点的指针域，空间开销比较大。链表最明显的好处是：常规数组排列关联项目的方式可能不同于这些数据在记忆体或磁盘上的顺序，数据的存储往往要在不同的排列顺序中转换。而链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。 数据元素随机存储，并通过指针表示数据之间逻辑关系的存储结构就是链式存储结构。 链表实际存储的是一个一个的节点，真正的数据元素包含在这些节点中，链表包含数据域和指针域，不是单一的数据类型和结构，因此链表中每个节点的具体实现，在C语言中使用结构体。
线性表的链式存储表示的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此为了表示每个数据元素与其直接后继元素之间的逻辑关系，对数据元素来说，除了存储其本身的信息之外，还需存储一个指向其直接后继元素的信息（即直接后继元素的存储位置）。由这两部分信息组成一个节点，表示线性表中的一个数据元素。线性表的链式存储表示，有一个缺点就是要查找一个数据元素，必须从头开始找起，非常麻烦。 对于非线性链表可以参见其他数据结构，例如树，图。另外一种基于多个线性链表的数据结构：跳表。其插入，删除，查找等基本操作可以达到O(nlogn)和平衡二叉树一样。 链表中存储数据元素的于被称作数据域，存储直接后继指针元素位置的域称为指针域（next指针）。指针域中存储的信息又称作指针或链。所以链表的基本思路是，利用struct结构体的设置，额外开辟出一份内存空间作为指针，它总是指向下一个节点，一个一个节点通过next指针相互串联，就形成了链表。其中数据域是自定义的数据类型，next为指向下一个链表节点的指针，通过访问next，可以引导我们去访问链表的下一个节点。
循环链表与单链表一样，是一种链式的存储结构，所不同的是，循环链表的最后一个节点的指针是指向该循环链表的第一个节点或者头节点，从而构成一个环形的链。 循环链表的运算与单链表的运算基本一致。所不同的有以下几点：
- 在建立一个循环链表时，必须使其最后一个节点的指针指向头节点，而不是像单链表那样设置为NULL。此种情况还适用于在最后一个节点插入一个新的节点。
- 在判断是否到表尾时，是判断该节点指针域的值是否是头节点，当指针域的值等于头指针时，说明已到表尾。而非像单链表一样判断指针域的值是否为NULL。
单链表是指节点中只有一个指向其后继元素的指针，具有单向性，但是有时需要搜索大量数据的时候，就需要从头开始遍历，搜索不是很搞笑。因此双向链表其实是对单链表的改进。在单链表的基础上，对于每个节点设计一个前驱指针，前驱指针与前一个节点相连，构成一个链表，这就是双向链表了。所以从双向链表中的任意一个节点开始，都可以很方便地访问它的前驱节点和后续节点。 当我们对单链表进行操作时，你要对某个节点的直接前驱元素进行操作时，必须从表头开始查找。这是由于单链表节点的结构所限制的。因为单链表每个节点只有一个存储直接后继元素地址的指针域，那么能不能定义一个既有存储直接后继元素地址的指针域，又有存储直接前驱元素地址的指针域的这样一个双指针域结构呢？这就是双向链表。 在双向链表中，节点除含有数据域外，还有两个指针域，一个存储直接后继元素节点地址，一般称为右指针域；一个存储直接前驱元素节点地址，一般称为左指针域。
一条完整的链表由以下几个部分组成：
- 头指针：一个普通的指针，它的特点是永远指向链表第一个节点的位置。头指针用于指明链表的位置，便于后续找到链表并使用表中的数据。
- 节点：链表中的又细分为头节点，首元节点和其他节点：
- 头节点：不存在任何数据的空节点，通常作为链表的第一个节点。对于链表来说，头节点不是必须的，它的作用只是为了方便解决某些实际问题。
- 首元节点：由于头节点是空节点的缘故，链表中第一个存有数据的节点为首元节点。
- 其他节点：链表中的其他节点。 因此一个完整的链表结构如图： ![[Pasted image 20220405211318.png]] 注意：链表中有头节点时，头指针指向头节点；反之，链表中没有头节点时，头指针指向首元节点。
- 解决数组无法存储多种数据类型的问题。
- 解决数组中，元素个数无法改变的限制。
- 数组移动元素的过程中，要对元素进行大范围的移动，很耗时间，效率也不高。