链表用途&&数组效率&&链表效率&&链表优缺点
2024-10-19 00:31:05
三大数据结构的实现方式
| 数据结构 | 实现方式 |
| 栈 | 数组/单链表 |
| 队列 | 数组/双端链表 |
| 优先级队列 | 数组/堆/有序链表 |
| 双端队列 | 双向链表 |
数组与链表实现方式的比较
数组与链表都很快
如果能精确预测栈或者队列所需要容纳的数据量 --- 数组
如果不能 --- 链表
数组的效率
|
|
无序数组 |
有序数组 |
|
查找 |
比较次数O(N) |
比较次数O(logN)<—二分查找 |
|
插入 |
O(1) |
比较次数O(N) |
|
|
移动次数MaxO(N) |
|
|
删除 |
比较次数O(N) |
比较次数O(logN) |
|
|
移动次数MaxO(N) |
移动次数MaxO(N) |
链表的效率
|
单链表 |
双端链表 |
有序链表 |
双向链表 |
|
|
头插 |
O(1) |
O(1) |
||
|
头删 |
O(1) |
O(1) |
||
|
尾插 |
O(1) |
O(1) |
||
|
尾删 |
O(N) |
O(1) |
||
|
插入 |
Max O(N) | Min O(N/2) |
|||
|
删除 |
O(1) |
|||
|
查找结点 |
O(N) 次比较 无移动次数 |
|||
|
删除结点 |
O(N) 次比较 无移动次数 |
O(N) – deleteKey(int i) |
||
|
指定结点后插入 |
O(N) 次比较 无移动次数 |
O(N) – insertAfter(int i) |
链表优点
l 使用内存无限制 可以扩展到所有可以使用的内存
数组大小在创建的时候 就固定了经常由于数组太大 导致效率低下 或者数组太小导致空间溢出
l 插入删除结点的时候 链表不需要任何移动 特别是复制时间远远大于比较时间的时候
双向链表
优点：
前向遍历
后向遍历
缺点：
每次插入或者删除一个链结点时候 需要处理四个连结点的引用（2个连接前一个链结点 两个链接后一个）由于多了两个引用 连结点占用的空间也变大了
最新文章
- 响应式手机商城页面顶部样式HTML代码
- OC基础--对象做参数在方法间传递
- 010 winform
- 在c++程序中执行DOS命令
- PL/SQL Developer使用
- AIDL实现Android IPC
- vbs运行批处理
- sql中truncate 、delete与drop区别
- java特殊运算符(转)
- .NET DataTable转化为json格式
- php数组(array)输出三种形式
- IOS开发，如何用最新的Itunes给手机装ipa文件
- ubuntu 创建 PyCharm 桌面快捷方式 (或者叫 启动器 ）
- Spring Cloud Alibaba基础教程：Nacos的数据持久化
- CentOS7中MariaDB重置密码
- Cobaltstrike、armitage联动
- 转----------数据库常见笔试面试题 - Hectorhua的专栏 - CSDN博客
- IIS+NGINX 负载web服务器
- 【添加最新版本的mysql的jdbc连接jar包】java.math.BigInteger cannot be cast to java.lang.Long异常
- 【java初探】——格式化字符串