ArrayList 和 LinkedList

在“集合框架”中有两种常规的 List 实现：ArrayList 和 LinkedList。使用两种 List 实现的哪一种取决于您特定的需要。如果要支持随机访问，而不必在除尾部的任何位置插入或除去元素，那么，ArrayList 提供了可选的集合。但如果，您要频繁的从列表的中间位置添加和除去元素，而只要顺序的访问列表元素，那么，LinkedList 实现更好。

  ArrayList内部是有数组实现的； 而LinkedList内部是有一个内部类来维护的，这个内部类包含三个属性，一个是指向上一个节点，一个是指向下一个节点，一个是当前元素的值

　　“ArrayList 和 LinkedList 都实现 Cloneable 接口，都提供了两个构造函数，一个无参的，一个接受另一个Collection”

　　2.3.1. LinkedList类

　　LinkedList类添加了一些处理列表两端元素的方法。

　　(1) void addFirst(Object o): 将对象o添加到列表的开头
  　　　　void addLast(Object o)：将对象o添加到列表的结尾

　　(2) Object getFirst(): 返回列表开头的元素
  　　　　Object getLast(): 返回列表结尾的元素

　　(3) Object removeFirst(): 删除并且返回列表开头的元素
　　  　　Object removeLast():删除并且返回列表结尾的元素

　　(4) LinkedList(): 构建一个空的链接列表
       LinkedList(Collection c): 构建一个链接列表，并且添加集合c的所有元素

　　“使用这些新方法，您就可以轻松的把 LinkedList 当作一个堆栈、队列或其它面向端点的数据结构。”

　　2.3.2. ArrayList类

　　ArrayList类封装了一个动态再分配的Object[]数组。每个ArrayList对象有一个capacity。这个capacity表示存储列表中元素的数组的容量。当元素添加到ArrayList时，它的capacity在常量时间内自动增加。

　　在向一个ArrayList对象添加大量元素的程序中，可使用ensureCapacity方法增加capacity。这可以减少增加重分配的数量。

　　(1) void ensureCapacity(int minCapacity): 将ArrayList对象容量增加minCapacity

　　(2) void trimToSize(): 整理ArrayList对象容量为列表当前大小。程序可使用这个操作减少ArrayList对象存储空间