dva*_*ria 1 stack pointers abstract-data-type time-complexity data-structures
使用LinkedList实现的Stack抽象数据类型的put(x)和get()函数的时间复杂度是多少？
我的第一个想法是他们都是O(1).但是如果get()必须从头节点遍历到列表中的最后一个元素以找到要删除和返回的元素,则get()函数将为O(n).
put(x)函数也必须遍历整个列表以找到最后一个节点,它将安装一个新节点.所以这也是O(n).
如果使用LinkedList的"专用"版本,一个始终保持指向列表中最后一个节点的指针,则这两个版本都将成为恒定时间操作.我是否正确理解LinkedList的标准实现不具备此功能？
您不必在列表的末尾插入.如果您插入(单链接)列表的前面,它们都是O(1).
堆栈包含1,2,3:
[1]->[2]->[3]
推5:
[5]->[1]->[2]->[3]
流行:
[1]->[2]->[3], returning 5