LinkedList 和 Array 比较# JobHunting - 待字闺中
B*4
1 楼
一般都说，LinkedList 删除是O（1）， Array删除是O（1）到O（n）。
但是，LinkedList 删除前不是要先定位到INDEX所在NODE吗,那已经是O（n)了呀？
但是，LinkedList 删除前不是要先定位到INDEX所在NODE吗,那已经是O（n)了呀？
x*a
2 楼
移动。
【在 B********4 的大作中提到】
: 一般都说，LinkedList 删除是O（1）， Array删除是O（1）到O（n）。
: 但是，LinkedList 删除前不是要先定位到INDEX所在NODE吗,那已经是O（n)了呀？
【在 B********4 的大作中提到】
: 一般都说，LinkedList 删除是O（1）， Array删除是O（1）到O（n）。
: 但是，LinkedList 删除前不是要先定位到INDEX所在NODE吗,那已经是O（n)了呀？
B*4
3 楼
LinkedList 移动不是必须从头开始移动吗，所以 worst case:O(n).
【在 x**********a 的大作中提到】
: 移动。
【在 x**********a 的大作中提到】
: 移动。
s*i
4 楼
单链，如果不给出previous ，的确是O(n)。
双链是O(1)
[发表自未名空间手机版 - m.mitbbs.com]
【在 B********4 的大作中提到】
: LinkedList 移动不是必须从头开始移动吗，所以 worst case:O(n).
双链是O(1)
[发表自未名空间手机版 - m.mitbbs.com]
【在 B********4 的大作中提到】
: LinkedList 移动不是必须从头开始移动吗，所以 worst case:O(n).
B*4
5 楼
双联你也得从头（或尾)一个个移过去，为啥是O(1)？
我理解双联LIST只是解决反向搜索问题。
【在 s*i 的大作中提到】
: 单链，如果不给出previous ，的确是O(n)。
: 双链是O(1)
:
: [发表自未名空间手机版 - m.mitbbs.com]
n*u
6 楼
prev和next的两个node里的pointer改一下就行了。
array的好处是省内存。
【在 B********4 的大作中提到】
:
: 双联你也得从头（或尾)一个个移过去，为啥是O(1)？
: 我理解双联LIST只是解决反向搜索问题。
g*g
7 楼
所以要具体例子具体分析，比如queue, stack就不是问题。
【在 B********4 的大作中提到】
: 一般都说，LinkedList 删除是O（1）， Array删除是O（1）到O（n）。
: 但是，LinkedList 删除前不是要先定位到INDEX所在NODE吗,那已经是O（n)了呀？
【在 B********4 的大作中提到】
: 一般都说，LinkedList 删除是O（1）， Array删除是O（1）到O（n）。
: 但是，LinkedList 删除前不是要先定位到INDEX所在NODE吗,那已经是O（n)了呀？
h*9
8 楼
我们通常说的删除只是delete 这个节点的操作 并不包括找到这个点。 对于list 只需
要改前后指针。 所以是o（1） 对于array 删除的操作是 删除这个节点 然后把后面的
所有节点前移。。。（或者把前面所有的节点后移） 这个前移或者后移的复杂度是o(n
)
要改前后指针。 所以是o（1） 对于array 删除的操作是 删除这个节点 然后把后面的
所有节点前移。。。（或者把前面所有的节点后移） 这个前移或者后移的复杂度是o(n
)
B*4
9 楼
需要改前后指针。 所以是o（1） 对于array 删除的操作是 删除这个节点 然后把后面
的所有节点前移。。。（或者把前面所有的节点后移） 这个前移或者后移的复杂度是o
(n).
这么解释就说的通。我的新问题是为啥并不包括找到这个点? 在Java里
LinkedList.remove(int index)
要实现这个方法需要两步，第一步找到这个节点，第二步修改前后节点的指针。
【在 h*******9 的大作中提到】
: 我们通常说的删除只是delete 这个节点的操作 并不包括找到这个点。 对于list 只需
: 要改前后指针。 所以是o（1） 对于array 删除的操作是 删除这个节点 然后把后面的
: 所有节点前移。。。（或者把前面所有的节点后移） 这个前移或者后移的复杂度是o(n
: )
s*r
10 楼
难道面试的时候因为这个挂了？
删除只需要修改指针，所以复杂度是O（1). 你这个函数需要分别调 find 和 delete，
比一般的删除明显复杂啊。
[在 BornIn1974 (BornIn1974) 的大作中提到：]
：
：【 在 hewei8829 (hewei8829) 的大作中提到: 】
：...........
删除只需要修改指针，所以复杂度是O（1). 你这个函数需要分别调 find 和 delete，
比一般的删除明显复杂啊。
[在 BornIn1974 (BornIn1974) 的大作中提到：]
：
：【 在 hewei8829 (hewei8829) 的大作中提到: 】
：...........
f*s
11 楼
Find O(n) delete O(1) 这样清楚么?
B*4
12 楼
暂时还没有挂，A家电面刚过。
话说现在是不是美国IT工作特好找呀？我都没有发简历，A家通过我的LinkedIn上简历
就找上我要电面。还说过两个月要来加拿大面试，难道美国本地都找不到人了？
【在 s*********r 的大作中提到】
: 难道面试的时候因为这个挂了？
: 删除只需要修改指针，所以复杂度是O（1). 你这个函数需要分别调 find 和 delete，
: 比一般的删除明显复杂啊。
: [在 BornIn1974 (BornIn1974) 的大作中提到：]
: ：
: ：【 在 hewei8829 (hewei8829) 的大作中提到: 】
: ：...........
话说现在是不是美国IT工作特好找呀？我都没有发简历，A家通过我的LinkedIn上简历
就找上我要电面。还说过两个月要来加拿大面试，难道美国本地都找不到人了？
【在 s*********r 的大作中提到】
: 难道面试的时候因为这个挂了？
: 删除只需要修改指针，所以复杂度是O（1). 你这个函数需要分别调 find 和 delete，
: 比一般的删除明显复杂啊。
: [在 BornIn1974 (BornIn1974) 的大作中提到：]
: ：
: ：【 在 hewei8829 (hewei8829) 的大作中提到: 】
: ：...........
相关阅读
F-1 opt期间发RSU和买公司股票的交税问题：W8-BEN证明中国住址(转载)也说说我和同组阿三发生的一件纠纷，我是不是玻璃心了说L家员工股票翻一点五倍的，到底是脑残还是脑瘫？？求建议：F和G的选择华人技术好但是不表现出来求职：美国湾区附近，入门级软件测试Oracle拉里·埃里森南加州大毕业演讲2016 (转载)【内部推荐】CS, EE, ME, Biology, Quality, RegulatoryBackground check问题简单说说这几年机器学习的形势SQL面题职场中国人基本上在最底层了吧Linkedin挂了工作遇到麻烦，大头对我不满意，请这里前辈指教如何应付 (转载)尼玛领英暴涨！pow(a,b) 这题考啥？KD Tree 找query点的最近点？苹果icloud/imessage组有发展前途吗骑驴找马找到驴小道消息：狗出23b