数据结构 - 链表

为什么需要链表

顺序表的构建需要预先知道数据大小来申请连续的存储空间，而在进行扩充(插入、删除)时又需要进行数据的搬迁，所以使用起来并不是很灵活。

链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。

链表的定义

链表（Linked list）是一种常见的基础数据结构，是一种 线性表的链式存储结构，存储地址空间不需要是连续的，而是在每一个节点（数据存储单元）里存放下一个节点的位置信息（即地址）。

链式存储有关的术语

• 结点： 数据元素的存储映像。由数据域和地址域两部分组成。
• 链表： n个结点由 指针链 组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。

单向链表

单向链表也叫单链表，是链表中最简单的一种形式，它的每个节点包含两个域，一个数据域和一个链接域(地址域)。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值（通常用 NULL 或 ^ 表示）。

单链表

• 数据域 data 用来存放具体的数据。
• 链接域 next 用来存放下一个节点的位置。
• L 指向链表的头节点（首节点）的位置，从 L 出发能找到表中的任意节点。

单向循环链表

单向循环链表

• 数据域 data 用来存放具体的数据。
• 地址域 next 用来存放下一个节点的位置，但最后一个结点的地址域要存储链表头结点的地址。

优点： 从链表中的任一个结点出发均可找到链表中其他结点。

双向链表

一种更复杂的链表是 双向链表。每个结点有两个链接：一个指向前一个节点（当此节点为第一个节点时，指向空值），而另一个指向下一个节点（当此节点为最后一个节点时，指向空值）。

双向链表

• 数据域 data 用来存放具体的数据。
• 地址域 pre 用来存放前一个节点的位置，地址域 next 用来存放下一个节点的位置。

优点： 方便找链表中的某个结点的前驱结点。

小扩展

头指针

• 头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针。
• 头指针具有标识作用， 所以常用头指针冠以链表的名字。
• 无论链表是否为空，头指针均不为空。头指针是链表的必要元素。

头结点

• 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义(也可存放链表的长度)。
• 有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其它结点的操作就统一了。
• 头结点不一定是链表必须要素。