LinkedList的局限

  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(10, 9));    
    在我的机器上耗时近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个元素。

文章转自庄周梦蝶  ，原文发布时间 2010-09-16

一文颠覆你对 ArrayList 和 LinkedList 的认知 在初学Java的时候我们经常能看到这么一句话：ArrayList增删慢查询快，LinkedList增删快查询慢。但随着学习的不断深入，我们会发现这句话并不对，初学时看到这句话主要还是为了新手友好。
LinkedHashMap 底层分析（下） 众所周知 HashMap 是一个无序的 Map，因为每次根据 key 的 hashcode 映射到 Entry 数组上，所以遍历出来的顺序并不是写入的顺序。
LinkedHashMap 底层分析（上） 众所周知 HashMap 是一个无序的 Map，因为每次根据 key 的 hashcode 映射到 Entry 数组上，所以遍历出来的顺序并不是写入的顺序。
ArrayList和LinkedList使用不当，性能差距会如此之大！ ArrayList实现了List接口，继承了AbstractList抽象类，底层是数组实现的，并且实现了自增扩容数组大小。ArrayList还实现了Cloneable接口和Serializable接口，所以他可以实现克隆和序列化。ArrayList还实现了RandomAccess接口，这个接口是一个标志接口，他标志着“只要实现该接口的List类，都能实现快速随机访问”。基本属性ArrayList属性主要由数组长度size、对象数组elementData、初始化容量default_capacity等组成， 其中初始化容量默认大小为10。//默认初始化容量private static final