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

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

接口 说明 复杂度
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队尾负责入队。

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

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

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


本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 在数据结构中穿针引线:链表实现栈和队列

我还会在以下平台发布内容

GitHub 哔哩哔哩