共计 2179 个字符，预计需要花费 6 分钟才能阅读完成。
简介
链表是一种和数组不同的线性表构造，数组的存储应用了一组间断的内存空间，而链表通过链接的形式将零散的内存空间串联起来应用。
链表的定义须要留神两点：链表依然是一个线性表构造；链表不应用间断的内存空间进行存储。
因而，链表克服了数组须要事后晓得数据大小的毛病，并且能充沛利用计算机内存空间，实现灵便的内存动静治理。
但链表也失去了疾速随机存取的长处，同时因为减少了结点的指针域，空间开销较大。
基本概念
链表是通过指针将零散的内存块串联在一起的，这里的内存块被称为链表的 结点。
结点除了存储数据之外，还会存储下一个结点的地址，这个记录下一个结点地址的指针被称为 后继指针 。在双向链表中，还会存储上一个结点的地址，这个记录上一个结点地址的指针被称为 前驱指针。
链表中存在两个比拟非凡的结点，别离是第一个结点和最初一个结点。因而也给这两个结点取了名称，第一个结点被称为 头结点 ，最初一个结点被称为 尾结点。
随机存储
把链表和数组作比拟，数组具备疾速随机存取的长处，而链表是随机存取效率非常低的数据结构。
如果通过下标去拜访链表中的结点，是不能应用寻址公式的，只能通过头结点作为入口，依据指针一个结点一个结点地顺次遍历，直到找到对应的结点。
综合计算下来，链表做随机拜访的工夫复杂度为 $O(n)$，效率比数组低得多。
插入、删除
尽管链表没有了数组随机存取的长处，但在插入、删除结点的时候，效率比数组高很多。
假如，要在链表中插入一个结点，在晓得插入地位的前后两个相邻结点的前提下，只需将新结点的后继指针指向下一个结点，而后将上一个结点的后继指针指向这个新结点，即可实现插入结点的操作。删除结点也是相似的操作，十分不便。
然而，插入、删除结点时效率高的前提是晓得操作地位的相邻结点，否则仍须要从头结点开始寻找到对应地位，这样的效率会非常低。
形形色色的链表
链表有很多不同的类型，在下面说的都是最简略的单向链表，简单一点的还有双向链表、循环链表。
单向链表
单向链表是最简略的链表构造，它蕴含两个域，一个信息域和一个指针域。
信息域存储理论的数据，指针域存储此结点的下一个结点地位。
在理论编码中，为了不便，头结点的信息域是空的，其指针域存储理论的第一个结点所在位置，尾结点的指针域个别会是 NULL 地址。
双向链表
双向链表是在单向链表的根底上多减少了一个指针域，这个新减少的指针域会存储上一个结点所在位置。
也就是说，在双向链表中，除头结点的任意结点都能够拜访到上一个结点，因而称为双向链表。
双端链表
双端链表与双向链表是齐全不同的两个概念。
双端链表是在单向链表的根底上，减少了尾结点的援用。领有这个援用的双端链表在尾部插入结点时特地不便，因而常被用作实现链式队列。
尽管双端链表能够不便地在尾部插入结点，但因为无奈快捷地获取倒数第二个结点，因而依然不能不便地删除尾结点，若须要此性能还是要靠双向链表实现。
循环链表
循环链表是一个头结点和尾结点连贯在一起的非凡链表，通过单向链表或双向链表都可能实现。
循环链表的长处就是从链表的尾结点到头结点十分不便，也不便解决具备环形构造特点的数据，如约瑟夫问题。
块状链表
快状链表自身是一个链表，然而链式存储的并不是个别的数据，而是由一些数据组成的程序表结点，这些结点也被称作块。
块状链表通过应用可变的程序表的长度和非凡的插入、删除的形式，能够达到 $O(\sqrt{N})$ 的工夫复杂度。
块状链表的另一个特点是绝对一般链表来说更节俭内存，因为不必保留指向每一个数据结点的指针。
应用上的问题
数组和链表如何抉择
仅个性和效率而言，数组领有疾速随机拜访的个性，链表能够疾速插入、删除。常常利用下标拜访元素能够应用数组，常常插入、删除元素能够应用链表。
然而，不能仅仅只用复杂度剖析决定应用哪种数据结构。数组简略易用，而且可能借助 CPU 缓存机制预读数组中的数据；而链表在内存中不是间断存储的，对 CPU 缓存不敌对，没方法无效预读。
数组的毛病是数据大小固定，而且一经申明要占用整块间断内存空间，如果申明的数组过大，零碎可能没有足够的间断内存空间调配给它。即便是在 Java 中应用能够动静扩容的 ArrayList 类型，也存在扩容耗时的问题。而链表自身没有大小的限度，天生反对动静扩容。
实现链表的技巧
编写一个正确的链表是比拟难的，然而其中也有一些技巧：
- 了解指针或援用的含意。将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，这个内存地址存储这个变量，通过指针能找到这个变量
- 警觉指针失落。插入结点时，先将插入结点的后继指针指向下一个结点，再把前一个结点的指针指向插入结点，这样才不会失落指针
- 防止内存透露。删除结点时，要记得手动开释内存空间
- 利用哨兵简化实现难度。在理论开发当中，如果向空链表中插入第一个结点的时候，还须要判断链表中是否曾经存在头结点，嵌入代码比较严重；然而，如果减少一个哨兵结点，哨兵结点的后继指针指向头结点，则能够省略这一步操作
- 重点注意边界条件解决。当链表为空的时候，代码是否能失常工作？当链表只有一个结点的时候，代码是否能失常工作等等
- 举例画图，辅助思考。链表的指针指向会比较复杂，这种状况能够通过举例画图的方法将各种状况列举进去，这样思路会更加清晰
- 多写多练，游刃有余。写链表代码是十分考验逻辑思维能力的，多多尝试练习能够进步逻辑思维能力
