Java中LinkedList的remove方法真的耗时O(1)吗

/ java / 没有评论 / 349浏览

这个问题其实来源于Leetcode的一道题目,也就是上一篇日志 LRU Cache。在使用LinkedList超时后,换成ArrayList居然AC了,而问题居然是在于List.remove(Object o)这个方法。

我们知道,链表和数组相比,最主要的特点就是add和remove的操作是O(1)的。Java中的链表一般使用LinkedList这个类型,数组一般使用ArrayList。它们同时implements了List这个interface,所以都有remove(int index)和remove(Object o)这两个方法。

普通意义上认为链表的remove操作是O(1)的,是因为对于某个给定的节点node,可以将它的前置节点的next直接置为node的下一个。而数组,则需要删除index处的元素,再将后面n个元素前移,所以需要O(n)的时间。

但是,在Java中果真如此吗?

细看JDK的源码,就可以发现,LinkedList的remove(int index)和remove(Object o)这两个方法都做不到O(1)的时间,而是O(n)。这是因为上面说的数据结构中的O(1)时间,是对于某个已经确定的节点。而LinkedList中,首先必须通过一个循环,找到第一个出现的Object o,或者走到index这个位置,再进行操作。也就是,有一个get的过程。

这时,虽然ArrayList的remove(int index)和remove(Object o)也是O(n)时间,但是移动耗费的时间远比LinkedList中往后寻址来的快得多,特别是元素很多的时候。JDK的源码里,这个操作是用System.arraycopy()来做的。所以,这时,LinkedList的最为坑爹的地方,也是最令人不解的地方就出现了——remove的操作居然比ArrayList还慢,而且慢的多!

而且,LinkedList需要内部维护一个数据结构,JDK 6中叫Entry,JDK 7中叫Node,这需要很多额外的内存。所以,除非急切需要LinkedList的Deque功能,任何情况下都应该使用ArrayList。其实,即使要用Deque,也有ArrayDeque。

所以,有时面试会问,在一个LinkedList list的遍历for循环中,不断执行remove(i)操作,时间复杂度是多少?其实是O(n^2),而不是O(n)。但是,如果使用iterator,it.remove()的时间复杂度就是O(1)了,因为这时元素已经给定。并且,for循环中进行remove(i)操作是要影响下标的。remove过后每次i都必须i--。使用iterator可以有效避免这个问题。这里可以看到,虽然for循环比较直观,但是有时iterator还是非常好的。

点击这里给我发消息
嘿!有什么能帮到您的吗?