关于队列这个问题，为什么要在tail部分添加元素呢？
来源：4-7 带有尾指针的链表：使用链表实现队列
慕前端0929456
2018-09-17
在front部分添加删除元素都是o(1)的复杂度
在tail部分添加就是o(n)
我觉得在tail这端删除也是o(n)
那为什么老师选择在tail端添加在front端删除
我觉得在front端添加和在tail端删除也一样的啊
为什么加了尾部指针就可以了呢
写回答
1回答
-
liuyubobobo
2018-09-18
如果我们的链表没有tail指针的话：
在链表头添加：O(1)，在链表尾删除：O(n)；
在链表头删除：O(1)，在链表尾添加：O(n)；
所以，如果使用链表实现一个队列，在没有指针的情况下，不管选择从哪边删除哪边添加，总有一个操作是O(n)的。
当我们维护了一个尾指针以后。从链表头增删，和从链表尾增删，都是O(1)的。
是的。此时，从链表头添加，从链表尾删除也是ok的。这时只是一个选择而已，对性能没有影响。我选择从链表头删除，从链表尾添加，是因为和队列的“语意”保持一致，即链表头就是队头，用于出队；链表尾就是队尾，用于入队。
当然了，依然是，你选择从链表头添加，从链表尾删除，是完全ok的。建议有兴趣自己实现一下试试看：）
加油！：）
042018-09-19
相似问题