线性表的链式存储结构,也叫做链表。在定义的链表中,若只含有一个指针域来存放下一个元素地址(即直接后继元素的存储地址),称这样的链表为单链表或线性链表。

链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。

节点结构如下

数据指针
datanext

data域–存放结点值的数据域
next域–存放结点的直接后继的地址(位置)的指针域(链域)
链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的,每个结点只有一个链域的链表称为单链表(Single Linked List)。

单链表逻辑表示:

一个括号内的表示完整的结点表示数据和指针用|分割
head->(d1|->)(d2|->)(d3|->) ….(dn|^)

其中,head 是头指针,它指向单链表中的第一个结点,这是单链表操作的入口点。由于最后一个结点没有直接后继结点,所以,它的指针域放入一个特殊的值 NULL。NULL 值在图示中常用(^)符号表示。可见,用单链表表示线性表时,数据元素之间的逻辑关系是通过链结点中的指针反映出来的,即指针是数据元素之间逻辑关系的映像。
为了简化对链表的操作,通常在单链表的第一个结点前增设一个附加结点,称为头结点,它的结构与表结点相同,其数据域可不存储信息,也可存储如线性表长度一类的附加信息。单链表设置头结点的作用归纳如下:① 头指针是指向头结点的非空指针,无论链表是否为空,头指针始终保持值不变,因此,头指针的处理方法对空表和非空表的操作是一致的。这与不带头结点的单链表为空时,头指针为空不同。② 首结点的地址存放在头结点(可看做首结点的前驱结点)的指针域中,故对该结点即首结点的操作与对表中其他结点的操作一致,无须进行特殊处理。

带头节点的单链表逻辑表示

head->(头|->)(d1|->)(d2|->)(d3|->) ….(dn|^)

以下用PHP代码演示单链表:包含单链表的基本运算

资料来源:知乎《数据结构》
PHP代码来自:
简书:https://www.jianshu.com/p/c571d7347023

最后修改日期:2020-04-28

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。