![](https://csdnimg.cn/release/download_crawler_static/86971024/bg4.jpg)
为单链表。
链表是由一个个结点构成的,结点定义如下:
typedef struct Node{
DataType data;
struct Node *next;
}LNode,*LinkList;
LNode 是结点的类型,*LinkList 是指向 LNode 结点的指针类型。
作为线性表的一种存储结构,我们关心的是结点间的逻辑结构,而对每个结点的实际地
址并不关心,所以通常的单链表用图2-4 的形式表示。
通常用“头指针”来标识一个单链表,如单链表L、单链表 H 等,是指某链表的第一个
结点的地址放在了指针变量L、H 中,头指针为“NULL”则表示一个空表。
2.单循环链表
对于单链表而言,最后一个结点的指针域是空指针,如果将该链表的头指针置入该指针
域,则使得链表头尾结点相连,就构成了单循环链表。
对于单链表只能从头结点开始遍历整个链表,而对于单循环链表则可以从表中任意结点
开始遍历整个链表,不仅如此,有时对链表常做的操作是在表尾、表头进行,此时可以改变
一下链表的标识方法,不用头指针而用一个指向尾结点的指针R 来标识,可以使操作效率得
以提高。
在单链表的结点中只有一个指向其后继结点的指针域next,因此若已知某结点的指针为
p,其后继结点的指针则为p >next,而找其前驱结点则只能从该链表的头指针开始,顺着各
结点的 next 域进行,也就是说找后继结点的时间性能是O(1),找前
驱的时间性能是 O(n),如果希望找前驱结点的时间性能也达到
O(1),则只能付出空间的代价:每个结点再加一个指向前驱结点的
指针域,结点的结构如图 2-5 所示,用这种结点组成的链表称为双
向链表。
typedef struct DLNode{
DataType data;
struct DLNnode *prior,*next;
}DLNode,*DLinkList;
通过双向链表中某结点的指针 p 既可以直接得到它的后继结点的指针 p->next,也可以
直接得到它的前驱结点的指针 p->prior。这样在有些操作中需要找前驱结点时,则勿需再用
循环。
设 p 指向双向循环链表中的某一结点,即p 中是该结点的指针,则p->prior->next 表示
的是 p 所指结点之前驱结点的后继结点的指针,即与p 相等;类似,p->next->prior 表示的