线性表的链式存储结构

线性表的链式存储结构

链表：用链式存储结构存储的线性表。

链表的特点：

（1）用一组任意的存储单元来存储线性表的数据元素，不要求逻辑上相邻的两个数据元素物理上也相邻，这组存储单元可以是连续的，也可以是不连续的。

（2）线性表中任意一个数据元素以结点的形式进行存储。结点包括两部分信息，其一为数据域，存储数据元素。其二为指针域，用以存储相邻结点的存储地址。指针域可以只有一个，用它来存储的直接后继结点的存储地址。也可以有两个，其中一个指针域存放的直接后继的存储地址，另一个指针域存放的直接前驱的存储地址。

（3）指针域中存储的信息称作指针或链。

n个结点链接成一个链表，即为线性表的链式存储结构。采用链式存储结构的线性表称为链表（Linked List）。

（4）链表是通过“链”建立起数据元素之间的逻辑关系，因此插入、删除操作不需要移动数据元素，不能随机存取。

链表如何表示线性表中元素之间的逻辑关系?

链表是用一组任意的存储单元来存放线性表的结点，线性表的逻辑关系是利用指针来体现，结点的逻辑次序与物理次序不一定相同。链表是通过每个结点的指针域将线性表的n个结点按其逻辑次序连接在一起。