庄周梦蝶

生活、程序、未来
   :: 首页 ::  ::  :: 聚合  :: 管理

LinkedList的局限

Posted on 2010-09-16 13:51 dennis 阅读(7492) 评论(9)  编辑  收藏 所属分类: java数据结构与算法源码解读

    java.util.LinkedList是双向链表,这个大家都知道,比如Java的基础面试题喜欢问ArrayList和LinkedList的区别,在什么场景下用。大家都会说LinkedList随机增删多的场景比较合适,而ArrayList的随机访问多的场景比较合适。更进一步,我有时候会问,LinkedList.remove(Object)方法的时间复杂度是什么?有的人回答对了,有的人回答错了。回答错的应该是没有读过源码。

    理论上说,双向链表的删除的时间复杂度是O(1),你只需要将要删除的节点的前节点和后节点相连,然后将要删除的节点的前节点和后节点置为null即可,
//伪代码
node.prev.next=node.next;
node.next.prev
=node.prev;
node.prev
=node.next=null;

这个操作的时间复杂度可以认为是O(1)级别的。但是LinkedList的实现是一个通用的数据结构,因此没有暴露内部的节点Entry对象,remove(Object)传入的Object其实是节点存储的value,这里还需要一个查找过程:
  public boolean remove(Object o) {
        
if (o==null) {
            
for (Entry<E> e = header.next; e != header; e = e.next) {
                
if (e.element==null) {
                    remove(e);
                    
return true;
                }
            }
        } 
else {
            
//查找节点Entry
            for (Entry<E> e = header.next; e != header; e = e.next) {
                
if (o.equals(e.element)) {
                    
//删除节点
                    remove(e);
                    
return true;
                }
            }
        }
        
return false;
    }


    删除节点的操作就是刚才伪代码描述的:
   private E remove(Entry<E> e) {
        E result 
= e.element;
    e.previous.next 
= e.next;
    e.next.previous 
= e.previous;
        e.next 
= e.previous = null;
        e.element 
= null;
    size
--;
    modCount
++;
        
return result;
    }

    因此,显然,LinkedList.remove(Object)方法的时间复杂度是O(n)+O(1),结果仍然是O(n)的时间复杂度,而非推测的O(1)复杂度。最坏情况下要删除的元素是最后一个,你都要比较N-1次才能找到要删除的元素。

    既然如此,说LinkedList适合随机删减有个前提,链表的大小不能太大,如果链表元素非常多,调用remove(Object)去删除一个元素的效率肯定有影响,一个简单测试,插入100万数据,随机删除1000个元素:
        final List<Integer> list = new LinkedList<Integer>();
        
final int count = 1000000;
        
for (int i = 0; i < count; i++) {
            list.add(i);
        }
        
final Random rand=new Random();
        
long start=System.nanoTime();
        
for(int i=0;i<1000;i++){
            
//这里要强制转型为Integer,否则调用的是remove(int)
            list.remove((Integer)rand.nextInt(count));
        }
        System.out.println((System.nanoTime()
-start)/Math.pow(109));
   
    在我的机器上耗时近9.5秒,删除1000个元素耗时9.5秒,是不是很恐怖?注意到上面的注释,产生的随机数强制转为Integer对象,否则调用的是remove(int)方法,而非remove(Object)。如果我们调用remove(int)根据索引来删除:
        for(int i=0;i<1000;i++){
            list.remove(rand.nextInt(list.size()
-1));
        }
    随机数范围要递减,防止数组越界,换成remove(int)效率提高不少,但是仍然需要2.2秒左右(包括了随机数产生开销)。这是因为remove(int)的实现很有技巧,它首先判断索引位置在链表的前半部分还是后半部分,如果是前半部分则从head往前查找,如果在后半部分,则从head往后查找(LinkedList的实现是一个环):
        Entry<E> e = header;
        
if (index < (size >> 1)) {
            
//前一半,往前找
            for (int i = 0; i <= index; i++)
                e 
= e.next;
        } 
else {
            
//后一半,往后找
            for (int i = size; i > index; i--)
                e 
= e.previous;
        }

     最坏情况下要删除的节点在中点左右,查找的次数仍然达到n/2次,但是注意到这里没有比较的开销,并且比remove(Object)最坏情况下n次查找还是好很多。

    总结下,LinkedList的两个remove方法,remove(Object)和remove(int)的时间复杂度都是O(n),在链表元素很多并且没有索引可用的情况下,LinkedList也并不适合做随机增删元素。在对性能特别敏感的场景下,还是需要自己实现专用的双向链表结构,真正实现O(1)级别的随机增删。更进一步,jdk5引入的ConcurrentLinkedQueue是一个非阻塞的线程安全的双向队列实现,同样有本文提到的问题,有兴趣可以测试一下在大量元素情况下的并发随机增删,效率跟自己实现的特定类型的线程安全的链表差距是惊人的。

    题外,ArrayList比LinkedList更不适合随机增删的原因是多了一个数组移动的动作,假设你删除的元素在m,那么除了要查找m次之外,还需要往前移动n-m-1个元素。


   

评论

# re: LinkedList的局限[未登录]  回复  更多评论   

2010-09-16 14:37 by Charles
你在面试的时候,应该强调LinkedList.remove(Object value),而不是LinkedList.remove(LinkedList.Entry xxx)。
比如C#里提供的LinkedList就开放了LinkedList.Node相关的操作。

我觉得一个真正知道LinkedList.remove(...)复杂度是O(1)的人,是不会不知道LinkedList.remove(Object value)需要遍历的吧

:-)

# re: LinkedList的局限  回复  更多评论   

2010-09-16 14:49 by dennis
@Charles
哦,怎么都集中在面试这个问题。面试只是引子,想说的是这种通用数据结构的局限,对性能敏感的场景需要自己实现。

# re: LinkedList的局限  回复  更多评论   

2010-09-16 14:50 by mrluanma
final List<Integer> list = new ArrayList<Integer>();
这句应该是:
final List<Integer> list = new LinkedList<Integer>();
吧, 不是要测试 LinkedList 的吗?

# re: LinkedList的局限  回复  更多评论   

2010-09-16 14:51 by dennis
@mrluanma
感谢纠正,改的时候忘了改回来。

# re: LinkedList的局限  回复  更多评论   

2010-09-16 19:52 by Agrael
确实存在这个问题,JDK里的类库某些为了通用,做出来一些“牺牲”。在某些时候还是需要自己实现一些东西来完成一些特殊需求的。

# re: LinkedList的局限  回复  更多评论   

2010-09-20 10:38 by XD
如果是要O(1)的随机remove(int)的话,还必须增大空间复杂度,多加一个n大小的lookup table来保持对entry的引用么?这样的话,add(int, obj)也能做到O(1)了。
那么要O(1)的随机remove(value)的话,只能用hash表了么?

也就是说,如果要自己实现一个同样接口的O(1)remove的LinkedList的话,要多加2个内部数据结构?好像不是很经济啊。

# re: LinkedList的局限  回复  更多评论   

2010-11-28 10:33 by ahuoo
写的不错,学习了

# re: LinkedList的局限  回复  更多评论   

2011-01-16 18:29 by gumingcn
ArrayList的remove(int m) 好像不需要查找m次,只是remove(object)需要吧?
public E remove(int index) {
RangeCheck(index);

modCount++;
E oldValue = (E) elementData[index];

int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // Let gc do its work

return oldValue;
}

# re: LinkedList的局限[未登录]  回复  更多评论   

2015-08-12 14:38 by robert
感谢分享

只有注册用户登录后才能发表评论。


网站导航: