2025年单向链表的存储密度（单链表的存储密度高于双链表）

线性表（List）是一种线性结构。其特点是数据元素直线的线性关系。

1.1初始化：

1.2容量管理

1.3数据存取

1.4指定位置插入元素

1.5删除顺序表元素

1.6查找值为o的数据元素的下标,使用顺序查找算法

1.7顺序表中元素有序插入与插入排序

instanceof运算符的前一个操作数是一个引用类型变量，后一个操作数是一个类（接口），用于判断前面的对象是否是后面的类，或子类、实现类的实例。若是，返回true；反之，返回false。

如果a,b均是comparable容器已实现的类型，则用comparable直接比较。
否则，转换为string类比较

addSort时间复杂度为O(n) sort为图片描述

1.8顺序表转换为数组

1.9顺序表转换为字符串

2.1单链表的概念

单链表是一个用指向后继元素的指针将具有线性关系的节点链接起来，最后一个节点的后继指针为空指针。

图片描述

节点：

由于节点类由data、next两部分组成，没有Comparable中数据类型的实现。故需改写Comparable中的方法。

节点类新增、改写几个方法：equals,comparaTo,toString
单链表的定义（部分）：

2.2单链表如何存取数据

首先用getNode(i)获取编号为i节点的引用。

链表getNode(i)时间复杂度为O(n)。注意，在顺序表中，复杂度为O(1)

获得引用后，用get(i)取得data值,set(i,x)修改i号节点的值。

2.3向链表中插入元素

s是指向新结点的引用变量，x是被插入的值。
分四种情况讨论：

1.向空链表插入一个新节点

2.在链表头结点之前插入新节点

3.在链表中间插入新节
图片描述

思考，两条语句能否调换位置？答：不能，p.next=s,此时s未确定,p指向未知位置。

4.在链表尾部插入新节点

完整的链表插入算法:

2.4删除链表节点

分三种情况处理：

1.删除的是空链表(first==null)
链表为空,此时删除非法。

2.被删除的是头结点(i=0)
first = first.next;//即可实现
实际开发中,可能需要被删除的值,故：

3.被删除的节点在中间

图片描述

得知要删除的节点p后,如何准确找到指针q的位置呢

完整的删除算法如下：

2.5查找节点

2.5向链表中插入有序节点
分四种情况讨论
1.链表为空

2.插入节点s的值小于头结点

first=s;//first 指向新节点
3.插入节点s值大于尾节点

4.插入节点处于中间位置

单链表有序插入算法:

//核心算法

2.6链表排序
单链表的插入排序示例：

总结:1.若是要在单链表中插入、删除一个节点，必须知道其前驱结点。
2.单链表不具有按序号随机处理的特点,只能从头指针一个一个顺序进行。

2.7链表转换为字符组/数组

3.1单循环链表
图片描述
具有单链表的特征,无需增加额外存储空间,对链表的处理更加灵活,整个链表构成一个环, 可以遍历已经访问过的元素。

在建立循环链表时,必须使最后一个节点的指针指向表头节点,而不是null。
在判断是否到表尾是.first==rear,而不是后继结点为null。

3.2双向链表

1.双链表的插入运算

图片描述

2.双链表的删除运算
直接断开节点间链接关系
删除s：

一、顺序表的特点是逻辑上相邻的数据元素，物理位置相邻，
并且，顺序表的存储空间需要预先分配。
它的优点是：
（1）方法简单，各种高级语言中都有数组，易实现。
（2）不用为表示节点间的逻辑关系而增加额外的存储开销。
（3）顺序表具有按元素序号随机访问的特点。
缺点：
（1）在顺序表中做插入、删除操作时，平均移动表中的一半元素，因此对n较大的顺序表效率低。
（2）需要预先分配足够大的存储空间(难以估计)，估计过大，可能会导致顺序表后部大量闲置；
预先分配过小，又会造成溢出。
二、在链表中逻辑上相邻的数据元素，物理存储位置不一定相邻，它使用**指针实现元素之间的
逻辑关系。并且，链表的存储空间是动态分配**的。
链表的最大特点是：
插入、删除运算方便。
缺点：
（1）要占用额外的存储空间存储元素之间的关系，存储密度降低。
存储密度是指一个节点中数据元素所占的存储单元和整个节点所占的存储单元之比。
（2）链表不是一种随机存储结构，不能随机存取元素。
三、顺序表与链表的优缺点切好相反，那么在实践应用中怎样选取存储结构呢？
通常有以下几点考虑：
（1）“MaxSize”分配，动态？静态？
当对线性表的长度或存储规模难以估计时，不宜采用顺序表。
当线性表的长度变化不大而且事先容易确定其大小时，为节省存储空间，
则采用顺序表作为存储结构比较适宜。
（2）基于运算的考虑（时间）
顺序存储是一种随机存取的结构，而链表则是一种顺序存取结构，
如果频繁按序号访问数据元素，显然顺表优于链表。
如果频繁增删，显然链表优于顺表。
（3）基于环境的考虑（语言）
顺序表容易实现，任何高级语言中都有数组类型；
链表的操作是基于指针的。相对来讲前者简单些，也用户考虑的一个因素。

总结：通常“较稳定”的线性表，即主要操作是查找操作的线性表，适于选择顺序存储；
而频繁做插入删除运算的（即动态性比较强）的线性表适宜选择链式存储。

不得转载。

2025年单向链表的存储密度（单链表的存储密度高于双链表）

相关推荐