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

大家好，我是讯享网，很高兴认识大家。

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

1.1初始化：

讯享网

1.2容量管理

1.3数据存取

讯享网

1.4指定位置插入元素

1.5删除顺序表元素

讯享网

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

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

讯享网

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

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向链表中插入元素

讯享网

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

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

讯享网

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

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

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

讯享网

完整的链表插入算法:

2.4删除链表节点

分三种情况处理：

讯享网

3.被删除的节点在中间

图片描述

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

讯享网

完整的删除算法如下：

2.5查找节点

讯享网

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

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

讯享网

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

讯享网

单链表有序插入算法:

//核心算法

讯享网

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

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

讯享网

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

3.2双向链表

1.双链表的插入运算

讯享网

图片描述

一、顺序表的特点是逻辑上相邻的数据元素，物理位置相邻，
并且，顺序表的存储空间需要预先分配。
它的优点是：
（1）方法简单，各种高级语言中都有数组，易实现。
（2）不用为表示节点间的逻辑关系而增加额外的存储开销。
（3）顺序表具有按元素序号随机访问的特点。
缺点：
（1）在顺序表中做插入、删除操作时，平均移动表中的一半元素，因此对n较大的顺序表效率低。
（2）需要预先分配足够大的存储空间(难以估计)，估计过大，可能会导致顺序表后部大量闲置；
预先分配过小，又会造成溢出。
二、在链表中逻辑上相邻的数据元素，物理存储位置不一定相邻，它使用指针实现元素之间的
逻辑关系。并且，链表的存储空间是动态分配

的。
链表的最大特点是：
插入、删除运算方便。
缺点：
（1）要占用额外的存储空间存储元素之间的关系，存储密度降低。
存储密度是指一个节点中数据元素所占的存储单元和整个节点所占的存储单元之比。
（2）链表不是一种随机存储结构，不能随机存取元素。
三、顺序表与链表的优缺点切好相反，那么在实践应用中怎样选取存储结构呢？
通常有以下几点考虑：
（1）“MaxSize”分配，动态？静态？
当对线性表的长度或存储规模难以估计时，不宜采用顺序表。
当线性表的长度变化不大而且事先容易确定其大小时，为节省存储空间，
则采用顺序表作为存储结构比较适宜。
（2）基于运算的考虑（时间）
顺序存储是一种随机存取的结构，而链表则是一种顺序存取结构，
如果频繁按序号访问数据元素，显然顺表优于链表。
如果频繁增删，显然链表优于顺表。
（3）基于环境的考虑（语言）
顺序表容易实现，任何高级语言中都有数组类型；
链表的操作是基于指针的。相对来讲前者简单些，也用户考虑的一个因素。

不得转载。

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

相关推荐