前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >在数据结构中穿针引线:链表实现栈和队列

在数据结构中穿针引线:链表实现栈和队列

作者头像
五分钟学算法
发布2018-12-25 16:11:15
3760
发布2018-12-25 16:11:15
举报
文章被收录于专栏:五分钟学算法五分钟学算法

在上小节中可以了解到 链表的时间复杂度 如下:

接口

说明

复杂度

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队尾负责入队。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2018-12-05,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 五分钟学算法 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 链表实现栈
  • 链表实现队列
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档