List:
一种线性的数据结构，在Java中，List是一个接口，在接口中定义了相关的操作，它的父类是Collection接口，它的子类有：quentialList ， ArrayList ， AttributeList ， CopyOnWriteArrayList ， LinkedList ， RoleList ， RoleUnresolvedList ， Stack ， Vector.
常用的List的子类有：ArrayList,LinkList,CopyOnWriteArrayList,Stack,Vector。
ArrayList:
一种低层以数组的方式存储数据的数据结构 。对于数组的优点是可以在常数级别实现对数据元素的访问，而对于数据的插入，删除，则需要将数组中的元素进行移动。
ArrayList中包含的重要常量有：（以下常量和方法都是来自JDK1.8中源代码中）
serialVersionUID 序列号，用于传输；
DEFAULT_CAPACITY：默认数组大小10；
Object[] EMPTY_ELEMENTDATA：数组对象，用于存储数据的数组；
Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA：默认空的数组对象。
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
} 即：使用特定参数的构造函数时，会创建一个数组，数组的大小为传入的指定参数的大小。如果为0，则空的数组，其他值则抛出异常。
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
} 即创建一个容量为10的list。
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;
} ArrayList中可以存储null对象，对于源代码中的indexOf,lastIndexOf，remove方法，需要做的是，先判断要传入的参数是否为null,如果为null,则对数组进行遍历，找出值为null的对象，如果不是空，则对数组进行遍历，使用equal方法进行判断，这里的o为Object对象，没有重写equal方法，所以equal方法还是Object类中的equal方法，使用对象的地址来判断是否属于同一个对象，而任何类都继承了Object类，对于不同的类，有的重写了equals方法，例如Integer类，因此对于不同的存储类，equals方法实现的方式不一样。为什么不直接使用equal方法，因为如果对象为null，null对象不存在equals方法，所以会抛出空指针异常错误。
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
} ArrayList向外部提供一个public类型的add方法，add方法的内部则调用私有化的add方法来进行add操作，这种手段有效的隐藏了真实的调用方法，私有化add方法：
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
} 首先判断数组的存放位置是否已经满了，如果没有，则将数据放在指定的位置，如果满了，则使用grow（)进行扩充；
private Object[] grow() {
return grow(size + 1);
}
private Object[] grow(int minCapacity) {
return elementData = Arrays.copyOf(elementData,
newCapacity(minCapacity));
}
private int newCapacity(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity <= 0) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
}
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
} 扩充是先将数组的大小加1，将其值传入minCapacity变量中，将其于Object数组的大小进行比较，如果大于Object数组值，则产生一个新的数组的容量值，值为当前数组值*1.5+1，如果值还是小于minCapacity，则将minCapacity作为新的容量值，然后使用Arrays.copyOf生成新的数组对象。
Arrays.copys方法会创建一个数组对象，然后将之前数组中的对象，复制到新的数组中。
注意：ArrayList不是线程安全的。
remove:
public boolean remove(Object o) {
final Object[] es = elementData;
final int size = this.size;
int i = 0;
found: {
if (o == null) {
for (; i < size; i++)
if (es[i] == null)
break found;
} else {
for (; i < size; i++)
if (o.equals(es[i]))
break found;
}
return false;
}
fastRemove(es, i);
return true;
} 即先判断对象是否为null,为null，则遍历数组找到null，调用fastRemove来删除null对象，不为null,在使用equals()比较找到位置，然后调用fastRemove()方法来进行删除，fastRemove将index后的对象向前复制一位，并将数组中的最后一个元素设置为null.
LinkedList:
是一种低层采用链表的方式实现，链表为双向链表，即每个节点既有它的后继节点，又有它的前驱节点。
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
} Node类为链表每个节点的框架。
LinkedList中的重要常量为：
Node<E> first: 第一个节点；
Node<E> last:最后一个节点；
int size : 节点的数量；
public LinkedList() {
} 创建一个空的链表；
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
} LinkedList的add方法会调用linkLast方法，linkLast会将根据新的值创建一个新的Node对象，然后判断last节点是否为null，如果为null，则说明链表为null,则将节点赋值给first节点，如果不为空，则将节点添加到last节点的后面。
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
remove方法同理，也是先判断对象是否为null,根据对象的值，进行不同操作的删除，和ArrayList同理。只不过删除的方法不一样，LinkList使用unlink(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;
} 从中我们可以看出，first是链表的第一个节点，如果prev等于null，即表示当前节点为第一个节点，则将first指向next节点，即可删除x节点，如果prev不为null，则将prev.next指向x.next即可，next如果为空，则表示节点为最后一个元素，则将prev设置为last，即可删除，否则，将next.prev指向prev即可。
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
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;
}
} get方法会先检查下标是否在合理的范围内，如果在，将调用node(index)方法，然后node(index)将当前的index与链表的长度的一半进行比较，如果小于，则从前往后查找，如果大于，则从后往前查找。
Vector：
Vector和ArrayList一样，唯一的区别是Vector是线程安全的，他会在add,remove,get方法上使用synchronized关键字，来保证并发操作下的同步问题。
Stack:
栈是一种先进后出的数据结构，栈的实现可以数组，也可以使用链表，Java中的栈继承Vector类，Vector则低层则使用数组进行存储，所以栈使用数组进行存储。
栈的主要方法有：push,pop,peek,search,这些方法都是同步的，有关键字synchronized修饰，所以stack是线程安全的。
CopyOnWriteArrayList
CopyOnWriterArrayList是一个线程安全的，读操作无锁的ArrayList；
public CopyOnWriteArrayList() {
setArray(new Object[0]);
}
final void setArray(Object[] a) {
array = a;
} CopyOnWriteArrayList()构造器是一个创建一个大小为0的数组；
public boolean add(E e) {
synchronized (lock) {
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
}
}
add方法是同步的，使用synchronized关键字，其添加方法和ArrayList方法一致。
public boolean remove(Object o) {
Object[] snapshot = getArray();
int index = indexOf(o, snapshot, 0, snapshot.length);
return (index < 0) ? false : remove(o, snapshot, index);
}
private boolean remove(Object o, Object[] snapshot, int index) {
synchronized (lock) {
Object[] current = getArray();
int len = current.length;
if (snapshot != current) findIndex: {
int prefix = Math.min(index, len);
......
return true;
}
} remove方法也是同步的，但是与ArrayList删除元素的方式不一致，即它会创建一个数组大小为当前组数-1大小的数组，然后遍历数组，寻找待删除的元素，然后将之后的元素全部赋值给新的数组对象，并做引用切换，如果没有找到，则将当前的元素赋值给新的数组对象，最后处理最后一个元素，如果最后一个元素是要删除的对象，则将当前数组赋值为新的数组对象，如果不等于，则返回false;
get(int)方法是没有synchronized关键字修饰，即没有使用锁，所以有可能会读取到脏数据，但是效率高。
如有异议，敬请指出，谢谢，与君共勉。
京公网安备 11010502036488号