一.java集合类图如下所示：
上述类图中，实线边框的是实现类，比如ArrayList，LinkedList，HashMap等，折线边框的是抽象类，比如AbstractCollection，AbstractList，AbstractMap等，而点线边框的是接口，比如Collection，Iterator，List等。
Java集合都在java.util包中实现。
二.List（基于JDK7）
List是有序的collection，当加入一个元素时，会以特定的顺序加入到集合中来保证元素是有序的。因此元素加入的顺序和取出的顺序可能不同。
List中元素是可以重复加入的，并且能够加入null元素，还可以通过索引来访问元素。
实现了List接口的有Vector、Stack、ArrayList、LinkedList这几个类，List接口为这些类提供了同一的方法。（Vector和Stack已基本很少使用）
List接口的源代码非常简单：
package java.
public interface List&E& extends Collection&E& {
int size();
boolean isEmpty();
boolean contains(Object o);
Iterator&E& iterator();
Object[] toArray();
&T& T[] toArray(T[] a);
boolean add(E e);
boolean remove(Object o);
E get(int index);
E set(int index, E element);
void add(int index, E element);
E remove(int index);
boolean containsAll(Collection&?& c);
boolean addAll(Collection&? extends E& c);
boolean addAll(int index, Collection&? extends E& c);
boolean removeAll(Collection&?& c);
boolean retainAll(Collection&?& c);
void clear();
boolean equals(Object o);
int hashCode();
int indexOf(Object o);
int lastIndexOf(Object o);
ListIterator&E& listIterator();
ListIterator&E& listIterator(int index);
List&E& subList(int fromIndex, int toIndex);
二.ArrayList
1、ArrayList的属性
public class ArrayList&E& extends AbstractList&E&
implements List&E&, RandomAccess, Cloneable, java.io.Serializable
private static final long serialVersionUID = 2892189L;
private transient Object[] elementD
private int
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
ArrayList也就是动态数组，可以看到ArrayList的实现是基于数组的，因此ArrayList也拥有数组的一些特性：
1）通过索引index随机访问的速度非常快，eg：get（index）
2）当元素个数超过数组容量时，需要进行内存的重新分配并复制原有元素，这会非常影响性能，因此最好在使用前就创建足够容量的ArrayList对象
2、构造
public ArrayList(int initialCapacity) {
if (initialCapacity & 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
public ArrayList() {
public ArrayList(Collection&? extends E& c) {
elementData = c.toArray();
size = elementData.
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
可以看到ArrayList有三种构造方式：
1）传递一个容量参数
2）不传递任何参数，则默认构造一个容量为10的ArrayList
3）以一个集合为参数进行构造，最后会生成一个size为集合大小，元素为集合中的所有元素的ArrayList
3、清除
在Java中，由于可以不用考虑内存释放，很多问题都变得非常简单。
如clear()方法，只需要依次将所有元素置为null即可，对象的释放会有JVM的GC机制自动完成。注意最后还要将size置为0.
public void clear() {
modCount++;
for (int i = 0; i & i++)
elementData[i] = null;
当要向集合中加入一个元素时，首先都是保证安全性（数组容量和索引大小，容量不足时就会重新分配内存，以原有元素重新构造），然后再加入一个元素。
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] =
return true;
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1);
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] =
当直接向数组中加入一个元素时，直接在数组末尾加入。
当在索引index处加入时，则需要将index处及以后的元素全部向后移动一个，再将index处元素置为待插入的新元素
从集合中删除一个元素的主要步骤是：
1）首先找到待删除元素的位置index
2）然后将index之后的所有元素向前移动一个
3）将size-1
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved & 0)
System.arraycopy(elementData, index+1, elementData, index,numMoved);
elementData[--size] = null;
return oldV
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index & index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
for (int index = 0; index & index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
return false;
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved & 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null;
6、查&改
set()和get()方法的实现非常简单，首先检查安全性（index位置是否合法），然后再直接用index索引数组元素并返回或修改
public E get(int index) {
rangeCheck(index);
return elementData(index);
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] =
return oldV
7、iterator
ArrayList通过一个下标cursor属性来实现迭代器。
cursor可访问的范围为[0，size]，当cursor=0时，hasPrevious（）返回false；当cursor=size时，hasNext()为false。
这是一个双向索引的迭代器，以next操作为例（prev侧实现类似）：
public boolean hasNext() {
return cursor !=
public E next() {
checkForComodification();
if (i &= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementD
if (i &= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
8、遍历
ArrayList的遍历方式主要有如下几种：
1）通过索引及get()访问（与原始的数组访问方式类似）
Integer value =
int size = list.size();
for (int i=0; i&size; i++) {
value = (Integer)list.get(i);
2）for循环遍历
Integer value = null;
for (Integer integ:list) {
3）通过iterator访问
Integer value = null;
Iterator iter = list.iterator();
while (iter.hasNext()) {
value = (Integer)iter.next();
三.LinkedList
与ArrayList不同，LinkedList是基于链表的，因此随机插入和删除的操作非常快，不需要像ArrayList那样可能需要大量copy，同时也不担心容量不足带来的效率问题，但是LinkedList随机访问的速度较差。
LinkedList中每个节点都包含prev和next索引，形成双向链表。LinkedList则通过first和last两个属性分别保存双向链表的头节点和尾部节点。
基本结构如下所示（部分连线未画出）：
1、基本辅助操作
创建一个节点Node对象
Node(Node&E& prev, E element, Node&E& next) {
this.item =
this.next =
this.prev =
向链表中加入、移除一个节点
向链表中加入一个节点对应的主要是对各个相关节点的操作，与C中修改指针的操作非常相似。
主要步骤是：
1）首先找到待插入位置的前后节点
2）然后以前后节点分别作为prev和next创建一个新节点
3）再对前后节点的prev和next属性进行更改
4）更新LinkedList的first、last引用
private void linkFirst(E e) {
final Node&E& f =
final Node&E& newNode = new Node&&(null, e, f);
first = newN
if (f == null)
last = newN
f.prev = newN
modCount++;
void linkLast(E e) {
final Node&E& l =
final Node&E& newNode = new Node&&(l, e, null);
last = newN
if (l == null)
first = newN
l.next = newN
modCount++;
void linkBefore(E e, Node&E& succ) {
final Node&E& pred = succ.
final Node&E& newNode = new Node&&(pred, e, succ);
succ.prev = newN
if (pred == null)
first = newN
pred.next = newN
modCount++;
从链表中移除一个节点的各个操作与上面的各个操作基本类似，对应的几个方法分别是：
private E unlinkFirst(Node&E& f) { }
private E unlinkLast(Node&E& l) { }
E unlink(Node&E& x) { }
LinkedList的很多方法都是基于上述这些操作的，因此在对上述基本操作有了一定的了解之后，就可以开始开始对LinkedList的学习了。
LinkedList只提供了两种构造方法：构造一个空的LinkedList或者一个集合来构造
public LinkedList() {
public LinkedList(Collection&? extends E& c) {
addAll(c);
3、增加、移除一个元素
当向集合中加入一个元素时，可以在链表头部、尾部加入，也可以在index之前加入，当不传递位置信息时，默认在链表尾部加入。
可以发现add()最终的操作都是link相关方法，即以新增元素为参数创建一个节点，再在恰当的位置与链表link在一起，即将元素加入到集合中了。
public void addFirst(E e) {
linkFirst(e);
public void addLast(E e) {
linkLast(e);
public boolean add(E e) {
linkLast(e);
return true;
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
linkBefore(element, node(index));
由上面增加一个元素的操作可以知道移除一个元素的操作也与之类似：首先找到待移除元素节点，然后调用unlink()方法解除该节点与链表直接的联系，即从链表中移除了。
4、查、改
get()与set()方法非常简单，与ArrayList基本相同：首先进行index合法性检查，再返回相应的value。
public E get(int index) {
checkElementIndex(index);
return node(index).
public E set(int index, E element) {
checkElementIndex(index);
Node&E& x = node(index);
E oldVal = x.
return oldV
5、根据index索引一个元素
首先进行简单的二分，判断index是链表的前半部还是后半部，然后再分别从链表头或链表尾部进行查找，使得效率有了一定程度的提升
Node&E& node(int index) {
if (index & (size && 1)) {
Node&E& x =
for (int i = 0; i & index; i++)
x = x.next;
Node&E& x = last;
for (int i = size - 1; i & index; i--)
通过对List、ArrayList、LinkedList的源码分析可以发现，其实他们的内部实现非常简单。
ArrayList、LinkedList的特点也与基本的数组、双向链表类似。
简单的总结如下：
List：有序、元素可重复、可以加入null元素、可通过索引index访问元素
ArrayList：基于动态数组，随机访问效率很高，插入或删除一个元素时效率较低（可能需要扩容、内存重分配、拷贝）
LinkedList：基于双向链表，随机访问效率较低，插入或删除一个元素时效率较高
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：60130次
积分：1859
积分：1859
排名：第18994名
原创：119篇
转载：21篇
(2)(4)(20)(63)(12)(4)(1)(5)(3)(9)(11)(2)(2)(3)(4)4411人阅读
Lisp（95）
作为一个基本功能，文件操作对于大多数语言来讲都是必须支持的，Lisp语言和大多数语言一样提供了文件操作接口。&在Lisp中对文件的操作通过函数open来实现，通过open函数打开一个文件，然后通过read函数读取文件内容，或者通过format函数将数据写入文件中。&函数open的第一个参数是目标文件的路径和文件名，然后是一些参数，包括：:direction用于指定文件打开后会执行的操作，缺省值是读取，如果需要写入的话使用:output作为值:if-does-not-exist用于指定目标文件不存在时的操作，可以指定值为nil，表示文件不存在时open函数返回nil，也可以指定为:create，表示文件不存在的话就创建一个。:if-exists用于指定目标文件存在时的操作，可以指定值为:overwrite，表示如果目标文件存在的话直接覆盖原文件。&所以有下面这样的样例代码：&(setq file-to-read (open &c:\\workspace\\lisp\\file-test.txt& :if-does-not-exist nil))
(setq file-to-write (open &c:\\workspace\\lisp\\file-test.txt& :direction :output :if-does-not-exist :create :if-exists :overwrite))
第一行代码使用open函数以读的方式打开文件“c:\\workspace\\lisp\\file-test.txt”，用变量file-to-read指向打开的文件，如果文件不存在则file-to-read的值为nil第二行代码使用open函数以写的方式打开文件“c:\\workspace\\lisp\\file-test.txt”，用变量file-to-write指向打开的文件，如果文件不存在就创建一个，如果文件存在就覆盖原文件。以写的方式打开文件后，可以使用format函数将内存中的数据写入文件中，样例如下：(format file-to-write &~a~%& sample-list)
以上代码将sample-list对象写入文件file-to-write中&以读得方式打开文件后，可以通过read函数读取文件中的内容，样例如下：(read file-to-read)以上代码从文件file-to-read中读取一行，并尝试按lisp语法解读该行的内容，如果写进去的是一个列表，读出来的也会是一个列表。&在文件操作完成后记得使用close函数关闭文件，格式如下：(close 文件变量)下面是文件读写的一个简单样例：(defun my-write-file ()
;文件写入样例
定义一个列表变量
(setq sample-list '(a b c (1 2) d e f (one two three (right left up down) four) g h i))
以写的方式打开文件，将文件句柄赋予变量file-to-write
(setq file-to-write (open &c:\\workspace\\lisp\\file-test.txt& :direction :output :if-does-not-exist :create :if-exists :overwrite))
将变量sample-list写入文件
(format file-to-write &~a~%& sample-list)
(close file-to-write))
(defun my-read-file ()
;文件读取样例
以读的方式打开文件
(setq file-to-read (open &c:\\workspace\\lisp\\file-test.txt& :if-does-not-exist nil))
如果文件不存在就退出
(if (not file-to-read)
(format t &file open failed ~%&)
(return-from my-read-file nil)))
读取文件中的一行，将读出来的值赋予list-readed
(setq list-readed (read file-to-read))
(close file-to-read)
判断list-readed是不是一个列表，并在控制台输出
(format t &is list-readed is a list:~a ~%& (listp list-readed))
返回读出来的值
list-readed)
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：1385026次
积分：14436
积分：14436
排名：第688名
原创：246篇
评论：707条
文章：30篇
阅读：89002
文章：88篇
阅读：565873
文章：20篇
阅读：54734
文章：12篇
阅读：28434
(1)(4)(3)(6)(5)(2)(5)(8)(1)(2)(4)(2)(4)(4)(5)(1)(3)(1)(5)(7)(4)(1)(1)(6)(2)(10)(13)(2)(7)(6)(5)(7)(10)(14)(3)(4)(7)(14)(49)(4)(4)Javascript实现Lisp列表(list)及操作 - 推酷
Javascript实现Lisp列表(list)及操作
Lisp中列表（list）是一个值对，通过操作cons来创建值对，例如(cons 1 2), 1和2分别是值对的两个值。 cons操作具有
，因此构成列表的元素可以是原子类型，也可以是列表类型本身,如(cons 1 (cons 2 3))。读取列表的操作有car、cdr,分别是读取值对的“左值”和“右值”，如(car '(1 2)) 返回1，(cdr '(1 2)) 则返回2， car、cdr操作同样具有闭包性。
对于用程序描述列表中是否包含某个元素这样一个功能，大多数的编程语言通过本身具有迭代操作（for||while）,很容易就可以实现它。但是Lisp可以用递归来完成迭代完成的，而令我感到惊讶是它仅仅使用car、cdr。
(defun our-member (obj lst)
(if (null lst)
(if (eql (car lst) obj)
(our-member obj (cdr lst)))))
这种通过纯函数来表达计算过程， 比起过程化的for&&while语法来说更加简洁。 在学习lisp语言之前，我从来没有想过要遍历一个列表，除了迭代之外还可以用递归，而递归这种方法更适合用来描述一个数学计算问题。
对于Javascript这样的语言，它具有比lisp更加丰富的数据结构，通常我们会用一个Array来表示列表，它的语法更为直观如:
var list =[1,2,3,4];
for(var i =0;i< list.i++){
虽然如此，我仍然希望Javascript也可以仅仅使用cons,car,cdr函数的来完成列表的各种操作，谨此来引发对不同语言的思考，这也是我写这个笔记的目的。
Javascript 纯函数实现 cons、car、cdr&
var cons =function(left, right){
function(f){return f(left,right);}; // 返回列表函数, 使left,right一直保存在内存中
var car =function(list){
return list(function(left,right){}); // 实例化高阶函数f，取left值
var cdr = function(list){
return list(function(left,right){});// 实例化高阶函数，取right值
var list=cons(1,cons(2,3));
car(list);//1
car(cdr(list));//2
cons没有使用任何javascript数据类型来存储left 、right值，而是返回一个“列表函数“。借助Javascript的
，cons把left，right传递到另一个高阶函数f，使得外部函数可以访问它们，最后为了取到列表的left和right，我们只要在car、cdr中实例化高阶函数f并传递给“列表函数& list。&
结语：数据去哪儿了？Javascript通过closure，让高阶函数接受自由变量作为参数，自由变量随高阶函数生与灭，而高阶函数在调用时不也被当做数据吗？这也正如函数式语言的宣称的那样，一切皆为函数。
注：Javascript closure 通常也叫做闭包，但和前面提到的闭包操作是不同的概念。
已发表评论数()
请填写推刊名
描述不能大于100个字符!
权限设置： 公开
仅自己可见
正文不准确
标题不准确
排版有问题
主题不准确
没有分页内容
图片无法显示
视频无法显示
与原文不一致List集合底层实现 - 博客频道 - CSDN.NET
JAVA_Admin_User的博客
List实现Collection接口，它的数据结构是有序可以重复的结合，该结合的体系有索引；它有三个实现类：ArrayList、LinkList、Vector三个实现类；
三个实现类的区别：
ArrayList:底层数据结构使数组结构，查询速度快，增删改慢，
LinkList:底层使用链表结构，增删速度快，查询稍慢；
Vector：底层是数组结构，线程同步ArrayList是线程不同步；
可变长度数组不断new数组：
ArrayList当初始化容量超过10时，会new一个50%de ,把原来的东西放入这150%中；
Vector：当容量超过10时，会new一个100%的浪费内存；
List接口对Collection进行了简单的扩充，它的具体实现类常用的有ArrayList和LinkedList。你可以将任何东西放到一个List容器中，并在需要时从中取出。ArrayList从其命名中可以看出它是一种类似数组的形式进行存储，因此它的随机访问速度极快，而LinkedList的内部实现是链表，它适合于在链表中间需要频繁进行插入和删除操作。在具体应用时可以根据需要自由选择。前面说的Iterator只能对容器进行向前遍历，而ListIterator则继承了Iterator的思想，并提供了对List进行双向遍历的方法。
2.ArrayList
1. ArrayList概述：
&& ArrayList是List接口的可变数组的实现。实现了所有可选列表操作，并允许包括 null 在内的所有元素。除了实现 List 接口外，此类还提供一些方法来操作内部用来存储列表的数组的大小。
&& 每个ArrayList实例都有一个容量，该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向ArrayList中不断添加元素，其容量也自动增长。自动增长会带来数据向新数组的重新拷贝，因此，如果可预知数据量的多少，可在构造ArrayList时指定其容量。在添加大量元素前，应用程序也可以使用ensureCapacity操作来增加ArrayList实例的容量，这可以减少递增式再分配的数量。&
&& 注意，此实现不是同步的。如果多个线程同时访问一个ArrayList实例，而其中至少一个线程从结构上修改了列表，那么它必须保持外部同步。
2. ArrayList的实现：
&& 对于ArrayList而言，它实现List接口、底层使用数组保存所有元素。其操作基本上是对数组的操作。下面我们来分析ArrayList的源代码：底层使用数组实现
Java代码&&
private&transient&Object[]&elementD
&2)构造方法：&
&& ArrayList提供了三种方式的构造器，可以构造一个默认初始容量为10的空列表、构造一个指定初始容量的空列表以及构造一个包含指定collection的元素的列表，这些元素按照该collection的迭代器返回它们的顺序排列的。
Java代码&&
1.&&&&&public&ArrayList()&{&&
2.&&&&&&&&&this(10);&&
3.&&&&&}&&
5.&&&&&public&ArrayList(int&initialCapacity)&{&&
6.&&&&&&&&&super();&&
7.&&&&&&&&&if&(initialCapacity&&&0)&&
8.&&&&&&&&&&&&&throw&new&IllegalArgumentException(&Illegal&Capacity:&&+&initialCapacity);&&
9.&&&&&&&&&this.elementData&=&new&Object[initialCapacity];&&
12.& public&ArrayList(Collection&?&extends&E&&c)&{&&
13.& &&&&elementData&=&c.toArray();&&
14.& &&&&size&=&elementData.&&
15.& &&&&//&c.toArray&might&(incorrectly)¬&return&Object[]&(see&6260652)&&
16.& &&&&if&(elementData.getClass()&!=&Object[].class)&&
17.& &&&&&&&&elementData&=&Arrays.copyOf(elementData,&size,&Object[].class);&&
&& ArrayList提供了set(int index, E element)、add(E e)、add(int index, E element)、addAll(Collection&?extends E& c)、addAll(int index, Collection&?extends E& c)这些添加元素的方法。下面我们一一讲解：
Java代码&&
1.&&&&&//&用指定的元素替代此列表中指定位置上的元素，并返回以前位于该位置上的元素。&&
2.&&&&&public&E&set(int&index,&E&element)&{&&
3.&&&&&&&&&RangeCheck(index);&&
5.&&&&&&&&&E&oldValue&=&(E)&elementData[index];&&
6.&&&&&&&&&elementData[index]&=&&&
7.&&&&&&&&&return&oldV&&
8.&&&&&} &
Java代码&&
1.&&&&&//&将指定的元素添加到此列表的尾部。&&
2.&&&&&public&boolean&add(E&e)&{&&
3.&&&&&&&&&ensureCapacity(size&+&1);&&&
4.&&&&&&&&&elementData[size++]&=&e;&&
5.&&&&&&&&&return&&&
6.&&&&&} &
Java代码&&
1.&&&&&//&将指定的元素插入此列表中的指定位置。&&
2.&&&&&//&如果当前位置有元素，则向右移动当前位于该位置的元素以及所有后续元素（将其索引加1）。&&
3.&&&&&public&void&add(int&index,&E&element)&{&&
4.&&&&&&&&&if&(index&&&size&||&index&&&0)&&
5.&&&&&&&&&&&&&throw&new&IndexOutOfBoundsException(&Index:&&+index+&,&Size:&&+size);&&
6.&&&&&&&&&//&如果数组长度不足，将进行扩容。&&
7.&&&&&&&&&ensureCapacity(size+1);&&//&Increments&modCount!!&&
8.&&&&&&&&&//&将&elementData中从Index位置开始、长度为size-index的元素，&&
9.&&&&&&&&&//&拷贝到从下标为index+1位置开始的新的elementData数组中。&&
10.& &&&&//&即将当前位于该位置的元素以及所有后续元素右移一个位置。&&
11.& &&&&System.arraycopy(elementData,&index,&elementData,&index&+&1,&size&-&index);&&
12.& &&&&elementData[index]&=&&&
13.& &&&&size++;&&
Java代码&&
1.&&&&&//&按照指定collection的迭代器所返回的元素顺序，将该collection中的所有元素添加到此列表的尾部。&&
2.&&&&&public&boolean&addAll(Collection&?&extends&E&&c)&{&&
3.&&&&&&&&&Object[]&a&=&c.toArray();&&
4.&&&&&&&&&int&numNew&=&a.&&
5.&&&&&&&&&ensureCapacity(size&+&numNew);&&//&Increments&modCount&&
6.&&&&&&&&&System.arraycopy(a,&0,&elementData,&size,&numNew);&&
7.&&&&&&&&&size&+=&numN&&
8.&&&&&&&&&return&numNew&!=&0;&&
9.&&&&&}&&
Java代码&&
1.&&&&&//&从指定的位置开始，将指定collection中的所有元素插入到此列表中。&&
2.&&&&&public&boolean&addAll(int&index,&Collection&?&extends&E&&c)&{&&
3.&&&&&&&&&if&(index&&&size&||&index&&&0)&&
4.&&&&&&&&&&&&&throw&new&IndexOutOfBoundsException(&&
5.&&&&&&&&&&&&&&&&&&Index:&&&+&index&+&&,&Size:&&&+&size);&&
7.&&&&&&&&&Object[]&a&=&c.toArray();&&
8.&&&&&&&&&int&numNew&=&a.&&
9.&&&&&&&&&ensureCapacity(size&+&numNew);&&//&Increments&modCount&&
11.& &&&&int&numMoved&=&size&-&&&
12.& &&&&if&(numMoved&&&0)&&
13.& &&&&&&&&System.arraycopy(elementData,&index,&elementData,&index&+&numNew,&numMoved);&&
15.& &&&&System.arraycopy(a,&0,&elementData,&index,&numNew);&&
16.& &&&&size&+=&numN&&
17.& &&&&return&numNew&!=&0;&&
Java代码&&
1.&&&&&//&返回此列表中指定位置上的元素。&&
2.&&&&&public&E&get(int&index)&{&&
3.&&&&&&&&&RangeCheck(index);&&
5.&&&&&&&&&return&(E)&elementData[index];&&
6.&&&&&}&&
&&& 5) 删除：&
&& ArrayList提供了根据下标或者指定对象两种方式的删除功能。如下：
Java代码&&
1.&&&&&//&移除此列表中指定位置上的元素。&&
2.&&&&&public&E&remove(int&index)&{&&
3.&&&&&&&&&RangeCheck(index);&&
5.&&&&&&&&&modCount++;&&
6.&&&&&&&&&E&oldValue&=&(E)&elementData[index];&&
8.&&&&&&&&&int&numMoved&=&size&-&index&-&1;&&
9.&&&&&&&&&if&(numMoved&&&0)&&
10.& &&&&&&&&System.arraycopy(elementData,&index+1,&elementData,&index,&numMoved);&&
11.& &&&&elementData[--size]&=&&//&Let&gc&do&its&work&&
13.& &&&&return&oldV&&
Java代码&&
1.&&&&&//&移除此列表中首次出现的指定元素（如果存在）。这是应为ArrayList中允许存放重复的元素。&&
2.&&&&&public&boolean&remove(Object&o)&{&&
3.&&&&&&&&&//&由于ArrayList中允许存放null，因此下面通过两种情况来分别处理。&&
4.&&&&&&&&&if&(o&==&null)&{&&
5.&&&&&&&&&&&&&for&(int&index&=&0;&index&&&&index++)&&
6.&&&&&&&&&&&&&&&&&if&(elementData[index]&==&null)&{&&
7.&&&&&&&&&&&&&&&&&&&&&//&类似remove(int&index)，移除列表中指定位置上的元素。&&
8.&&&&&&&&&&&&&&&&&&&&&fastRemove(index);&&
9.&&&&&&&&&&&&&&&&&&&&&return&&&
10.& &&&&&&&&&&&&}&&
11.& }&else&{&&
12.& &&&&for&(int&index&=&0;&index&&&&index++)&&
13.& &&&&&&&&if&(o.equals(elementData[index]))&{&&
14.& &&&&&&&&&&&&fastRemove(index);&&
15.& &&&&&&&&&&&&return&&&
16.& &&&&&&&&}&&
17.& &&&&}&&
18.& &&&&return&&&
&&& 注意：从数组中移除元素的操作，也会导致被移除的元素以后的所有元素的向左移动一个位置。
&&&6) 调整数组容量：&
&& 从上面介绍的向ArrayList中存储元素的代码中，我们看到，每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。数组扩容通过一个公开的方法ensureCapacity(int minCapacity)来实现。在实际添加大量元素前，我也可以使用ensureCapacity来手动增加ArrayList实例的容量，以减少递增式再分配的数量。
Java代码&&
1.&&&&&public&void&ensureCapacity(int&minCapacity)&{&&
2.&&&&&&&&&modCount++;&&
3.&&&&&&&&&int&oldCapacity&=&elementData.&&
4.&&&&&&&&&if&(minCapacity&&&oldCapacity)&{&&
5.&&&&&&&&&&&&&Object&oldData[]&=&elementD&&
6.&&&&&&&&&&&&&int&newCapacity&=&(oldCapacity&*&3)/2&+&1;&&
7.&&&&&&&&&&&&&&&&&if&(newCapacity&&&minCapacity)&&
8.&&&&&&&&&&&&&&&&&&&&&newCapacity&=&minC&&
9.&&&&&&&&&&&//&minCapacity&is&usually&close&to&size,&so&this&is&a&win:&&
10.& &&&&&&elementData&=&Arrays.copyOf(elementData,&newCapacity);&&
11.& &&&&}&&
&& 从上述代码中可以看出，数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的1.5倍。这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时，要在构造ArrayList实例时，就指定其容量，以避免数组扩容的发生。或者根据实际需求，通过调用ensureCapacity方法来手动增加ArrayList实例的容量。
&& ArrayList还给我们提供了将底层数组的容量调整为当前列表保存的实际元素的大小的功能。它可以通过trimToSize方法来实现。代码如下：
Java代码&&
1.&&&&&public&void&trimToSize()&{&&
2.&&&&&&&&&modCount++;&&
3.&&&&&&&&&int&oldCapacity&=&elementData.&&
4.&&&&&&&&&if&(size&&&oldCapacity)&{&&
5.&&&&&&&&&&&&&elementData&=&Arrays.copyOf(elementData,&size);&&
6.&&&&&&&&&}&&
7.&&&&&}&&
&&&7) Fail-Fast机制：&
ArrayList也采用了快速失败的机制，通过记录modCount参数来实现。在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。具体介绍请参考我之前的文章&中的Fail-Fast机制。
&&&8) 关于其他&的一些方法的实现都很简单易懂，读者可参照API文档和源代码，一看便知，这里就不再多说。
ArrayList和的区别：
1.Vector是线程同步的，所以它也是线程安全的。而ArratList是线程异步的，不安全。如果不考虑安全因素，一般用Arralist效率比较高，查看JDK文档，给出提示：
& 如果要实现Arraylist线程同步，可以通过下面方式：
如果多个线程同时访问一个&ArrayList&实例，而其中至少一个线程从结构上修改了列表，那么它必须&保持外部同步。（结构上的修改是指任何添加或删除一个或多个元素的操作，或者显式调整底层数组的大小；仅仅设置元素的值不是结构上的修改。）这一般通过对自然封装该列表的对象进行同步操作来完成。如果不存在这样的对象，则应该使用&方法将该列表“包装”起来。这最好在创建时完成，以防止意外对列表进行不同步的访问：
&&&&&&& List list = Collections.synchronizedList(new ArrayList(...));
2.如果集合中的元素数量大于当前集合数组的长度时，Vector的增长率是目前数组长度的100%，而ArryaList增长率为目前数组长度的50%。所以，如果集合中使用数据量比较大的数据，用Vector有一定优势。
3.linkList
LinkedList与Collection关系如下图：
LinkedList的本质是双向链表。
(01) LinkedList继承于AbstractSequentialList，并且实现了Dequeue接口。
(02) LinkedList包含两个重要的成员：header 和 size。
header是双向链表的表头，它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量： previous, next, element。其中，previous是该节点的上一个节点，next是该节点的下一个节点，element是该节点所包含的值。
size是双向链表中节点的个数。
第3部分 LinkedList源码解析(基于JDK1.6.0_45)
为了更了解LinkedList的原理，下面对LinkedList源码代码作出分析。
在阅读源码之前，我们先对LinkedList的整体实现进行大致说明：
&&& LinkedList实际上是通过双向链表去实现的。既然是双向链表，那么它的顺序访问会非常高效，而随机访问效率比较低。
&&& 既然LinkedList是通过双向链表的，但是它也实现了List接口{也就是说，它实现了get(int location)、remove(int location)等“根据索引值来获取、删除节点的函数”}。LinkedList是如何实现List的这些接口的，如何将“双向链表和索引值联系起来的”？
&&& 实际原理非常简单，它就是通过一个计数索引值来实现的。例如，当我们调用get(int location)时，首先会比较“location”和“双向链表长度的1/2”；若前者大，则从链表头开始往后查找，直到location位置；否则，从链表末尾开始先前查找，直到location位置。
&& 这就是“双线链表和索引值联系起来”的方法。
好了，接下来开始阅读源码(只要理解双向链表，那么LinkedList的源码很容易理解的)。
& 1 package java.
& 3 public class LinkedList&E&
& 4&&&&extends AbstractSequentialList&E&
& 5&&&&implements List&E&, Deque&E&, Cloneable,java.io.Serializable
& 7&&&&// 链表的表头，表头不包含任何数据。Entry是个链表类数据结构。
& 8&&&&private transient Entry&E& header = new Entry&E&(null, null,null);
&10&&&&// LinkedList中元素个数
&11&&&&private transient int size = 0;
&13&&&&// 默认构造函数：创建一个空的链表
&14&&&&public LinkedList() {
&15&&&&&&&&header.next = header.previous =
&18&&&&// 包含“集合”的构造函数:创建一个包含“集合”的LinkedList
&19&&&&public LinkedList(Collection&? extends E& c) {
&20&&&&&&&&this();
&21&&&&&&&&addAll(c);
&24&&&&// 获取LinkedList的第一个元素
&25&&&&public E getFirst() {
&26&&&&&&&&if (size==0)
&27&&&&&&&&&&&&throw newNoSuchElementException();
&29&&&&&&&&// 链表的表头header中不包含数据。
&30&&&&&&&&// 这里返回header所指下一个节点所包含的数据。
&31&&&&&&&&return header.next.
&34&&&&// 获取LinkedList的最后一个元素
&35&&&&public E getLast()& {
&36&&&&&&&&if (size==0)
&37&&&&&&&&&&&&throw new NoSuchElementException();
&39&&&&&&&&// 由于LinkedList是双向链表；而表头header不包含数据。
&40&&&&&&&&// 因而，这里返回表头header的前一个节点所包含的数据。
&41&&&&&&&&return header.previous.
&44&&&&// 删除LinkedList的第一个元素
&45&&&&public E removeFirst() {
&46&&&&&&&&return remove(header.next);
&49&&&&// 删除LinkedList的最后一个元素
&50&&&&public E removeLast() {
&51&&&&&&&&return remove(header.previous);
&54&&&&// 将元素添加到LinkedList的起始位置
&55&&&&public void addFirst(E e) {
&56&&&&&&&&addBefore(e, header.next);
&59&&&&// 将元素添加到LinkedList的结束位置
&60&&&&public void addLast(E e) {
&61&&&&&&&&addBefore(e, header);
&64&&&&// 判断LinkedList是否包含元素(o)
&65&&&&public boolean contains(Object o) {
&66&&&&&&&&return indexOf(o) != -1;
&69&&&&// 返回LinkedList的大小
&70&&&&public int size() {
&71&&&&&&&&
&74&&&&// 将元素(E)添加到LinkedList中
&75&&&&public boolean add(E e) {
&76&&&&&&&&// 将节点(节点数据是e)添加到表头(header)之前。
&77&&&&&&&&// 即，将节点添加到双向链表的末端。
&78&&&&&&&&addBefore(e, header);
&79&&&&&&&&
&82&&&&// 从LinkedList中删除元素(o)
&83&&&&// 从链表开始查找，如存在元素(o)则删除该元素并返回true；
&84&&&&// 否则，返回false。
&85&&&&public boolean remove(Object o) {
&86&&&&&&&&if (o==null) {
&87&&&&&&&&&&&&// 若o为null的删除情况
&88&&&&&&&&&&&&for (Entry&E& e = header. e != e = e.next) {
&89&&&&&&&&&&&&&&&& if (e.element==null) {
&90&&&&&&&&&&&&&&&&&&&&remove(e);
&91&&&&&&&&&&&&&&&&&&&&
&92&&&&&&&&&&&&&&&& }
&93&&&&&&&&&&&&}
&94&&&&&&&&} else {
&95&&&&&&&&&&&&// 若o不为null的删除情况
&96&&&&&&&&&&&&for (Entry&E& e = header. e != e = e.next) {
&97&&&&&&&&&&&&&&&& if (o.equals(e.element)) {
&98&&&&&&&&&&&&&&&&&&&& remove(e);
&99&&&&&&&&&&&&&&&&&&&&
100&&&&&&&&&&&&&&&& }
101&&&&&&&&&&&& }
102&&&&&&&& }
103&&&&&&&&
106&&&& // 将“集合(c)”添加到LinkedList中。
107&&&& // 实际上，是从双向链表的末尾开始，将“集合(c)”添加到双向链表中。
108&&&& public boolean addAll(Collection&?extends E& c) {
109&&&&&&&& return addAll(size, c);
112&&&& // 从双向链表的index开始，将“集合(c)”添加到双向链表中。
113&&&& public boolean addAll(int index,Collection&? extends E& c) {
114&&&&&&&& if (index & 0 || index & size)
115&&&&&&&&&&&& throw newIndexOutOfBoundsException(&Index: &+index+
116&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&, Size: &+size);
117&&&&&&&& Object[] a = c.toArray();
118&&&&&&&& // 获取集合的长度
119&&&&&&&& int numNew = a.
120&&&&&&&& if (numNew==0)
121&&&&&&&&&&&&
122&&&&&&&& modCount++;
124&&&&&&&& // 设置“当前要插入节点的后一个节点”
125&&&&&&&& Entry&E& successor =(index==size ? header : entry(index));
126&&&&&&&& // 设置“当前要插入节点的前一个节点”
127&&&&& &&&Entry&E& predecessor =successor.
128&&&&&&&& // 将集合(c)全部插入双向链表中
129&&&&&&&& for (int i=0; i&numN i++) {
130&&&&&&&&&&&& Entry&E& e = newEntry&E&((E)a[i], successor, predecessor);
131&&&&&&&&&&&& predecessor.next =
132&&&&&&&&&&&& predecessor =
133&&&&&&&& }
134&&&&&&&& successor.previous =
136&&&&&&&& // 调整LinkedList的实际大小
137&&&&&&&& size += numN
138&&&&&&&&
141&&&& // 清空双向链表
142&&&& public void clear() {
143&&&&&&&& Entry&E& e = header.
144&&&&&&&& // 从表头开始，逐个向后遍历；对遍历到的节点执行一下操作：
145&&&&&&&& // (01) 设置前一个节点为null
146&&&&&&&& // (02) 设置当前节点的内容为null
147&&&&&&&& // (03) 设置后一个节点为“新的当前节点”
148&&&&&&&& while (e != header) {
149&&&&&&&&&&&& Entry&E& next = e.
150&&&&&&&&&&&& e.next = e.previous =
151&&&&&&&&&&&& e.element =
152&&&&&&&&&&&& e =
153&&&&&&&& }
154&&&&&&&& header.next = header.previous =
155&&&&&&&& // 设置大小为0
156&&&&&&&& size = 0;
157&&&&&&&& modCount++;
160&&&& // 返回LinkedList指定位置的元素
161&&&& public E get(int index) {
162&&&&&&&& return entry(index).
165&&&& // 设置index位置对应的节点的值为element
166&&&& public E set(int index, E element) {
167&&&&&&&& Entry&E& e = entry(index);
168&&&&&&&& E oldVal = e.
169&&&&&&&& e.element =
170&&&&&&&& return oldV
173&&&& // 在index前添加节点，且节点的值为element
174&&&& public void add(int index, E element) {
175&&&&&&&& addBefore(element, (index==size ?header : entry(index)));
178&&&& // 删除index位置的节点
179&&&& public E remove(int index) {
180&&&&&&&& return remove(entry(index));
183&&&& // 获取双向链表中指定位置的节点
184&&&& private Entry&E& entry(int index) {
185&&&&&&&& if (index & 0 || index &= size)
186&&&&&&&&&&&& throw newIndexOutOfBoundsException(&Index: &+index+
187&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&, Size: &+size);
188&&&&&&&& Entry&E& e =
189&&&&&&&& // 获取index处的节点。
190&&&&&&&& // 若index & 双向链表长度的1/2,则从前先后查找;
191&&&&&&&& // 否则，从后向前查找。
192&&&&&&& &if (index & (size && 1)) {
193&&&&&&&&&&&& for (int i = 0; i &=i++)
194&&&&&&&&&&&&&&&& e = e.
195&&&&&&&& } else {
196&&&&&&&&&&&& for (int i = i &i--)
197&&&&&&&&&&&&&&&& e = e.
198&&&&&&&& }
199&&&&&&&&
202&&&& // 从前向后查找，返回“值为对象(o)的节点对应的索引”
203&&&& // 不存在就返回-1
204&&&& public int indexOf(Object o) {
205&&&&&&&& int index = 0;
206&&&&&&&& if (o==null) {
207&&&&&&&&&&&& for (Entry e = header. e != e = e.next) {
208&&&&&&&&&&&&&&&& if (e.element==null)
209&&&&&&&&&&&&&&&&&&&&
210&&&&&&&&&&&&&&&& index++;
211&&&&&&&&&&&& }
212&&&&&&&& } else {
213&&&&&&&&&&&& for (Entry e = header. e != e = e.next) {
214&&&&&&&&&&&&&&&& if (o.equals(e.element))
215&&&&&&&&&&& &&&&&&&&&
216&&&&&&&&&&&&&&&& index++;
217&&&&&&&&&&&& }
218&&&&&&&& }
219&&&&&&&& return -1;
222&&&& // 从后向前查找，返回“值为对象(o)的节点对应的索引”
223&&&& // 不存在就返回-1
224&&&& public int lastIndexOf(Object o) {
225&&&&&&&& int index =
226&&&&&&&& if (o==null) {
227&&&&&&&&&&&& for (Entry e = header. e!= e = e.previous) {
228&&&&&&&&&&&&&&&& index--;
229&&&&&&&&&&&&&&&& if (e.element==null)
230&&&&&&&&&&&&&&&&&&&&
231&&&&&&&&&&&& }
232&&&&&&&& } else {
233&& &&&&&&&&&&for (Entry e = header. e != e = e.previous) {
234&&&&&&&&&&&&&&&& index--;
235&&&&&&&&&&&&&&&& if (o.equals(e.element))
236&&&&&&&&&&&&&&&&&&&&
237&&&&&&&&&&&& }
238&&&&&&&& }
239&&&&&&&& return -1;
242&&&& // 返回第一个节点
243&&&& // 若LinkedList的大小为0,则返回null
244&&&& public E peek() {
245&&&&&&&& if (size==0)
246&&&&&&&&&&&&
247&&&&&&&& return getFirst();
250&&&& // 返回第一个节点
251&&&& // 若LinkedList的大小为0,则抛出异常
252&&&& public E element() {
253&&&&&&&& return getFirst();
256&&&& // 删除并返回第一个节点
257&&&& // 若LinkedList的大小为0,则返回null
258&&&& public E poll() {
259&&&&&&&& if (size==0)
260&&&&&&&&&&&&
261&&&&&&&& return removeFirst();
264&&&& // 将e添加双向链表末尾
265&&&& public boolean offer(E e) {
266&&&&&&&& return add(e);
269&&&& // 将e添加双向链表开头
270&&&& public boolean offerFirst(E e) {
271&&&&&&&& addFirst(e);
272&&&&&&&&
275&&&& // 将e添加双向链表末尾
276&&&& public boolean offerLast(E e) {
277&&&&&&&& addLast(e);
278&&&&&&&&
281&&&& // 返回第一个节点
282&&&& // 若LinkedList的大小为0,则返回null
283&&&& public E peekFirst() {
284&&&&&&&& if (size==0)
285&&&&&&&&&&&&
286&&&&&&&& return getFirst();
289&&&& // 返回最后一个节点
290&&&& // 若LinkedList的大小为0,则返回null
291&&&& public E peekLast() {
292&&&&&&&& if (size==0)
293&&&&&&&&&&&&
294&&&&&&&& return getLast();
297&&&& // 删除并返回第一个节点
298&&&& // 若LinkedList的大小为0,则返回null
299&&&& public E pollFirst() {
300&&&&&&&& if (size==0)
301&&&&&&&&&&&&
302&&&&&&&& return removeFirst();
305&&&& // 删除并返回最后一个节点
306&&&& // 若LinkedList的大小为0,则返回null
307&&&& public E pollLast() {
308&&&&&&&& if (size==0)
309&&&&&&&&&&&&
310&&&&&&&& return removeLast();
313&&&& // 将e插入到双向链表开头
314&&&& public void push(E e) {
315&&&&&&&& addFirst(e);
318&&&& // 删除并返回第一个节点
319&&&& public E pop() {
320&&&&&&&& return removeFirst();
323&&&& // 从LinkedList开始向后查找，删除第一个值为元素(o)的节点
324&&&& // 从链表开始查找，如存在节点的值为元素(o)的节点，则删除该节点
325&&&& public booleanremoveFirstOccurrence(Object o) {
326&&&&&&&& return remove(o);
329&&&& // 从LinkedList末尾向前查找，删除第一个值为元素(o)的节点
330&&&& // 从链表开始查找，如存在节点的值为元素(o)的节点，则删除该节点
331&&&& public boolean removeLastOccurrence(Objecto) {
332&&&&&&&& if (o==null) {
333&&&&&&&&&&&& for (Entry&E& e =header. e != e = e.previous) {
334&&&&&&&&&&&&&&&& if (e.element==null) {
335&&&&&&&&&& &&&&&&&&&&remove(e);
336&&&&&&&&&&&&&&&&&&&&
337&&&&&&&&&&&&&&&& }
338&&&&&&&&&&&& }
339&&&&&&&& } else {
340&&&&&&&&&&&& for (Entry&E& e =header. e != e = e.previous) {
341&&&&&&&&&&&&&&&& if (o.equals(e.element)) {
342&&&& &&&&&&&&&&&&&&&&remove(e);
343&&&&&&&&&&&&&&&&&&&&
344&&&&&&&&&&&&&&&& }
345&&&&&&&&&&&& }
346&&&&&&&& }
347&&&&&&&&
350&&&& // 返回“index到末尾的全部节点”对应的ListIterator对象(List迭代器)
351&&&& public ListIterator&E& listIterator(intindex) {
352&&&&&&&& return new ListItr(index);
355&&&& // List迭代器
356&&&& private class ListItr implementsListIterator&E& {
357&&&&&&&& // 上一次返回的节点
358&&&&&&&& private Entry&E& lastReturned =
359&&&&&&&& // 下一个节点
360&&&&&&&& private Entry&E&
361&&&&&&&& // 下一个节点对应的索引值
362&&&&&&&& private int nextI
363&&&&&&&& // 期望的改变计数。用来实现fail-fast机制。
364&&&&&&&& private int expectedModCount =modC
366&&&&&&&& // 构造函数。
367&&&&&&&& // 从index位置开始进行迭代
368&&&&&&&& ListItr(int index) {
369&&&&&&&&&&&& // index的有效性处理
370&&&&&&&&&&&& if (index & 0 || index &size)
371&&&&&&&&&&&&&&&& throw newIndexOutOfBoundsException(&Index: &+index+ &, Size:&+size);
372&&&&&&&&&&&& // 若“index 小于‘双向链表长度的一半’”，则从第一个元素开始往后查找；
373&&& &&&&&&&&&// 否则，从最后一个元素往前查找。
374&&&&&&&&&&&& if (index & (size && 1)){
375&&&&&&&&&&&&&&&& next = header.
376&&&&&&&&&&&&&&&& for (nextIndex=0;nextIndex& nextIndex++)
377&&&&&&&&&&&&&&&&&&&& next = next.
378&&&&&&&&&&&& } else {
379&&&&&& &&&&&&&&&&next =
380&&&&&&&&&&&&&&&& for (nextIndex=nextIndex& nextIndex--)
381&&&&&&&&&&&&&&&&&&&& next = next.
382&&&&&&&&&&&& }
383&&&&&&&& }
385&&&&&&&& // 是否存在下一个元素
386&&&&&&&& public boolean hasNext() {
387&&&&&&&&& &&&// 通过元素索引是否等于“双向链表大小”来判断是否达到最后。
388&&&&&&&&&&&& return nextIndex !=
389&&&&&&&& }
391&&&&&&&& // 获取下一个元素
392&&&&&&&& public E next() {
393&&&&&&&&&&&& checkForComodification();
394&&&&&&&&&&&& if (nextIndex == size)
395&&&&&&&&&&&&&&&& throw newNoSuchElementException();
397&&&&&&&&&&&& lastReturned =
398&&&&&&&&&&&& // next指向链表的下一个元素
399&&&&&&&&&&&& next = next.
400&&&&&&&&&&&& nextIndex++;
401&&&&&&&&&&&& return lastReturned.
402&&&&&&&& }
404&&&&&&&& // 是否存在上一个元素
405&&&&&&&& public boolean hasPrevious() {
406&&&&&&&&&&&& // 通过元素索引是否等于0，来判断是否达到开头。
407&&&&&&&&&&&& return nextIndex != 0;
408&&&&&&&& }
410&&&&&&&& // 获取上一个元素
411&&&&&&&& public E previous() {
412&&&&&&&&&&&& if (nextIndex == 0)
413&&&&&&&&&&&& throw newNoSuchElementException();
415&&&&&&&&&&&& // next指向链表的上一个元素
416&&&&&&&&&&&& lastReturned = next =next.
417&&&&&&&&&&&& nextIndex--;
418&&&&&&&&&&&& checkForComodification();
419&&&&&&&&&&&& return lastReturned.
420&&&&&&&& }
422&&&&&&&& // 获取下一个元素的索引
423&&&&&&&& public int nextIndex() {
424&&&&&&&&&&&& return nextI
425&&&&&&&& }
427&&&&&&&& // 获取上一个元素的索引
428&&&&&&&& public int previousIndex() {
429&&&&&&&&&&&& return nextIndex-1;
430&&&&&&&& }
432&&&&&&& &// 删除当前元素。
433&&&&&&&& // 删除双向链表中的当前节点
434&&&&&&&& public void remove() {
435&&&&&&&&&&&& checkForComodification();
436&&&&&&&&&&&& Entry&E& lastNext =lastReturned.
437&&&&&&&&&&&& try {
438&&&&&&&&&&&&&&&&LinkedList.this.remove(lastReturned);
439 &&&&&&&&&&&&} catch (NoSuchElementException e){
440&&&&&&&&&&&&&&&& throw newIllegalStateException();
441&&&&&&&&&&&& }
442&&&&&&&&&&&& if (next==lastReturned)
443&&&&&&&&&&&&&&&& next = lastN
444&&&&&&&&&&&& else
445&&&&&&&&&&&&&&&& nextIndex--;
446&&&&&&&&&&&& lastReturned =
447&&&&&&&&&&&& expectedModCount++;
448&&&&&&&& }
450&&&&&&&& // 设置当前节点为e
451&&&&&&&& public void set(E e) {
452&&&&&&&&&&&& if (lastReturned == header)
453&&&&&&&&&&&&&&&& throw newIllegalStateException();
454&&& &&&&&&&&&checkForComodification();
455&&&&&&&&&&&& lastReturned.element =
456&&&&&&&& }
458&&&&&&&& // 将e添加到当前节点的前面
459&&&&&&&& public void add(E e) {
460&&&&&&&&&&&& checkForComodification();
461&&&&&&&&&&&& lastReturned =
462&&&&&&&&&&&& addBefore(e, next);
463&&&&&&&&&&&& nextIndex++;
464&&&&&&&&&&&& expectedModCount++;
465&&&&&&&& }
467&&&&&&&& // 判断“modCount和expectedModCount是否相等”，依次来实现fail-fast机制。
468&&&&&&&& final void checkForComodification() {
469&&&&&&&&&&&& if (modCount != expectedModCount)
470&&&&&&&&&&&& throw newConcurrentModificationException();
471&&&&&&&& }
474&&&& // 双向链表的节点所对应的数据结构。
475&&&& // 包含3部分：上一节点，下一节点，当前节点值。
476&&&& private static class Entry&E& {
477&&&&&&&& // 当前节点所包含的值
478&&&&&&&& E
479&&&&&&&& // 下一个节点
480&&&&&&&& Entry&E&
481&&&&&&&& // 上一个节点
482&&&&&&&& Entry&E&
484&&&&&&&& /**
485&&&&&&&&& * 链表节点的构造函数。
486&&&&&&&&& * 参数说明：
487&&&&&&&&& *&&element& —— 节点所包含的数据
488&&&&&&&&& *&&next&&&&& —— 下一个节点
489&&&&&&&&& *&&previous —— 上一个节点
490&&&&&&&&& */
491&&&&&&&& Entry(E element, Entry&E& next,Entry&E& previous) {
492&&&&&&&&&&&& this.element =
493&&&&&&&&&&&& this.next =
494&&&&&&&&&&&& this.previous =
495&&&&&&&& }
498&&&& // 将节点(节点数据是e)添加到entry节点之前。
499&&&& private Entry&E& addBefore(E e,Entry&E& entry) {
500&&&&&&&& // 新建节点newEntry，将newEntry插入到节点e之前；并且设置newEntry的数据是e
501&&&&&&&& Entry&E& newEntry = newEntry&E&(e, entry, entry.previous);
502&&&&&&&& newEntry.previous.next = newE
503&&&&&&&& newEntry.next.previous = newE
504&&&&&&&& // 修改LinkedList大小
505&&&&&&&& size++;
506&&&&&&&& // 修改LinkedList的修改统计数：用来实现fail-fast机制。
507&&&&&&&& modCount++;
508&&&&&&&& return newE
511&&&& // 将节点从链表中删除
512&&& &private E remove(Entry&E& e) {
513&&&&&&&& if (e == header)
514&&&&&&&&&&&& throw newNoSuchElementException();
516&&&&&&&& E result = e.
517&&&&&&&& e.previous.next = e.
518&&&&&&&& e.next.previous = e.
519&&&&&&&& e.next = e.previous =
520&&&&&&&& e.element =
521&&&&&&&& size--;
522&&&&&&&& modCount++;
523&&&&&&&&
526&&&& // 反向迭代器
527&&&& public Iterator&E&descendingIterator() {
528&&&&&&&& return new DescendingIterator();
531&&&& // 反向迭代器实现类。
532&&&& private class DescendingIteratorimplements Iterator {
533&&&&&&&& final ListItr itr = newListItr(size());
534&&&&&&&& // 反向迭代器是否下一个元素。
535&&&&&&&& // 实际上是判断双向链表的当前节点是否达到开头
536&&&&&&&& public boolean hasNext() {
537&&&&&&& &&&&&return itr.hasPrevious();
538&&&&&&&& }
539&&&&&&&& // 反向迭代器获取下一个元素。
540&&&&&&&& // 实际上是获取双向链表的前一个节点
541&&&&&&&& public E next() {
542&&&&&&&&&&&& return itr.previous();
543&&&&&&&& }
544&&&&&&&& // 删除当前节点
545&&&&&&&& public void remove() {
546&&&&&& &&&&&&itr.remove();
547&&&&&&&& }
551&&&& // 返回LinkedList的Object[]数组
552&&&& public Object[] toArray() {
553&&&& // 新建Object[]数组
554&&&& Object[] result = new Object[size];
555&&&&&&&& int i = 0;
556&&&&&&&& // 将链表中所有节点的数据都添加到Object[]数组中
557&&&&&&&& for (Entry&E& e = header. e!= e = e.next)
558&&&&&&&&&&&& result[i++] = e.
562&&&& // 返回LinkedList的模板数组。所谓模板数组，即可以将T设为任意的数据类型
563&&&& public &T& T[] toArray(T[] a) {
564&&&&&&&& // 若数组a的大小 & LinkedList的元素个数(意味着数组a不能容纳LinkedList中全部元素)
565&&&&&&&& // 则新建一个T[]数组，T[]的大小为LinkedList大小，并将该T[]赋值给a。
566&&&&&&&& if (a.length & size)
567&&&&&&&&&&&& a =(T[])java.lang.reflect.Array.newInstance(
568&&&&&&&&&&&&&&&&&&&&&& &&&&&&&&&&a.getClass().getComponentType(),size);
569&&&&&&&& // 将链表中所有节点的数据都添加到数组a中
570&&&&&&&& int i = 0;
571&&&&&&&& Object[] result =
572&&&&&&&& for (Entry&E& e = header. e!= e = e.next)
573&&&&&&&&&&&& result[i++] = e.
575&&&&&&&& if (a.length & size)
576&&&&&&&&&&&& a[size] =
578&&&&&&&&
582&&&& // 克隆函数。返回LinkedList的克隆对象。
583&&&& public Object clone() {
584&&&&&&&& LinkedList&E& clone =
585&&&&&&&& // 克隆一个LinkedList克隆对象
586 &&&&&&&&try {
587&&&&&&&&&&&& clone = (LinkedList&E&)super.clone();
588&&&&&&&& } catch (CloneNotSupportedException e){
589&&&&&&&&&&&& throw new InternalError();
590&&&&&&&& }
592&&&&&&&& // 新建LinkedList表头节点
593&&&&&&&& clone.header = new Entry&E&(null,null, null);
594&&&&&&&& clone.header.next =clone.header.previous = clone.
595&&&&&&&& clone.size = 0;
596&&&&&&&& clone.modCount = 0;
598&&&&&&&& // 将链表中所有节点的数据都添加到克隆对象中
599&&&&&&&& for (Entry&E& e = header. e!= e = e.next)
600&&&&&&&&&&&& clone.add(e.element);
602&&&&&&&&
605&&&& // java.io.Serializable的写入函数
606&&&& // 将LinkedList的“容量，所有的元素值”都写入到输出流中
607&&&& private voidwriteObject(java.io.ObjectOutputStream s)
608&&&&&&&& throws java.io.IOException {
609&&&&&&&& // Write out any hidden serializationmagic
610&&&&&&&& s.defaultWriteObject();
612&&&&&&&& // 写入“容量”
613&&&&&&&& s.writeInt(size);
615&&&&&&&& // 将链表中所有节点的数据都写入到输出流中
616&&&&&&&& for (Entry e = header. e !=e = e.next)
617&&&&&&&&&&&& s.writeObject(e.element);
620&&&& // java.io.Serializable的读取函数：根据写入方式反向读出
621&&&& // 先将LinkedList的“容量”读出，然后将“所有的元素值”读出
622&&&& private voidreadObject(java.io.ObjectInputStream s)
623&&&&&&&& throws java.io.IOException,ClassNotFoundException {
624&&&&&&&& // Read in any hidden serializationmagic
625&&&&&&&& s.defaultReadObject();
627&&&&&&&& // 从输入流中读取“容量”
628&&&&&&&& int size = s.readInt();
630&&&&&&&& // 新建链表表头节点
631&&&&&&&& header = new Entry&E&(null,null, null);
632&&&&&&&& header.next = header.previous =
634&&&&&&&& // 从输入流中将“所有的元素值”并逐个添加到链表中
635&&&&&&&& for (int i=0; i& i++)
636&&&&&&&&&&&& addBefore((E)s.readObject(),header);
(01) LinkedList 实际上是通过双向链表去实现的。
&&&&&&& 它包含一个非常重要的内部类：Entry。Entry是双向链表节点所对应的数据结构，它包括的属性有：当前节点所包含的值，上一个节点，下一个节点。
(02) 从LinkedList的实现方式中可以发现，它不存在LinkedList容量不足的问题。
(03) LinkedList的克隆函数，即是将全部元素克隆到一个新的LinkedList对象中。
(04) LinkedList实现java.io.Serializable。当写入到输出流时，先写入“容量”，再依次写入“每一个节点保护的值”；当读出输入流时，先读取“容量”，再依次读取“每一个元素”。
(05) 由于LinkedList实现了Deque，而Deque接口定义了在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。每种方法都存在两种形式：一种形式在操作失败时抛出异常，另一种形式返回一个特殊值（null 或 false，具体取决于操作）。
总结起来如下表格：
&&&&&&& 第一个元素（头部）&&&&&&&&&&&&&&&&最后一个元素（尾部）
&&&&&&& 抛出异常&&&&&&& 特殊值&&&&&&&&&&&抛出异常&&&&&&&&&&特殊值
插入&&&addFirst(e)&&& offerFirst(e)&&& addLast(e)&&&&&&& offerLast(e)
移除&&&removeFirst()& pollFirst()&&&&& removeLast()&&&&& pollLast()
检查&&&getFirst()&&&& peekFirst()&&&&& getLast()&&&&&&&& peekLast()
(06) LinkedList可以作为FIFO(先进先出)的队列，作为FIFO的队列时，下表的方法等价：
队列方法&&&&&&等效方法
add(e)&&&&&&& addLast(e)
offer(e)&&&&& offerLast(e)
remove()&&&&& removeFirst()
poll()&&&&&&& pollFirst()
element()&&&& getFirst()
peek()&&&&&&& peekFirst()
(07) LinkedList可以作为LIFO(后进先出)的栈，作为LIFO的栈时，下表的方法等价：
栈方法&&&&&&&等效方法
push(e)&&&&& addFirst(e)
pop()&&&&&&& removeFirst()
peek()&&&&&& peekFirst()
无论如何，千万不要通过随机访问去遍历LinkedList！
相对于ArrayList来说，Vector线程是安全的，也就是说是同步的
创建了一个向量类的对象后，可以往其中随意地插入不同的类的对象，既不需顾及类型也不需预先选定向量的容量，并可方便地进行查找。对于预先不知或不愿预先定义数组大小，并需频繁进行查找、插入和删除工作的情况，可以考虑使用向量类。向量类提供了三种构造方法：
public vector()
public vector(intinitialcapacity,int capacityIncrement)
public vector(intinitialcapacity)
使用第一种方法，系统会自动对向量对象进行管理。若使用后两种方法，则系统将根据参数initialcapacity设定向量对象的容量（即向量对象可存储数据的大小），当真正存放的数据个数超过容量时，系统会扩充向量对象的储存容量。
参数capacityIncrement给定了每次扩充的扩充值。当capacityIncrement为0时，则每次扩充一倍。利用这个功能可以优化存储。在Vector类中提供了各种方法方便用户使用：
JAVA_Admin_User
排名：千里之外
