链表

链表：线性表还可以使用链式存储方式保存，即线性表中的各个元素保存在各自的存储空间中，形成一个个节点。这些结点在内存的地址不要求是相邻的，它们之间通过指针连接起来。

特点:

1. 灵活存储，不要求预先分配一块连续的空间，而是按需分配，随时需要，随时分配
2. 不要求分配的空间必须是相邻的
3. 没有容量上限，除非计算机资源耗尽

单链表

单链表是由一组动态分配的结点形成的链表，每个节点保存线性表中的一个元素及指针，指针指向保存其后继元素的结点。

可以将单例表想象成火车，火车头后面连着着一节一节的车厢（是不是很形象）

指针head指向单链表中的表头结点，head成为表头指针或头指针。每个结点中都有一个指针，指向保存其后继元素的节点。表尾元素所在结点的指针为空，表示单链表的结束。在程序中，使用null表示空指针，而在图中使用“∧"表示。

单链表中的”单“表示每个节点中仅含有一个指针。

时间复杂度

在带头结点的单链表中进行操作时，如果给定了当前指针，则插入操作和删除操作的时间复杂度均为0（1），因为操作过程中不需要进行元素的移动，也不需要将当前指针从表头后移到当前位置。

在判定单链表是否为空时，只需要查看表的头结点中指针域的值，时间复杂度也为0(1)，对于清空表操作，因为要将所有数据结点占用的空间释放，所以时间复杂度是0（n）。

对于求表长操作，如果在头结点中保存了链表的长度，则时间复杂度是0(1）。如果采用的是计数方式，即从表头开始，逐个结点进行计数，则时间复杂度为0(n)。

查找操作的时间复杂度是根据查找目标在链表中的位置而定的。若在单链表中一定能找到查找目标，则在最优的情况下，比较1次就能找到，时间复杂度为0(1）；而在最坏的情况下，需要进行n次比较，时间复杂度为0(n）。平均来看，需要查找链表的约一半元素，所以时间复杂度是0（n)。在查找失败时，查找操作的时间复杂度也是0（n）。

在线性表采用链式存储结构时，每个结点中除存储元素值以外，还需要保存一个指针。指针的空间属于额外的空间开销。对于有n个元素的线性表，若采用单链表存储，则占用的空间为nx(E+P)，其中E是结点中数据域占用的空间量，P是结点中指针域占用的空间量，用于数据的部分是nxE，属于有效部分，用于额外开销的部分是nxP，属于结构性开销。