LinkedList和Queue, stack, deck的关系



  • 你好,

    我想问一下,因为在Java linkedList, 可以从前面加前面减,也可以从后面加后面减,知道用的是stack, queue, 或者deck重要吗?还是我可以提到就用一个linkedlist, 根据我的需要从前或者后加减?

    谢谢



  • 本质就是这样做的。

    不过queue, stack之类的结构也可以使用array来实现,要了解linkedlist和arrary的优缺点:)



  • 可以用queue,stack来解决问题的情况下,我是应该选择linkedlist还是array呢?

    Linkedlist的优点是不是remove第一个element之后不用shuffle整个list呢?Array如果减掉第一个,其余的element都要变动?



  • @Chuanxi_Zhang 对啊,时间复杂度不一样。每次移动1个元素(增加,删除),array都需要把其他所有元素move一次,所以是O(n)的时间。LinkedList就不用了,要删除/增加节点的前面那个节点的next一指就完事儿。
    为什么不比较查找效率?
    虽然平时LinkedList查找是O(n),Array是O(1)由于LinkedList,但因为这两数据结构有限制,stack只能取最后面放入的一个,queue只能取最先进入的,所以,这个时候用LinkedList实现方式,由于要取得的索引其实是固定的那一个,链表中是有记录的。所以是O(1)。
    自己实现的话,比如stack最后一个是 tail
    直接 tail = tail.pre; return tail.next;

    比如 queue第一个是head,
    head = head.next; return head.prev;
    这样就好了,所以链表实现查找的时间复杂度应该是O(1)。


登录后回复
 

与 BitTiger Community 的连接断开,我们正在尝试重连,请耐心等待