线性链表

01-数据结构与算法 飞快学 499浏览

线性链表:线性表的链式存储结构称为线性链表,是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接来实现的。

在线性表的链式存储方式中,每个结点由两部分组成:一部分用于存放数据元素的值,称为数据域;另一部分用于存放指针,称为指针域,用于指向该结点的前一个或后一个结点(即前件或后件)。线性链表分为单链表、双向链表和循环链表三种类型。

线性链表和顺序表相比,优点是 1)高效率的插入和删除节点,2)空间大小可以灵活调整;缺点是 1)不能随机存取,2)由于使用了指针域,需要占用较多的存储空间。

单链表

lianbiao01

双向链表

liaobiao02

循环链表

在线性链表中,其插入与删除的运算虽然比较方便,但还存在一个问题,在运算过程中对于空表和对第一个结点的处理必须单独考虑,使空表与非空表的运算不统一。为了克服线性链表的这个缺点,可以采用另一种链接方式,即循环链表。

lianbiao03