LinkedList 和 Array 比较 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

LinkedList 和 Array 比较

LinkedList 和 Array 比较# JobHunting - 待字闺中

B*42014-12-22 08:12

1 楼

一般都说，LinkedList 删除是O（1）， Array删除是O（1）到O（n）。
但是，LinkedList 删除前不是要先定位到INDEX所在NODE吗,那已经是O（n)了呀？

x*a2014-12-22 08:12

2 楼

移动。

【在 B********4 的大作中提到】

: 一般都说，LinkedList 删除是O（1）， Array删除是O（1）到O（n）。
: 但是，LinkedList 删除前不是要先定位到INDEX所在NODE吗,那已经是O（n)了呀？

B*42014-12-22 08:12

3 楼

LinkedList 移动不是必须从头开始移动吗，所以 worst case:O(n).

【在 x**********a 的大作中提到】

: 移动。

s*i2014-12-22 08:12

4 楼

单链，如果不给出previous ，的确是O(n)。
双链是O(1)

[发表自未名空间手机版 - m.mitbbs.com]

【在 B********4 的大作中提到】

: LinkedList 移动不是必须从头开始移动吗，所以 worst case:O(n).

B*42014-12-22 08:12

5 楼

双联你也得从头（或尾)一个个移过去，为啥是O(1)？
我理解双联LIST只是解决反向搜索问题。

【在 s*i 的大作中提到】

: 单链，如果不给出previous ，的确是O(n)。
: 双链是O(1)
:
: [发表自未名空间手机版 - m.mitbbs.com]

n*u2014-12-22 08:12

6 楼

prev和next的两个node里的pointer改一下就行了。
array的好处是省内存。

【在 B********4 的大作中提到】

:
: 双联你也得从头（或尾)一个个移过去，为啥是O(1)？
: 我理解双联LIST只是解决反向搜索问题。

g*g2014-12-22 08:12

7 楼

所以要具体例子具体分析，比如queue, stack就不是问题。

【在 B********4 的大作中提到】

: 一般都说，LinkedList 删除是O（1）， Array删除是O（1）到O（n）。
: 但是，LinkedList 删除前不是要先定位到INDEX所在NODE吗,那已经是O（n)了呀？

h*92014-12-22 08:12

8 楼

我们通常说的删除只是delete 这个节点的操作并不包括找到这个点。对于list 只需
要改前后指针。所以是o（1）对于array 删除的操作是删除这个节点然后把后面的
所有节点前移。。。（或者把前面所有的节点后移）这个前移或者后移的复杂度是o(n
)

B*42014-12-22 08:12

9 楼

需要改前后指针。所以是o（1）对于array 删除的操作是删除这个节点然后把后面
的所有节点前移。。。（或者把前面所有的节点后移）这个前移或者后移的复杂度是o
(n).
这么解释就说的通。我的新问题是为啥并不包括找到这个点? 在Java里
LinkedList.remove(int index)
要实现这个方法需要两步，第一步找到这个节点，第二步修改前后节点的指针。

【在 h*******9 的大作中提到】

: 我们通常说的删除只是delete 这个节点的操作并不包括找到这个点。对于list 只需
: 要改前后指针。所以是o（1）对于array 删除的操作是删除这个节点然后把后面的
: 所有节点前移。。。（或者把前面所有的节点后移）这个前移或者后移的复杂度是o(n
: )

s*r2014-12-22 08:12

10 楼

难道面试的时候因为这个挂了？
删除只需要修改指针，所以复杂度是O（1). 你这个函数需要分别调 find 和 delete，
比一般的删除明显复杂啊。
[在 BornIn1974 (BornIn1974) 的大作中提到：]
：
：【在 hewei8829 (hewei8829) 的大作中提到: 】
：...........

f*s2014-12-22 08:12

11 楼

Find O(n) delete O(1) 这样清楚么?

B*42014-12-22 08:12

12 楼

暂时还没有挂，A家电面刚过。
话说现在是不是美国IT工作特好找呀？我都没有发简历，A家通过我的LinkedIn上简历
就找上我要电面。还说过两个月要来加拿大面试，难道美国本地都找不到人了？

【在 s*********r 的大作中提到】

: 难道面试的时候因为这个挂了？
: 删除只需要修改指针，所以复杂度是O（1). 你这个函数需要分别调 find 和 delete，
: 比一般的删除明显复杂啊。
: [在 BornIn1974 (BornIn1974) 的大作中提到：]
: ：
: ：【在 hewei8829 (hewei8829) 的大作中提到: 】
: ：...........