Java中常用的List子类主要有：ArrayList、LinkedList、Vector。有序（存储和取出的元素一致），可重复的。
三者比较
1：访问：ArrayList和Vector都实现了RandomAccess接口，提供了随机访问功能，查询O（1）;LinkedList是链表，查询O（n）;
2：增删：ArrayList和Vector底层是数组，增删容易引起大量的内存操作，效率较慢；LinkedList是链表实现，增加和删除较快；
3：线程安全性：Vector是线程安全的，大部分的方法都用了syncrhoized关键字修饰。如果是单线程下使用，可以用Arrayist，如果是多线程操作的list，则可以用Vector来保证线程安全。
4：ArrayList每次扩容增加50%，Vector扩容增加一倍。
一：ArrayList
ArrayList实现了List接口，实现了一系列的add()/get()/clear()/remove()等接口中的方法。其底层其实是一个数组，通过对数组上一系列操作的封装来实现list的各种功能的。
1：ArrayList 实际上是通过一个数组去保存数据的。当我们构造ArrayList时；若使用默认构造函数，则ArrayList的默认容量大小是10。
2：当ArrayList容量不足以容纳全部元素时，ArrayList扩容：新的容量=“(原始容量x3)/2 + 1”。创建新容量大小的数组并把原数组内容复制过去。
3：底层数据结构是数组，查询快，增删慢。线程不安全，效率高。
底层源码：
package java.util; public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
// 序列版本号
private static final long serialVersionUID = 8683452581122892189L; // 保存ArrayList中数据的数组
private transient Object[] elementData; // ArrayList中实际数据的数量
private int size; // ArrayList带容量大小的构造函数。
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
// 新建一个数组
this.elementData = new Object[initialCapacity];
} // ArrayList构造函数。默认容量是10。
public ArrayList() {
this(10);
} // 创建一个包含collection的ArrayList
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} // 将当前容量值设为 =实际元素个数
public void trimToSize() {
modCount++;
int oldCapacity = elementData.length;
if (size < oldCapacity) {
elementData = Arrays.copyOf(elementData, size);
}
} // 确定ArrarList的容量。
// 若ArrayList的容量不足以容纳当前的全部元素，设置 新的容量=“(原始容量x3)/2 + 1”
public void ensureCapacity(int minCapacity) {
// 将“修改统计数”+1
modCount++;
int oldCapacity = elementData.length;
// 若当前容量不足以容纳当前的元素个数，设置 新的容量=“(原始容量x3)/2 + 1”
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
elementData = Arrays.copyOf(elementData, newCapacity);
}
} // 添加元素e
public boolean add(E e) {
// 确定ArrayList的容量大小
ensureCapacity(size + 1); // Increments modCount!!
// 添加e到ArrayList中
elementData[size++] = e;
return true;
} // 返回ArrayList的实际大小
public int size() {
return size;
} // 返回ArrayList是否包含Object(o)
public boolean contains(Object o) {
return indexOf(o) >= 0;
} // 返回ArrayList是否为空
public boolean isEmpty() {
return size == 0;
} // 正向查找，返回元素的索引值
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
} // 反向查找，返回元素的索引值
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
} // 反向查找(从数组末尾向开始查找)，返回元素(o)的索引值
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
} // 返回ArrayList的Object数组
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
} // 返回ArrayList的模板数组。所谓模板数组，即可以将T设为任意的数据类型
public <T> T[] toArray(T[] a) {
// 若数组a的大小 < ArrayList的元素个数；
// 则新建一个T[]数组，数组大小是“ArrayList的元素个数”，并将“ArrayList”全部拷贝到新数组中
if (a.length < size)
return (T[]) Arrays.copyOf(elementData, size, a.getClass()); // 若数组a的大小 >= ArrayList的元素个数；
// 则将ArrayList的全部元素都拷贝到数组a中。
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
} // 获取index位置的元素值
public E get(int index) {
RangeCheck(index); return (E) elementData[index];
} // 设置index位置的值为element
public E set(int index, E element) {
RangeCheck(index); E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
} // 将e添加到ArrayList中
public boolean add(E e) {
ensureCapacity(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
} // 将e添加到ArrayList的指定位置
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(
"Index: "+index+", Size: "+size); ensureCapacity(size+1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
} // 删除ArrayList指定位置的元素
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;
} // 删除ArrayList的指定元素
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
} // 快速删除第index个元素
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
// 从"index+1"开始，用后面的元素替换前面的元素。
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 将最后一个元素设为null
elementData[--size] = null; // Let gc do its work
} // 删除元素
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
// 便利ArrayList，找到“元素o”，则删除，并返回true。
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
} // 清空ArrayList，将全部的元素设为null
public void clear() {
modCount++; for (int i = 0; i < size; i++)
elementData[i] = null; size = 0;
} // 将集合c追加到ArrayList中
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacity(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
} // 从index位置开始，将集合c添加到ArrayList
public boolean addAll(int index, Collection<? extends E> c) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(
"Index: " + index + ", Size: " + size); Object[] a = c.toArray();
int numNew = a.length;
ensureCapacity(size + numNew); // Increments modCount int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved); System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
} // 删除fromIndex到toIndex之间的全部元素。
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved); // Let gc do its work
int newSize = size - (toIndex-fromIndex);
while (size != newSize)
elementData[--size] = null;
} private void RangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(
"Index: "+index+", Size: "+size);
} // 克隆函数
public Object clone() {
try {
ArrayList<E> v = (ArrayList<E>) super.clone();
// 将当前ArrayList的全部元素拷贝到v中
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError();
}
} // java.io.Serializable的写入函数
// 将ArrayList的“容量，所有的元素值”都写入到输出流中
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject(); // 写入“数组的容量”
s.writeInt(elementData.length); // 写入“数组的每一个元素”
for (int i=0; i<size; i++)
s.writeObject(elementData[i]); if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
} } // java.io.Serializable的读取函数：根据写入方式读出
// 先将ArrayList的“容量”读出，然后将“所有的元素值”读出
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in size, and any hidden stuff
s.defaultReadObject(); // 从输入流中读取ArrayList的“容量”
int arrayLength = s.readInt();
Object[] a = elementData = new Object[arrayLength]; // 从输入流中将“所有的元素值”读出
for (int i=0; i<size; i++)
a[i] = s.readObject();
}
}
Java中对ArrayList集合的常用操作
1.list中添加，获取，删除元素；
2.list中是否包含某个元素；
3.list中根据索引将元素数值改变(替换)；
4.list中查看（判断）元素的索引；
5.根据元素索引位置进行的判断；
6.利用list中索引位置重新生成一个新的list（截取集合）；
7.对比两个list中的所有元素；
8.判断list是否为空；
9.返回Iterator集合对象；
10.将集合转换为字符串；
11.将集合转换为数组；
12.集合类型转换；
备注：内容中代码具有关联性。
.list中添加，获取，删除元素；
添加方法是：.add(e)；
获取方法是：.get(index)；
按照索引删除方法是：.remove(index)
按照元素内容删除方法是：.remove(Object o)； List<String> person=new ArrayList<>();
person.add("jackie"); //索引为0 //.add(e)
person.add("peter"); //索引为1
person.add("annie"); //索引为2
person.add("martin"); //索引为3
person.add("marry"); //索引为4 person.remove(3); //.remove(index)
person.remove("marry"); //.remove(Object o) String per="";
per=person.get(1);
System.out.println(per); //.get(index) for (int i = 0; i < person.size(); i++) {
System.out.println(person.get(i)); //.get(index)
}
.list中是否包含某个元素；
方法：.contains(Object o)； 返回true或者false List<String> fruits=new ArrayList<>();
fruits.add("苹果");
fruits.add("香蕉");
fruits.add("桃子");
//for循环遍历list
for (int i = 0; i < fruits.size(); i++) {
System.out.println(fruits.get(i));
}
String appleString="苹果";
//true or false
System.out.println("fruits中是否包含苹果："+fruits.contains(appleString)); if (fruits.contains(appleString)) {
System.out.println("我喜欢吃苹果");
}else {
System.out.println("我不开心");
} .list中根据索引将元素数值改变(替换)；
注意 .set(index, element); 和 .add(index, element); 的不同； String a="白龙马", b="沙和尚", c="八戒", d="唐僧", e="悟空";
List<String> people=new ArrayList<>();
people.add(a);
people.add(b);
people.add(c);
people.set(0, d); //.set(index, element); //将d唐僧放到list中索引为0的位置，替换a白龙马
people.add(1, e); //.add(index, element); //将e悟空放到list中索引为1的位置,原来位置的b沙和尚后移一位 //增强for循环遍历list
for(String str:people){
System.out.println(str);
}
.list中查看（判断）元素的索引；
注意：indexOf()和lastIndexOf()的不同； List<String> names=new ArrayList<>();
names.add("刘备"); //索引为0
names.add("关羽"); //索引为1
names.add("张飞"); //索引为2
names.add("刘备"); //索引为3
names.add("张飞"); //索引为4
System.out.println(names.indexOf("刘备"));
System.out.println(names.lastIndexOf("刘备"));
System.out.println(names.indexOf("张飞"));
System.out.println(names.lastIndexOf("张飞")); 5.根据元素索引位置进行的判断; if (names.indexOf("刘备")==0) {
System.out.println("刘备在这里");
}else if (names.lastIndexOf("刘备")==3) {
System.out.println("刘备在那里");
}else {
System.out.println("刘备到底在哪里？");
} .利用list中索引位置重新生成一个新的list（截取集合）；
方法： .subList(fromIndex,toIndex)；.size()；该方法得到list中的元素数的和 List<String> phone=new ArrayList<>();
phone.add("三星"); //索引为0
phone.add("苹果"); //索引为1
phone.add("锤子"); //索引为2
phone.add("华为"); //索引为3
phone.add("小米"); //索引为4
//原list进行遍历
for(String pho:phone){
System.out.println(pho);
}
//生成新list
phone=phone.subList(1, 4); //.subList(fromIndex, toIndex) //利用索引1-4的对象重新生成一个list，但是不包含索引为4的元素，4-1=3
for (int i = 0; i < phone.size(); i++) { // phone.size() 该方法得到list中的元素数的和
System.out.println("新的list包含的元素是"+phone.get(i));
}
7.对比两个list中的所有元素；
//两个相等对象的equals方法一定为true, 但两个hashcode相等的对象不一定是相等的对象 //1.<BR>if (person.equals(fruits)) {
System.out.println("两个list中的所有元素相同");
}else {
System.out.println("两个list中的所有元素不一样");
}
//2.
if (person.hashCode()==fruits.hashCode()) {
System.out.println("我们相同");
}else {
System.out.println("我们不一样");
} .判断list是否为空； //空则返回true，非空则返回false if (person.isEmpty()) {
System.out.println("空的");
}else {
System.out.println("不是空的");
} .返回Iterator集合对象； System.out.println("返回Iterator集合对象:"+person.iterator()); .将集合转换为字符串； String liString="";
liString=person.toString();
System.out.println("将集合转换为字符串:"+liString); .将集合转换为数组； System.out.println("将集合转换为数组:"+person.toArray()); 12.集合类型转换； //1.默认类型
List<Object> listsStrings=new ArrayList<>();
for (int i = 0; i < person.size(); i++) {
listsStrings.add(person.get(i));
}
//2.指定类型
List<StringBuffer> lst=new ArrayList<>();
for(String string:person){
lst.add(StringBuffer(string));
}
二：LinkedList
LinkedList通过另一种方式实现List接口，不仅如此，它还实现了 Queue、Deque接口，使得LinkedList可以作为栈、队列、双端队列来使用。
LinkedList底层是一个双向链表。其对于 List、Queue、Deque接口中的方法都是通过封装在链表上的操作来实现的。查询慢，增删快。线程不安全，效率高。
底层源码：
package com.chy.collection.core;
import java.util.AbstractSequentialList;
import java.util.Collections;
import java.util.ConcurrentModificationException;
import java.util.Deque;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Queue;
import java.util.Vector;
/**
* LinkedList实际上是通过双向链表去实现的、整个链表是通过Entry实体类来存储数据的
*/
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
//链表的表头、表头不包含任何数据、
//Entry是双向链表节点所对应的数据结构，它包括的属性有：当前节点所包含的值，上一个节点，下一个节点。
private transient Entry<E> header = new Entry<E>(null, null, null);
// LinkedList中元素个数
private transient int size = 0;
/**
* 构造一个空的LinkedList、只含有表头
*/
public LinkedList() {
header.next = header.previous = header;
}
/**
* 创建一个包含c的LinkedList、先创建默认空、然后将c中所有元素添加到LinkedList中
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
/** 获取链表第一个元素、*/
public E getFirst() {
if (size==0)
throw new NoSuchElementException();
//因其是双向链表、这里的header可视为顺序的第一个不含元素的表头、所以第一个是此header的下一个元素
return header.next.element;
}
/** 获取链表最后一个元素*/
public E getLast() {
if (size==0)
throw new NoSuchElementException();
//因其是双向链表、这里的header可视为逆序的第一个不含元素的表头、所以最后一个是此header的上一个元素
return header.previous.element;
}
/** 删除LinkedList的第一个元素*/
public E removeFirst() {
return remove(header.next);
}
/** 删除LinkedList的最后一个元素*/
public E removeLast() {
return remove(header.previous);
}
/** 将元素e添加到LinkedList的起始位置*/
public void addFirst(E e) {
addBefore(e, header.next);
}
/** 将元素e添加到LinkedList的结束位置*/
public void addLast(E e) {
addBefore(e, header);
}
/** 判断是否包含Object o*/
public boolean contains(Object o) {
return indexOf(o) != -1;
}
/** 返回LinkedList的大小*/
public int size() {
return size;
}
/** 将元素(E)添加到LinkedList中、添加到末尾*/
public boolean add(E e) {
addBefore(e, header);
return true;
}
/** 从LinkedList中删除o、如果存在则删除第一查找到的o并返回true、若不存在则返回false*/
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 {
for (Entry<E> e = header.next; e != header; e = e.next) {
if (o.equals(e.element)) {
remove(e);
return true;
}
}
}
return false;
}
/** 将c中元素添加到双向链表LinkedList中、从尾部开始添加*/
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
/** 将c中元素添加到双向链表LinkedList中、所有元素添加到index与index+1表示的元素中间*/
public boolean addAll(int index, Collection<? extends E> c) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size);
//将c转换成数组、方便遍历元素和获取元素个数
Object[] a = c.toArray();
int numNew = a.length;
if (numNew==0)
return false;
modCount++;
//设置当前要插入节点的下一个节点
Entry<E> successor = (index==size ? header : entry(index));
//设置当前要插入节点的上一个节点
Entry<E> predecessor = successor.previous;
//将c中元素插入到LinkedList中
for (int i=0; i<numNew; i++) {
Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);
predecessor.next = e;
predecessor = e;
}
successor.previous = predecessor;
size += numNew;
return true;
}
/** 删除LinkedList中所有元素*/
public void clear() {
Entry<E> e = header.next;
while (e != header) {
Entry<E> next = e.next;
e.next = e.previous = null;
e.element = null;
e = next;
}
header.next = header.previous = header;
size = 0;
modCount++;
}
// Positional Access Operations
/** 获取index处的元素*/
public E get(int index) {
return entry(index).element;
}
/** 设置index处的元素、并将old元素返回*/
public E set(int index, E element) {
Entry<E> e = entry(index);
E oldVal = e.element;
e.element = element;
return oldVal;
}
/** 在index前添加节点，且节点的值为element*/
public void add(int index, E element) {
addBefore(element, (index==size ? header : entry(index)));
}
/** 删除index位置的节点*/
public E remove(int index) {
return remove(entry(index));
}
/** 获取双向链表LinkedList中指定位置的节点、是LinkedList实现List中通过index操作元素的关键*/
private Entry<E> entry(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size);
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;
}
return e;
}
// Search Operations
/** 查询o所在LinkedList中的位置的索引、从前向后、不存在返回-1*/
public int indexOf(Object o) {
int index = 0;
if (o==null) {
for (Entry e = header.next; e != header; e = e.next) {
if (e.element==null)
return index;
index++;
}
} else {
for (Entry e = header.next; e != header; e = e.next) {
if (o.equals(e.element))
return index;
index++;
}
}
return -1;
}
/** 查询o所在LinkedList中的位置的索引、从后向前、不存在返回-1*/
public int lastIndexOf(Object o) {
int index = size;
if (o==null) {
for (Entry e = header.previous; e != header; e = e.previous) {
index--;
if (e.element==null)
return index;
}
} else {
for (Entry e = header.previous; e != header; e = e.previous) {
index--;
if (o.equals(e.element))
return index;
}
}
return -1;
}
// Queue operations.
/** 返回第一个节点、若size为0则返回null*/
public E peek() {
if (size==0)
return null;
return getFirst();
}
/** 返回第一个节点、若size为0则抛异常NoSuchElementException*/
public E element() {
return getFirst();
}
/** 删除并返回第一个节点 、若LinkedList的大小为0,则返回null*/
public E poll() {
if (size==0)
return null;
return removeFirst();
}
/** 删除第一个元素、若LinkedList的大小为0,则抛异常*/
public E remove() {
return removeFirst();
}
/** 将e添加双向链表末尾*/
public boolean offer(E e) {
return add(e);
}
// Deque operations
/** 将e添加双向链表开头*/
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
/** 将e添加双向链表末尾*/
public boolean offerLast(E e) {
addLast(e);
return true;
}
/**返回第一个节点、若LinkedList的大小为0,则返回null*/
public E peekFirst() {
if (size==0)
return null;
return getFirst();
}
/**返回最后一个节点、 若LinkedList的大小为0,则返回null*/
public E peekLast() {
if (size==0)
return null;
return getLast();
}
/** 删除并返回第一个、若LinkedList的大小为0,则返回null*/
public E pollFirst() {
if (size==0)
return null;
return removeFirst();
}
/** 删除并返回最后一个、若LinkedList的大小为0,则返回null*/
public E pollLast() {
if (size==0)
return null;
return removeLast();
}
/** 将e插入到双向链表开头*/
public void push(E e) {
addFirst(e);
}
/** 删除并返回第一个节点*/
public E pop() {
return removeFirst();
}
/** 从LinkedList中删除o、如果存在则删除第一查找到的o并返回true、若不存在则返回false*/
public boolean removeFirstOccurrence(Object o) {
return remove(o);
}
/** 从LinkedList末尾向前查找，删除第一个值为元素(o)的节点*/
public boolean removeLastOccurrence(Object o) {
if (o==null) {
for (Entry<E> e = header.previous; e != header; e = e.previous) {
if (e.element==null) {
remove(e);
return true;
}
}
} else {
for (Entry<E> e = header.previous; e != header; e = e.previous) {
if (o.equals(e.element)) {
remove(e);
return true;
}
}
}
return false;
}
/** 返回“index到末尾的全部节点”对应的ListIterator对象(List迭代器)*/
public ListIterator<E> listIterator(int index) {
return new ListItr(index);
}
private class ListItr implements ListIterator<E> {
// 上一次返回的节点
private Entry<E> lastReturned = header;
// 下一个节点
private Entry<E> next;
// 下一个节点对应的索引值
private int nextIndex;
// 期望的改变计数。用来实现fail-fast机制。
private int expectedModCount = modCount;
//构造函数、 从index位置开始进行迭代
ListItr(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size);
/*
* 若 “index 小于 ‘双向链表长度的一半’”，则从第一个元素开始往后查找；
* 否则，从最后一个元素往前查找。
*/
if (index < (size >> 1)) {
next = header.next;
for (nextIndex=0; nextIndex<index; nextIndex++)
next = next.next;
} else {
next = header;
for (nextIndex=size; nextIndex>index; nextIndex--)
next = next.previous;
}
}
// 是否存在下一个元素
public boolean hasNext() {
return nextIndex != size;
}
// 获取下一个元素
public E next() {
checkForComodification();
if (nextIndex == size)
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.element;
}
// 是否存在上一个元素
public boolean hasPrevious() {
return nextIndex != 0;
}
// 获取上一个元素
public E previous() {
if (nextIndex == 0)
throw new NoSuchElementException();
lastReturned = next = next.previous;
nextIndex--;
checkForComodification();
return lastReturned.element;
}
// 获取下一个元素的索引
public int nextIndex() {
return nextIndex;
}
// 获取上一个元素的索引
public int previousIndex() {
return nextIndex-1;
}
// 删除双向链表中的当前节点
public void remove() {
checkForComodification();
Entry<E> lastNext = lastReturned.next;
try {
LinkedList.this.remove(lastReturned);
} catch (NoSuchElementException e) {
throw new IllegalStateException();
}
if (next==lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = header;
expectedModCount++;
}
// 设置当前节点为e
public void set(E e) {
if (lastReturned == header)
throw new IllegalStateException();
checkForComodification();
lastReturned.element = e;
}
// 将e添加到当前节点的前面
public void add(E e) {
checkForComodification();
lastReturned = header;
addBefore(e, next);
nextIndex++;
expectedModCount++;
}
// 判断 “modCount和expectedModCount是否相等”，以此来实现fail-fast机制。
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
/**
* 内部静态类、是双向链表的节点所对应的数据结构、
* 此数据结构包含三部分：上一节点、下一节点、当前节点值
*/
private static class Entry<E> {
//当前节点值
E element;
//下一节点
Entry<E> next;
//上一节点
Entry<E> previous;
/**
* 链表节点构造函数
* @param element 节点值
* @param next 下一节点
* @param previous 上一节点
*/
Entry(E element, Entry<E> next, Entry<E> previous) {
this.element = element;
this.next = next;
this.previous = previous;
}
}
//新建节点、节点值是e、将新建的节点添加到entry之前
private Entry<E> addBefore(E e, Entry<E> entry) {
//觉得难理解的可以先花个几分钟看一下链式结构资料、最好是图片形式的
//新建节点实体
Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
//将参照节点原来的上一个节点（即插在谁前面的）的下一个节点设置成newEntry
newEntry.previous.next = newEntry;
//将参照节点（即插在谁前面的）的前一个节点设置成newEntry
newEntry.next.previous = newEntry;
size++;
modCount++;
return newEntry;
}
//将节点从链表中删除、返回被删除的节点的内容
private E remove(Entry<E> e) {
//如果是表头、抛异常
if (e == header)
throw new NoSuchElementException();
E result = e.element;
//下面实际上就是、将e拿掉、然后将e的上下两个节点连接起来
e.previous.next = e.next;
e.next.previous = e.previous;
e.next = e.previous = null;
e.element = null;
size--;
modCount++;
return result;
}
/**
* 反向迭代器
* @since 1.6
*/
public Iterator<E> descendingIterator() {
return new DescendingIterator();
}
/** 反向迭代器实现类 */
private class DescendingIterator implements Iterator {
final ListItr itr = new ListItr(size());
public boolean hasNext() {
return itr.hasPrevious();
}
public E next() {
return itr.previous();
}
public void remove() {
itr.remove();
}
}
/** 返回LinkedList的克隆对象*/
public Object clone() {
LinkedList<E> clone = null;
try {
clone = (LinkedList<E>) super.clone();
} catch (CloneNotSupportedException e) {
throw new InternalError();
}
// Put clone into "virgin" state
clone.header = new Entry<E>(null, null, null);
clone.header.next = clone.header.previous = clone.header;
clone.size = 0;
clone.modCount = 0;
// Initialize clone with our elements
for (Entry<E> e = header.next; e != header; e = e.next)
clone.add(e.element);
return clone;
}
/** 将LinkedList中的所有元素转换成Object[]中*/
public Object[] toArray() {
Object[] result = new Object[size];
int i = 0;
for (Entry<E> e = header.next; e != header; e = e.next)
result[i++] = e.element;
return result;
}
/** 将LinkedList中的所有元素转换成Object[]中、并且完成类型转换*/
public <T> T[] toArray(T[] a) {
if (a.length < size)
a = (T[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);
int i = 0;
Object[] result = a;
for (Entry<E> e = header.next; e != header; e = e.next)
result[i++] = e.element;
if (a.length > size)
a[size] = null;
return a;
}
private static final long serialVersionUID = 876323262645176354L;
/** 将LinkedList的“容量，所有的元素值”都写入到输出流中
* 1、将LinkedList的容量写入进去
* 2、将LinkedList中的所有元素写入进去
*/
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out any hidden serialization magic
s.defaultWriteObject();
// Write out size
s.writeInt(size);
// Write out all elements in the proper order.
for (Entry e = header.next; e != header; e = e.next)
s.writeObject(e.element);
}
/**
* 将写入的LinkedList读取出来
* 1、读取写入的LinkedList的容量
* 2、读取写入的元素
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in any hidden serialization magic
s.defaultReadObject();
// Read in size
int size = s.readInt();
// Initialize header
header = new Entry<E>(null, null, null);
header.next = header.previous = header;
// Read in all elements in the proper order.
for (int i=0; i<size; i++)
addBefore((E)s.readObject(), header);
}
}三：Vector
Vector也是在底层通过一个数组来保存数据，通过底层数组的一系列操作来实现List接口。同ArrayList一样，Vector底层数组容量不足时会扩容，然后把原有内容复制过去。底层数据结构是数组，查询快，增删慢。线程不安全，效率高。线程安全，效率低。
底层源码：
package java.util;
public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{ // 保存Vector中数据的数组
protected Object[] elementData;
// 实际数据的数量
protected int elementCount;
// 容量增长系数
protected int capacityIncrement;
// Vector的序列版本号
private static final long serialVersionUID = -2767605614048989439L;
// Vector构造函数。默认容量是10。
public Vector() {
this(10);
}
// 指定Vector容量大小的构造函数
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
// 指定Vector"容量大小"和"增长系数"的构造函数
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
// 新建一个数组，数组容量是initialCapacity
this.elementData = new Object[initialCapacity];
// 设置容量增长系数
this.capacityIncrement = capacityIncrement;
}
// 指定集合的Vector构造函数。
public Vector(Collection<? extends E> c) {
// 获取“集合(c)”的数组，并将其赋值给elementData
elementData = c.toArray();
// 设置数组长度
elementCount = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
}
// 将数组Vector的全部元素都拷贝到数组anArray中
public synchronized void copyInto(Object[] anArray) {
System.arraycopy(elementData, 0, anArray, 0, elementCount);
}
// 将当前容量值设为 =实际元素个数
public synchronized void trimToSize() {
modCount++;
int oldCapacity = elementData.length;
if (elementCount < oldCapacity) {
elementData = Arrays.copyOf(elementData, elementCount);
}
}
// 确认“Vector容量”的帮助函数
private void ensureCapacityHelper(int minCapacity) {
int oldCapacity = elementData.length;
// 当Vector的容量不足以容纳当前的全部元素，增加容量大小。
// 若 容量增量系数>0(即capacityIncrement>0)，则将容量增大当capacityIncrement
// 否则，将容量增大一倍。
if (minCapacity > oldCapacity) {
Object[] oldData = elementData;
int newCapacity = (capacityIncrement > 0) ?
(oldCapacity + capacityIncrement) : (oldCapacity * 2);
if (newCapacity < minCapacity) {
newCapacity = minCapacity;
}
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
// 确定Vector的容量。
public synchronized void ensureCapacity(int minCapacity) {
// 将Vector的改变统计数+1
modCount++;
ensureCapacityHelper(minCapacity);
}
// 设置容量值为 newSize
public synchronized void setSize(int newSize) {
modCount++;
if (newSize > elementCount) {
// 若 "newSize 大于 Vector容量"，则调整Vector的大小。
ensureCapacityHelper(newSize);
} else {
// 若 "newSize 小于/等于 Vector容量"，则将newSize位置开始的元素都设置为null
for (int i = newSize ; i < elementCount ; i++) {
elementData[i] = null;
}
}
elementCount = newSize;
}
// 返回“Vector的总的容量”
public synchronized int capacity() {
return elementData.length;
}
// 返回“Vector的实际大小”，即Vector中元素个数
public synchronized int size() {
return elementCount;
}
// 判断Vector是否为空
public synchronized boolean isEmpty() {
return elementCount == 0;
}
// 返回“Vector中全部元素对应的Enumeration”
public Enumeration<E> elements() {
// 通过匿名类实现Enumeration
return new Enumeration<E>() {
int count = 0;
// 是否存在下一个元素
public boolean hasMoreElements() {
return count < elementCount;
}
// 获取下一个元素
public E nextElement() {
synchronized (Vector.this) {
if (count < elementCount) {
return (E)elementData[count++];
}
}
throw new NoSuchElementException("Vector Enumeration");
}
};
}
// 返回Vector中是否包含对象(o)
public boolean contains(Object o) {
return indexOf(o, 0) >= 0;
} // 从index位置开始向后查找元素(o)。
// 若找到，则返回元素的索引值；否则，返回-1
public synchronized int indexOf(Object o, int index) {
if (o == null) {
// 若查找元素为null，则正向找出null元素，并返回它对应的序号
for (int i = index ; i < elementCount ; i++)
if (elementData[i]==null)
return i;
} else {
// 若查找元素不为null，则正向找出该元素，并返回它对应的序号
for (int i = index ; i < elementCount ; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
// 查找并返回元素(o)在Vector中的索引值
public int indexOf(Object o) {
return indexOf(o, 0);
}
// 从后向前查找元素(o)。并返回元素的索引
public synchronized int lastIndexOf(Object o) {
return lastIndexOf(o, elementCount-1);
}
// 从后向前查找元素(o)。开始位置是从前向后的第index个数；
// 若找到，则返回元素的“索引值”；否则，返回-1。
public synchronized int lastIndexOf(Object o, int index) {
if (index >= elementCount)
throw new IndexOutOfBoundsException(index + " >= "+ elementCount);
if (o == null) {
// 若查找元素为null，则反向找出null元素，并返回它对应的序号
for (int i = index; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
// 若查找元素不为null，则反向找出该元素，并返回它对应的序号
for (int i = index; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
// 返回Vector中index位置的元素。
// 若index月结，则抛出异常
public synchronized E elementAt(int index) {
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
}
return (E)elementData[index];
}
// 获取Vector中的第一个元素。
// 若失败，则抛出异常！
public synchronized E firstElement() {
if (elementCount == 0) {
throw new NoSuchElementException();
}
return (E)elementData[0];
}
// 获取Vector中的最后一个元素。
// 若失败，则抛出异常！
public synchronized E lastElement() {
if (elementCount == 0) {
throw new NoSuchElementException();
}
return (E)elementData[elementCount - 1];
}
// 设置index位置的元素值为obj
public synchronized void setElementAt(E obj, int index) {
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " +
elementCount);
}
elementData[index] = obj;
}
// 删除index位置的元素
public synchronized void removeElementAt(int index) {
modCount++;
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " +
elementCount);
} else if (index < 0) {
throw new ArrayIndexOutOfBoundsException(index);
}
int j = elementCount - index - 1;
if (j > 0) {
System.arraycopy(elementData, index + 1, elementData, index, j);
}
elementCount--;
elementData[elementCount] = null; /* to let gc do its work */
}
// 在index位置处插入元素(obj)
public synchronized void insertElementAt(E obj, int index) {
modCount++;
if (index > elementCount) {
throw new ArrayIndexOutOfBoundsException(index
+ " > " + elementCount);
}
ensureCapacityHelper(elementCount + 1);
System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
elementData[index] = obj;
elementCount++;
}
// 将“元素obj”添加到Vector末尾
public synchronized void addElement(E obj) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = obj;
}
// 在Vector中查找并删除元素obj。
// 成功的话，返回true；否则，返回false。
public synchronized boolean removeElement(Object obj) {
modCount++;
int i = indexOf(obj);
if (i >= 0) {
removeElementAt(i);
return true;
}
return false;
}
// 删除Vector中的全部元素
public synchronized void removeAllElements() {
modCount++;
// 将Vector中的全部元素设为null
for (int i = 0; i < elementCount; i++)
elementData[i] = null;
elementCount = 0;
}
// 克隆函数
public synchronized Object clone() {
try {
Vector<E> v = (Vector<E>) super.clone();
// 将当前Vector的全部元素拷贝到v中
v.elementData = Arrays.copyOf(elementData, elementCount);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError();
}
}
// 返回Object数组
public synchronized Object[] toArray() {
return Arrays.copyOf(elementData, elementCount);
}
// 返回Vector的模板数组。所谓模板数组，即可以将T设为任意的数据类型
public synchronized <T> T[] toArray(T[] a) {
// 若数组a的大小 < Vector的元素个数；
// 则新建一个T[]数组，数组大小是“Vector的元素个数”，并将“Vector”全部拷贝到新数组中
if (a.length < elementCount)
return (T[]) Arrays.copyOf(elementData, elementCount, a.getClass());
// 若数组a的大小 >= Vector的元素个数；
// 则将Vector的全部元素都拷贝到数组a中。
System.arraycopy(elementData, 0, a, 0, elementCount);
if (a.length > elementCount)
a[elementCount] = null;
return a;
}
// 获取index位置的元素
public synchronized E get(int index) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
return (E)elementData[index];
}
// 设置index位置的值为element。并返回index位置的原始值
public synchronized E set(int index, E element) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
Object oldValue = elementData[index];
elementData[index] = element;
return (E)oldValue;
}
// 将“元素e”添加到Vector最后。
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
// 删除Vector中的元素o
public boolean remove(Object o) {
return removeElement(o);
}
// 在index位置添加元素element
public void add(int index, E element) {
insertElementAt(element, index);
}
// 删除index位置的元素，并返回index位置的原始值
public synchronized E remove(int index) {
modCount++;
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
Object oldValue = elementData[index];
int numMoved = elementCount - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--elementCount] = null; // Let gc do its work
return (E)oldValue;
}
// 清空Vector
public void clear() {
removeAllElements();
}
// 返回Vector是否包含集合c
public synchronized boolean containsAll(Collection<?> c) {
return super.containsAll(c);
}
// 将集合c添加到Vector中
public synchronized boolean addAll(Collection<? extends E> c) {
modCount++;
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityHelper(elementCount + numNew);
// 将集合c的全部元素拷贝到数组elementData中
System.arraycopy(a, 0, elementData, elementCount, numNew);
elementCount += numNew;
return numNew != 0;
}
// 删除集合c的全部元素
public synchronized boolean removeAll(Collection<?> c) {
return super.removeAll(c);
}
// 删除“非集合c中的元素”
public synchronized boolean retainAll(Collection<?> c) {
return super.retainAll(c);
}
// 从index位置开始，将集合c添加到Vector中
public synchronized boolean addAll(int index, Collection<? extends E> c) {
modCount++;
if (index < 0 || index > elementCount)
throw new ArrayIndexOutOfBoundsException(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityHelper(elementCount + numNew);
int numMoved = elementCount - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
elementCount += numNew;
return numNew != 0;
}
// 返回两个对象是否相等
public synchronized boolean equals(Object o) {
return super.equals(o);
}
// 计算哈希值
public synchronized int hashCode() {
return super.hashCode();
}
// 调用父类的toString()
public synchronized String toString() {
return super.toString();
}
// 获取Vector中fromIndex(包括)到toIndex(不包括)的子集
public synchronized List<E> subList(int fromIndex, int toIndex) {
return Collections.synchronizedList(super.subList(fromIndex, toIndex), this);
}
// 删除Vector中fromIndex到toIndex的元素
protected synchronized void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = elementCount - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// Let gc do its work
int newElementCount = elementCount - (toIndex-fromIndex);
while (elementCount != newElementCount)
elementData[--elementCount] = null;
}
// java.io.Serializable的写入函数
private synchronized void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
s.defaultWriteObject();
}
}