如何自学建网站,品牌营销策划方案怎么做才好,网站个人中心设计,wordpress编辑器可视化调用目录 一、什么是链表
二、基本操作
三、为什么要使用链表
四、为什么能够在常数时间访问数组元素
数组优点
数组缺点
五、动态数组诞生
链表优点
链表缺点
六、链表、数组和动态数组的对比
七、 链表种类
1. 单向链表
2. 双向链表
3. 循环链表
八、链表衍生
...…目录 一、什么是链表
二、基本操作
三、为什么要使用链表
四、为什么能够在常数时间访问数组元素
数组优点
数组缺点
五、动态数组诞生
链表优点
链表缺点
六、链表、数组和动态数组的对比
七、 链表种类
1. 单向链表
2. 双向链表
3. 循环链表
八、链表衍生
...... 一、什么是链表
链表是一种用于存储数据集合的数据结构。
链表有以下属性
相邻元素之间通过指针连接最后一个元素的后继指针值为 NULL在程序执行过程中链表的长度可以增加或缩小链表的空间能够按需分配(直到系统内存耗尽)没有内存空间的浪费(但是链表中的指针需要一些额外的内存开销) 二、基本操作
增删改查、计数等操作
三、为什么要使用链表
如果使用数组整个数组所有的元素都存储在操作系统分配的一个内存块中。
通过使用特定元素的索引作为数组下标可以在常数时间内访问数组元素。
四、为什么能够在常数时间访问数组元素
为了访问一个数组元素该元素的内存地址需要计算其距离数组基地址的偏移量。
需用一个乘法计算偏移量再加上基地址就可获得某个元素的内存地址。
数组优点
简单且易用。
访问元素快(常数时间)
数组缺点
大小固定数组的大小是静态的(在使用前指定数组的大小)。分配一个连续空间块数组初始分配空间时有时无法分配能存储整个数组的内存空间(当数组规模太大时)。基于位置的插入或删除操作实现复杂
比如说
如果要在数组中的给定位置插人元素可能需要移动存储在数组中的其他元素
这样才能腾出指定的位置来放插入的新元素如果在数组的开始位置插人元素那么移动操作的开销将更大。
五、动态数组诞生
动态数组是一种可随机存取且可自动调整大小的线性数据结构能够添加或删除元素。
也称为可增数组、可变长数组、动态表、数组列表在Java语言就是ArrayList。
实现动态数组的一个简单方法是首先初始化固定大小的数组。
一旦数组存储满了创建一个两倍于原始数组大小的新数组。
同样若数组中存储的元素个数小于数组大小的一半则把数组大小减少一半。
链表优点
可以在常数时间内扩展。
当创建数组时必须分配能存储一定数量元素的内存。
如果向数组中添加更多的元素那么必须创建一个新的数组然后把原数组中的元素复制到新数组中这将花费
大量的时间。而我们的链表是动态分配存储空间采取的是随机分配存储。
链表缺点
链表有许多不足链表的主要缺点在于访问单个元素的时间开销问题。
数组是随机存取的即存取数组中任一元素的时间开销为O(1)。而链表在最差情况下访问一个元素的开销为
O(n)。
数组在存取时间方面的另外一个优点是内存的空间局部性。
由于数组被定义为连续的内存块所以任何数组元素与其邻居是物理相邻的。
这极大得益于现代CPU的缓存模式。
尽管链表的动态分配存储空间有很大的优势但在存储和检索数据的开销方面却有很大的不足。
有时很难对链表操作。
如果要删除最后一项倒数第二项必须更改后继指针值为NULL。
这需要从头遍历链表找到倒数第二个结点的链接并设置其后继指针为 NULL。
最后链表中的额外指针引用需要浪费内存。
六、链表、数组和动态数组的对比
七、 链表种类
1. 单向链表
链表通常是指单向链表它包含多个结点每个结点有一个指向后继元素的next(下一个)指针。
表中最后一个结点的next指针值为 NULL表示该链表的结束。 2. 双向链表
双向链表的优点是对于链表中一个给定的结点可以从两个方向进行操作。
在单向链表中只有获得结点的前驱结点的指针才能删除该结点。
然而在双向链表中即使没有一个结点的前驱结点的地址也能删除该结点
因为每个结点有都一个指向前驱结点的指针可以直接后退到前驱结点。 双向链表缺点
每个结点需再添加一个额外的指针因此需要更多的空间开销。
结点的插人或删除更加费时因为它需要更多的指针操作。
3. 循环链表
在单向链表和双向链表中都采用 NULI 值表示链表的结束然而循环链表没有结束标志。
当遍历循环链表时需要特别小心否则将会无限地遍历链表因为在循环链表中每个结点都有一个后继结点。
与单向链表不同循环链表中没有next 指针为 NULI 的结点。
循环链表在某些情况下是非常有用的。
例如当多个进程需要在相同的时间内使用同一个计算机资源CPU时
必须确保在所有其他进程使用这些资源完前没有进程访问该资源轮询算法
在循环链表中使用表头结点访问元素与单向链表和双向链表中的表头结点相似 上图指的是单向循环链表当然还有我们的双向循环链表工作原理类似。
八、链表衍生
......
