第4章 链表

4.1 链表的基础知识

链表是一种常见的基础数据结构。在链表中，每个节点包含指向下一个节点的指针，这些指针把节点连接成链状结构。

在创建链表时无须事先知道链表的长度。链表节点的内存分配不是在创建链表时一次性地完成，而是每添加一个节点分配一次内存。当插入一个节点时，只需要为新节点分配内存，然后通过调整指针的指向来确保新节点被链接到链表中。这样，链表就能实现灵活的内存动态管理，可以充分地利用计算机的内存资源。

和数组相比，链表更适合用来存储一个大小动态变化的数据集。如果需要在一个数据集中频繁地添加新的数据并且不需要考虑数据的顺序，那么可以用链表来实现这个数据集。链表中的插入操作可以用O（1）的时间来实现。

由于链表中的内存不是一次性分配的，因此链表节点在内存中的地址并不是连续的。如果想在链表中找到链表的第i个节点，就只能从头节点开始朝着指向下一个节点的指针遍历链表，它的时间效率为O（n）。而在数组中，根据下标用O（1）的时间就能找到第i个元素。

链表的创建、插入节点、删除节点等操作都只需要20行左右的代码就能实现，其代码量比较适合作为面试题。由于链表是一种动态的数据结构，其操作是针对指针进行的，因此应聘者需要有较好的编程功底才能编写出正确的操作链表的代码。另外，链表这种数据结构很灵活，面试官可以用链表设计出具有挑战性的面试题。基于上述几个原因，与链表相关的题目深受面试官的青睐。

大多数出现在算法面试题中的链表都是单向链表。单向链表的节点包含指向下一个节点的指针，因此单向链表的节点可以定义为如下形式：