|
|
|
线性表的链式存储是用结点来存储数据元素，元素的结点地址可以连续，也可以不连续，因此，存储数据元素的同时必须存储元素之间的逻辑关系。另外，结点空间只有在需要的时候才申请，无须事先分配。基本的结点结构如下所示：
|
|
|
|
|
|
结点中的数据域用于存储数据元素的值，指针域则存储当前元素的直接前驱或直接后继元素的位置信息，指针域中所存储的信息称为指针（或链）。
|
|
|
|
n个结点通过指针连成一个链表，若结点中只有一个指针域，则称为线性链表（或单链表），如下图（a）所示。
|
|
|
|
|
|
|
|
在链式存储结构中，只需要一个指针（称为头指针，如上图（b）中的Head）指向第一个结点，就可以按照链接关系顺序地访问表中的任意一个元素。为了简化对链表状态的判定和处理，特别引入一个不存储数据元素的结点，称为头结点，将其作为链表的第一个结点并令头指针指向该结点。
|
|
|
|
在链式存储结构下进行插入和删除，其实质都是对相关指针的修改。
|
|
|
|
|
|
|
|
在单链表p所指结点（下图中元素a所在结点）后插入新元素结点（s所指结点，下图（a）中元素c所在结点）时，操作如下：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
在上图（b）中，若需删除元素b，则令p结点的指针域指向其后继的后继结点（即上图（b）中元素c所在结点），从而将元素b所在的结点从链表中摘除。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
线性表采用链表作为存储结构时，只能顺序地访问元素，而不能对元素进行随机存取。但其优点是插入和删除操作不需要移动元素。
|
|
|
|
根据结点中指针信息的实现方式，还有双向链表、循环链表和静态链表等链表结构。
|
|
|
|
.双向链表：每个结点包含两个指针，分别指明当前元素的直接前驱和直接后继信息，可在两个方向上遍历链表中的元素。
|
|
|
|
.循环链表：表尾结点的指针指向表中的第一个结点，可从表中任意结点开始遍历整个链表。
|
|
|
|
|
|
若双向链表中结点的front和next指针域分别指示当前结点的直接前驱和直接后继，则在双向链表中插入s所指结点时相关结点的指针域变化情况如下图（a）所示，其操作过程如下：
|
|
|
|
|
|
|
|
|
|
在双向链表中删除p所指结点时相关结点的指针域变化情况如上图（b）所示，其操作过程如下：
|
|
|
|
|
