在数据结构中穿针引线：链表实现栈和队列
16lz
2021-01-22
在上小节中可以了解到 链表的时间复杂度 如下：
| 接口 | 说明 | 复杂度 |
|---|---|---|
| add(index, e) | 插入操作 | O(n) |
| remove(index, e) | 删除操作 | O(n) |
| set(index, e) | 修改操作 | O(n) |
| get(index, e) | 查找操作 | O(n) |
| contains(index, e) | 也是查找操作 | O(n) |
这似乎说明 链表 是一个性能不太优的数据结构，我们来对链表的接口进行一些调整，然后在看一下 时间复杂度 。
| 接口 | 说明 | 复杂度 |
|---|---|---|
| addFirst(index, e) | 插入表头操作 | O(1) |
| addLase(index, e) | 插入链尾操作 | O(1) |
| removeFirst(index, e) | 删除表头操作 | O(1) |
| removeLast(index, e) | 删除链尾操作 | O(1) |
| getFirst(index, e) | 查找链表头操作 | O(1) |
经过添加这些接口，链表的在使用时复杂度就变成了O(1)。
链表实现栈
链表实现队列
根据队列的性质，对于队列的操作势必会影响到链表的两端，根据前文的表格可以知道一端为O(1)，另外一端为O(n)。
为什么在链表中链表头的操作会简单为O(1) 呢，根据上图可以看出，因为有了一个标识位 head ，因此可以很快的定位的表头，同样的我们可以设置一个tail变量，这样对于两端插入元素都是很容易。
这样队列从head端删除元素，从tail端插入元素。
head 队首负责出队，tail队尾负责入队。
更多相关文章
- 看动画轻松理解时间复杂度（一）
- Oracle基本操作+Java连接Oracle
- NumPy进阶修炼｜基础操作与运算
- python数据分析——详解python读取数据相关操作
- PHP操作Redis数据库常用方法（总结）
- 关于PHP目录操作总结
- PHP作用域和文件夹操作示例
- php链式操作的实现
- PHP常用日期时间操作合集