链表的定义
链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点都包括两部分:一是数据域,用来存储元素数值数据,另一个是存储直接后继结点地址的指针域,该指针一般称为next,用来指向下一个结点的位置。由于下一个结点也是链表类型,所以next的指针也要定义为链表类型。
链表概念及特点
头指针:是指向链表中第一个结点的指针
首元结点:是指链表中存储的第一个数据元素的结点
头结点:是在链表的首元结点之前附设的一个结点
在链表中设置头结点有何好处?
1)便于首元结点的处理。首元结点的地址保存在头结点的指针域中,所以在链表的第一个位置上的操作和其他位置一致,无须进行特殊处理。
2)便于空表和非空表的统一处理。无论链表是否为空,头指针都是指向头结点的非空指针,因此空表和非空表的处理也就统一了。
头结点的数据域内装的是什么?
可以为空,也可以存放线性表的长度等附加信息,但此节点不能计入链表长度值
链表的特点
1)结点在存储器中的位置是任意的,即逻辑相邻的数据元素在物理上不一定相邻
2)访问时只能通过头指针进入链表,并通过每个结点的指针域依次向后顺序扫描其余结点,所以寻找第一个结点和最后一个结点所花费的时间是不同的
链表的分类
1)单向链表
2)双向链表
3)循环链表(单向循环链表、双向循环链表)