列表，头指针，头节点

图1显示了线性表（赵，钱，孙，李，周，吴，郑，王）的逻辑状态. 头指针指示第一节点在链表中的存储位置（即，第一数据元素的存储映像）. 同时，由于最后一个数据元素没有直接后继，因此线性链接列表中最后一个节点的指针为“ NULL”.

图1线性链表的逻辑状态

从上面的描述可以看出，单链接列表可以由头指针唯一地确定，并且可以由C语言中的“结构指针”来描述.

[cpp]

// -----线性表的单链表存储结构----- typedefstructLNode {ElemTypedata; structLNode * next;} LNode，* LinkList;

有时，在单链表的第一个节点（称为头节点）之前添加一个节点. 头节点的数据字段不能存储任何信息或其他信息，例如线性表的长度. 头节点的指针字段存储指向第一个节点的指针（即，第一个元素节点的位置）. 如图2（a）所示，此时，单链接列表的头指针指向头节点. 如果线性表为空，则头节点的指针字段为“空”，如图2（b）所示.

图2具有头节点的单链表（a）非空列表； （b）空清单

循环链表是链式存储结构的另一种形式. 它的特征是表中最后一个节点的指针字段指向头节点，并且整个链表形成一个环. 因此，从表中的任何节点开始，您都可以在表中找到其他节点，如图3所示为单链循环列表.

图3单链循环表（a）非空表； （b）空表

循环链表的操作基本上与线性链表相同. 唯一的区别是算法中的循环条件不是p或p-> next是否为空，而是它们是否等于头指针，而是有时（如果在循环链表中）设置不带a的尾指针头指针（如图4（a）所示）可以简化某些操作. 例如，将两个线性表合并为一个表时，仅需要连接一个表的尾表和另一表的头表. 当线性表使用图2.4（a）中的循环链表作为存储结构时，此操作仅需要更改两个指针值，并且操作时间为O（1）. 合并后的表如图4（b）所示.

图4循环链表只有尾指针（a）两个链表； （b）合并清单

在上述链存储结构的节点中，只有一个指针字段指示直接后继. 因此，从某个节点开始，您只能跟随指针查找其他节点. 如果要查找节点的直接前任，则需要从头指针开始. 换句话说，在单链表中，NextElem的执行时间为O（1）链表头节点，而PriorElem的执行时间为O（n）. 为了克服这种单向列表的缺点，可以使用双向列表. 顾名思义，双向链接列表的节点中有两个指针字段，其中一个指向直接后继者，另一个指向直接前任者. 可以用C语言描述如下:

[cpp]

// -----线性列表双链表存储结构----- typedefstructDuLNode {ElemTypedata; structDuLNode * prior; structDuLNode * next;} DuLNode，* DuLinkList;

类似于单链循环表，双向链表也可以具有一个循环表，如图5（c）所示，链表中有两个环链表头节点，图5（b）显示只是一个头节点的Empty表. 在双向链表中，如果d是指向表中某个节点的指针（即d是DuLinkList类型变量），那么显然存在

d-> next-> prior = d-> prior-> next = d

图5双向链表示例（a）节点结构； （b）空双循环链表； （c）非空双向链表

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-243528-1.html