ArrayList&LinkedList

    在网上看到很多很多对于这两个容器的分析，但是往往每个人都只是关注到了这样子两句话，ArrayList是一个动态数组，LinkedList为链表，数据量大后，在快速存取上，使用ArrayList效率高，在插入和删除上，LinkedList效率较快。
    但是我们来抽丝剥茧看看，到底是为什么？
     首先ArrayList和LinkedList都是继承至List这一个接口，List到底是对什么的抽象呢？看过数据结构的朋友肯定都能说出来-线性表：
     线性表的存储方式有很多种，顺序存储，链式存储，索引存储，散列存储。。。。我们先抛开两个容器，来看看这些存储方式，顺序存储一般可以用一维动态数组表示，也就是常常看到的a[0]，a[1]这种方式，假设一个数组大小是5，如果你要在a[2]插入一个数据，首先你要找到a[2]的地址，然后赋值为你想插入的值，a[2]后面的a[3]a[4]依次往后面移动一位，然后插入完成，如果你要删除，大体流程和插入时一致的。
     我们再来看看链式存储，每一个节点都有一个数据域和指针域，数据域放置当前节点的值，指针域放置下一个节点的地址，这里就是为什么它不能实现随机存储的原因，如果是顺序存储，它只要通过基地址+（你想求的下表-1）*每个节点的长度就能得到你所要的地址，但是对于链式存储来讲，只能通过上一个的指针域去找到下一个节点的地址，所以你想寻找数据，都必须一个一个的找。才能进行操作。它的删除和表中插入操作的步骤都是寻找到操作节点，设置当前节点指针域。就ok。
   上面对线性表的顺序存储和链式存储进行了分析，大家看出来了么？
    其实ArrayList就是对线性表顺序存储的一种封装，反之LinkedList则是对链式存储的一种封装。
   在这里还有一个概念，在快速存取上，使用ArrayList效率高，在插入和删除上，LinkedList效率较快，这里很多人都在想ArrayList的存和LinkedList的插入有什么区别，这里不是矛盾的么，所以对于这两个容器
ArrayList的优势在于读取和表尾插入
LinkedList的优势在于表中插入和删除。
当然这些也并不是绝对的 ，写写代码试试就知道了

评论

1 楼 yuantong 2009-10-18  

分析的很透彻，从数据结构出发，循序渐进，很好