List为有序的Collection（集合），它按对象进入的顺序保存对象，所以它能对列表中的每个元素的插入和删除为进行精确控制，同时可以保存重复对象。LinkedList、ArrayList、Vector都实现了List接口。
List接口继承Collection接口，而Collection继承Iterable接口，即List->Collection->Iterable，接口也可以继承，也是用关键字extends。
LinkedList（它没有实现RandomAccess接口）、ArrayList、Vector除了实现了List接口还实现了RandomAccess, Cloneable, java.io.Serializable三个接口，
- RandomAccess接口：仅仅是一个标识，实现该接口代表着List（列表）是随机存取的。此接口的主要目的是允许通用算法更改其行为，以便在应用于随机访问列表或顺序访问列表时提供良好的性能。例如需要大量进行随机访问列表中的值时，如果使用顺序访问的列表时，效率将大大降低，如果用
instanceof提前进行对该列表进行判断是否该列表时随机储存的，便可以保证算法的高效性。 - Cloneable接口：该接口也是一个标识，接口内没有方法，实现该接口表示该对象是可以使用Object对象中clone方法进行复制一个对象(覆盖了父类Object中的clone方法)。
- Serializable接口：该接口也是一个标识，接口内没有方法，实现该接口表示该对象是可序列化的。没有实现此接口的类将不能使它们的任一状态被序列化或逆序列化。
LinkedList
LinkedList继承AbstractSequentialList类，而且除了实现了开始说的几个接口，还实现了Deque接口。（总共这些接口List
LinkedList列表是顺序存储的，是双向链表，它内部有个静态类Node，除了有个next指针还有一个prev指针。p.s，静态内部类是指不依赖于外部类进行实例化的一种内部类，非静态的内部类依赖于内部类进行实例化，而且不能访问外部类中非静态的成员和方法。
LinkedList里几个实例都是transient的，transient的含义见文章末尾，大概意思就是指序列化的时候不进行序列化。
transient int size = 0;
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
方法
1.linkLast()和unlinkFirst()方法私有的，而unlink()方法是default的
/**
* Unlinks non-null last node l.
*/
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
/**
* Unlinks non-null first node f.
*/
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC，断开，帮助GC回收垃圾
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
/**
* Unlinks non-null node x.
*/
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
2.add()和addAll()方法
//在index位置插入链表的位置，
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
//node方法查找index所在的节点
succ = node(index);
pred = succ.prev;
}
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
Node<E> node(int index) {
// assert isElementIndex(index);
//是从前往后还是从后往前找
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
3.Queue操作peek() poll() push() element() remove() pop()
//如果没有，则返回null
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
public E element() {
return getFirst();
}
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
//如果没有，则返回null
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
//没有节点可移除，则抛异常
public E remove() {
return removeFirst();
}
ArrayList
ArrayList和Vector类基本上类似，ArrayList是线程不安全的，Vector是线程安全的，ArrayList的动态存储是默认是1.5倍增加的。
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
Vector
Vector和ArrayList一样都是基于储存元素的Object[] array来实现的，它们会在内存中开辟一段连续的存储空间来存储，由于是连续存储的，支持用序号来访问元素，同时索引数据的速度比较快。但插入、删除元素需要移动大量元素，所以对数据插入、删除执行比较慢。同ArrayList一样，Vector也有一个初始容量的大小，每当元素超过初始容量时，需要动态地扩长它们存储空间。
Vector线程安全的，大部分方法都使用synchromized进行线程同步。
实现的接口有：List
Vector动态增加存储容量默认为两倍。动态的增加容量过程是传入需要的存储容量值，判断默认容量的两倍是否满足传入的存储容量值，不满足的话，那么设置当前的新容量为传入存储容量值。Vector类里有个实例变量modCount用来记录当前Vector列表结构上被修改几次（结构上修改是指列表大小的改变，不是指存储容量的改变）。否则会扰乱它，使得正在进行的迭代可能产生不正确的结果（感觉用来记录当前list是不是之前的那个list）。每次对列表进行添加、删除元素modCount值都会改变。
注意：modCount是父类AbstractList类的实例变量。Vector继承AbstractList
方法
1.扩容的时候复制值调用的方法是Arrays.copyOf(elementData, newCapacity)
2.Vector类中的indexOf()方法和lastIndexOf()方法
从index开始找，返回元素下标值，首先判断是否为null，然后根据equals来判断是否相等。
public int indexOf(Object o) {
return indexOf(o, 0);
}
public synchronized int indexOf(Object o, int index) {
if (o == null) {
for (int i = index ; i < elementCount ; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = index ; i < elementCount ; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
public synchronized int lastIndexOf(Object o, int index) {
if (index >= elementCount)
throw new IndexOutOfBoundsException(index + " >= "+ elementCount);
if (o == null) {
for (int i = index; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = index; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
3.removeElementAt()方法和insertElementAt()添加元素方法
需要注意的是,按照数组下标删除值，需要将删除元素后面元素向前移，移动方法调用System.arraycopy()方法，删除元素后需要将指针指向空，然后让gc进行回收释放对象垃圾。
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 */
}
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++;
}
4.clone()方法
返回一个引用指向一个新的对象。
public synchronized Object clone() {
try {
@SuppressWarnings("unchecked")
Vector<E> v = (Vector<E>) super.clone();
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(e);
}
}
5.迭代器
迭代器调用next()方法时，首先会通过checkForComodification()方法来检查expectedModCount的值和对象中modCount的值是否相等，不相等的话说明迭代器在迭代过程中对容器进行添加或者删除元素了（具体见如下代码）。
public synchronized Iterator<E> iterator() {
return new Itr();
}
/**
* An optimized version of AbstractList.Itr
*/
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
// 保存当前modCount值
int expectedModCount = modCount;
public boolean hasNext() {
// Racy but within spec, since modifications are checked
// within or after synchronization in next/previous
return cursor != elementCount;
}
public E next() {
synchronized (Vector.this) {
checkForComodification();
int i = cursor;
if (i >= elementCount)
throw new NoSuchElementException();
cursor = i + 1;
return elementData(lastRet = i);
}
}
public void remove() {
if (lastRet == -1)
throw new IllegalStateException();
synchronized (Vector.this) {
checkForComodification();
Vector.this.remove(lastRet);
expectedModCount = modCount;
}
cursor = lastRet;
lastRet = -1;
}
@Override
public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
synchronized (Vector.this) {
final int size = elementCount;
int i = cursor;
if (i >= size) {
return;
}
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) Vector.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
action.accept(elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
子类
Vector类一个重要子类就是Stack，所以java.util.Stack类的栈是基于连续存储的Vector 实现的。除了pop(),peek(),push(),empty()方法外，还有继承Vector类的add(),addAll(),indexOf()等方法。
transient关键字
我们都知道一个对象只要实现了Serilizable接口，这个对象就可以被序列化，Java的这种序列化模式为开发者提供了很多便利，我们可以不必关系具体序列化的过程，只要这个类实现了Serilizable接口，这个的所有属性和方法都会自动序列化。
然而在实际开发过程中，我们常常会遇到这样的问题，这个类的有些属性需要序列化，而其他属性不需要被序列化，诚然，你可以让这个类来实现Externalizable接口，这个接口是Serilizable的子接口，但是你必须实现readExternal和writeExternal方法，你可以在这两个方法中实现具体属性的反序列化和序列化操作。然而这就意味着你必须在这两个方法中手工编写额外的代码来进行具体属性的序列化。java的transient关键字为我们提供了便利，你只需要实现Serilizable接口，将不需要序列化的属性前添加关键字transient，序列化对象的时候，这个属性就不会序列化到指定的目的地中。
package wwj.com.test;
import java.io.*;
/**
* Created by Jerry on 2017/4/3.
*/
public class TestTransient {
public static void main(String[] args) throws IOException, ClassNotFoundException {
A a = new A(25,"张三");
//输出 A{a=25, b='张三'}
System.out.println(a);
ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream("d://mm.txt"));
oos.writeObject(a);
oos.close();
ObjectInputStream ois = new ObjectInputStream(new FileInputStream("d://mm.txt"));
a = (A)ois.readObject();
//输出 A{a=25, b='null'}，b的值已经为null
System.out.println(a);
}
}
class A implements Serializable{
int a;
transient String b;
public A(int a, String b){
this.a = a;
this.b = b;
}
@Override
public String toString() {
return "A{" +
"a=" + a +
", b='" + b + '\'' +
'}';
}
}
