链式存储结构
结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻
线性表的链式表示又称为非顺序映像或链式映像。
如何实现？
相关术语
-
各结点由两个域组成：
- 数据域：存储元素数值数据
- 指针域：存储直接后继结点的存储位置
-
结点：数据元素的存储映像。由数据域和指针域两部分组成
-
链表：n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。
-
单链表、双链表、循环链表：
结点只有一个指针域的链表，称为单链表或线性链表
有两个指针域的链表，称为双链表
首尾相接的链表称为循环链表
循环链表示意图：
- 头指针、头结点和首元结点
头指针是指向链表中第一个结点的指针
首元结点是指链表中存储第一个数据元素a1的结点
头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息
上例链表的逻辑结构示意图有以下两种形式：
问题讨论
如何表示空表？
有头结点时，当头结点的指针域为空时表示空表
在链表中设置头结点有什么好处？
- 便于首元结点的处理
首元结点的地址保存在头结点的指针域中,所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理; - 便于空表和非空表的统一处理
无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了。
头结点的数据域内装的是什么？
头结点的数据域可以为空，也可存放线性表长度等附加信息，但此结点不能计入链表长度值。
链表（链式存储结构）的特点
（1）结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻
（2）访问时只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等
链表的优缺点
优点
- 数据元素的个数可以自由扩充
- 插入、删除等操作不必移动数据，只需修改链接指针，修改效率较高
缺点
- 存储密度小
- 存取效率不高，必须采用顺序存取，即存取数据元素时，只能按链表的顺序进行访问（顺藤摸瓜）
