B********4
发帖数: 7156 | 1 一般都说，LinkedList 删除是O（1）， Array删除是O（1）到O（n）。
但是，LinkedList 删除前不是要先定位到INDEX所在NODE吗,那已经是O（n)了呀？ |
x**********a
发帖数: 1372 | 2 移动。
【在 B********4 的大作中提到】
: 一般都说，LinkedList 删除是O（1）， Array删除是O（1）到O（n）。
: 但是，LinkedList 删除前不是要先定位到INDEX所在NODE吗,那已经是O（n)了呀？
|
B********4
发帖数: 7156 | 3 LinkedList 移动不是必须从头开始移动吗，所以 worst case:O(n).
【在 x**********a 的大作中提到】
: 移动。
|
s*i
发帖数: 5025 | 4 单链，如果不给出previous ，的确是O(n)。
双链是O(1)
[发表自未名空间手机版 - m.mitbbs.com]
【在 B********4 的大作中提到】
: LinkedList 移动不是必须从头开始移动吗，所以 worst case:O(n).
|
B********4
发帖数: 7156 | 5
双联你也得从头（或尾)一个个移过去，为啥是O(1)？
我理解双联LIST只是解决反向搜索问题。
【在 s*i 的大作中提到】
: 单链，如果不给出previous ，的确是O(n)。
: 双链是O(1)
:
: [发表自未名空间手机版 - m.mitbbs.com]
|
n*********u
发帖数: 1030 | 6
prev和next的两个node里的pointer改一下就行了。
array的好处是省内存。
【在 B********4 的大作中提到】
:
: 双联你也得从头（或尾)一个个移过去，为啥是O(1)？
: 我理解双联LIST只是解决反向搜索问题。
|
g*****g
发帖数: 34805 | 7 所以要具体例子具体分析，比如queue, stack就不是问题。
【在 B********4 的大作中提到】
: 一般都说，LinkedList 删除是O（1）， Array删除是O（1）到O（n）。
: 但是，LinkedList 删除前不是要先定位到INDEX所在NODE吗,那已经是O（n)了呀？
|
h*******9
发帖数: 46 | 8 我们通常说的删除只是delete 这个节点的操作 并不包括找到这个点。 对于list 只需
要改前后指针。 所以是o（1） 对于array 删除的操作是 删除这个节点 然后把后面的
所有节点前移。。。（或者把前面所有的节点后移） 这个前移或者后移的复杂度是o(n
) |
B********4
发帖数: 7156 | 9
需要改前后指针。 所以是o（1） 对于array 删除的操作是 删除这个节点 然后把后面
的所有节点前移。。。（或者把前面所有的节点后移） 这个前移或者后移的复杂度是o
(n).
这么解释就说的通。我的新问题是为啥并不包括找到这个点? 在Java里
LinkedList.remove(int index)
要实现这个方法需要两步，第一步找到这个节点，第二步修改前后节点的指针。
【在 h*******9 的大作中提到】
: 我们通常说的删除只是delete 这个节点的操作 并不包括找到这个点。 对于list 只需
: 要改前后指针。 所以是o（1） 对于array 删除的操作是 删除这个节点 然后把后面的
: 所有节点前移。。。（或者把前面所有的节点后移） 这个前移或者后移的复杂度是o(n
: )
|
s*********r
发帖数: 35 | 10 难道面试的时候因为这个挂了？
删除只需要修改指针，所以复杂度是O（1). 你这个函数需要分别调 find 和 delete，
比一般的删除明显复杂啊。
[在 BornIn1974 (BornIn1974) 的大作中提到：]
：
：【 在 hewei8829 (hewei8829) 的大作中提到: 】
：........... |
f*******s
发帖数: 182 | 11 Find O(n) delete O(1) 这样清楚么? |
B********4
发帖数: 7156 | 12 暂时还没有挂，A家电面刚过。
话说现在是不是美国IT工作特好找呀？我都没有发简历，A家通过我的LinkedIn上简历
就找上我要电面。还说过两个月要来加拿大面试，难道美国本地都找不到人了？
【在 s*********r 的大作中提到】
: 难道面试的时候因为这个挂了？
: 删除只需要修改指针，所以复杂度是O（1). 你这个函数需要分别调 find 和 delete，
: 比一般的删除明显复杂啊。
: [在 BornIn1974 (BornIn1974) 的大作中提到：]
: ：
: ：【 在 hewei8829 (hewei8829) 的大作中提到: 】
: ：...........
|
