List接口是继承于Collection接口，子接口是AbstractList，
Collection
/
List
/
AbstractList
/ |
Vector ArrayList AbstractSequenceList
|
Stack LinkedList
这里写到了
ArrayList
LinkedList
Vector
Stack
一、ArrayList：（JDK8）
ArrayList 是一个动态数组，非线程安全，允许元素为null。
其底层数据结构依然是数组，它实现了List<E>, RandomAccess, Cloneable, java.io.Serializable接口，其中RandomAccess代表了其拥有随机快速访问的能力，ArrayList可以以O(1)的时间复杂度去根据下标访问元素。
因其底层数据结构是数组，所以可想而知，它是占据一块连续的内存空间（容量就是数组的length），所以它也有数组的缺点，空间效率不高。
由于数组的内存连续，可以根据下标以O1的时间读写(改查)元素，因此时间效率很高。
1、构造函数：构建出数组elementData和数量size。
public ArrayList(int paramInt)
{
if (paramInt > 0) {
elementData = new Object[paramInt];
} else if (paramInt == 0) {
elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: " + paramInt);
}
}
public ArrayList()
{
elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(Collection<? extends E> paramCollection)
{
elementData = paramCollection.toArray();
if ((size = elementData.length) != 0)
{
if (elementData.getClass() != Object[].class) {
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
}
else {
elementData = EMPTY_ELEMENTDATA;
}
}
这里大家要注意一下Collection.toArray()这个方法，在Collection子类各大集合的源码中，高频使用了这个方法去获得某Collection的所有元素。
2、增加：每次 add之前，都会判断add后的容量，是否需要扩容。扩容默认扩容数组的一半，如果扩容一半不够，就用目标的size作为扩容后的容量；扩容成功后，会修改modCount。复制数组，然后设置对应下标元素值。
add()
3、删除：remove()
4、修改：set()
5、查找：get()
6、清空：clear()
7、包含：
public boolean contains(Object o)
public int indexOf(Object o)
8、判空：boolean isEmpty()
9、迭代器：Iterator
增删效率低，改查效率高
二、LinkedList：改查效率低，增删效率高
Collection.toArray();：不管是ArrayList、LinkedList 在批量add的时候，都会先转化成数组去做。 因为数组可以用for循环直接花式遍历。比较方便 高效。
非线程安全，允许元素为null，可重复。
其底层数据结构是链表，它实现List<E>, Deque<E>, Cloneable, java.io.Serializable接口，它实现了Deque<E>,所以它也可以作为一个双端队列。
双向链表。
节点：Node<E>
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;
}
}
1、增加单节点：add(E e) 或 add(int index, E e)
2、删除：E remove（int index)
3、改：set
4、查：get(int index)
5、查下标：int indexOf(Object o)
6、从尾到头找：int lastIndexOf(Object o)
7、转换成数组：new一个新数组，遍历链表，将每个元素存在数组里，返回
public Object[] toArray()
8、
三、Vector类：（基于jdk1.8）
矢量队列，jdk1.0添加的类，
继承于AbstractList，实现了List（所以是一个队列，支持相关的添加、修改、删除和遍历）实现了RandomAccess（提供了随机访问功能）、Cloneable接口（实现了clone()）
是线程安全的，相当于arrayList的线程安全版本。
1、相关数据结构
java.lang.Object
↳ java.util.AbstractCollection<E>
↳ java.util.AbstractList<E>
↳ java.util.Vector<E>
public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
protected Object[] elementData; //保存Vector中数据的数组
protected int elementCount; //实际数据的数量
protected int capacityIncrement; //容量增长系数
private static final long serialVersionUID = -2767605614048989439L; //vector的序列版本号
private static final int MAX_ARRAY_SIZE = 2147483639; //最大数组容量
}
2、构造函数：
//设置默认容量大小 和 每次容量增加时的增量值
public Vector(int paramInt1, int paramInt2)
{
if (paramInt1 < 0) {
throw new IllegalArgumentException("Illegal Capacity: " + paramInt1);
}
elementData = new Object[paramInt1];
capacityIncrement = paramInt2;
}
//默认构造函数，设置默认容量
public Vector(int paramInt)
{
this(paramInt, 0);
}
//默认构造函数，默认容量为10
public Vector()
{
this(10);
}
//创建一个包含collection的vector
public Vector(Collection<? extends E> paramCollection)
{
elementData = paramCollection.toArray();
elementCount = elementData.length;
if (elementData.getClass() != Object[].class) {
elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
}
}
3、是线程安全的，相当于ArrayList的线程安全版本，基本的增删方法都是synchronized同步的。
synchronized boolean add(E object)
void add(int location, E object)
synchronized boolean addAll(Collection<? extends E> collection)
synchronized boolean addAll(int location, Collection<? extends E> collection)
synchronized void addElement(E object)
synchronized int capacity()
void clear()
synchronized Object clone()
boolean contains(Object object)
synchronized boolean containsAll(Collection<?> collection)
synchronized void copyInto(Object[] elements)
synchronized E elementAt(int location)
Enumeration<E> elements()
synchronized void ensureCapacity(int minimumCapacity)
synchronized boolean equals(Object object)
synchronized E firstElement()
E get(int location)
synchronized int hashCode()
synchronized int indexOf(Object object, int location)
int indexOf(Object object)
synchronized void insertElementAt(E object, int location)
synchronized boolean isEmpty()
synchronized E lastElement()
synchronized int lastIndexOf(Object object, int location)
synchronized int lastIndexOf(Object object)
synchronized E remove(int location)
boolean remove(Object object)
synchronized boolean removeAll(Collection<?> collection)
synchronized void removeAllElements()
synchronized boolean removeElement(Object object)
synchronized void removeElementAt(int location)
synchronized boolean retainAll(Collection<?> collection)
synchronized E set(int location, E object)
synchronized void setElementAt(E object, int location)
synchronized void setSize(int length)
synchronized int size()
synchronized List<E> subList(int start, int end)
synchronized <T> T[] toArray(T[] contents)
synchronized Object[] toArray()
synchronized String toString()
synchronized void trimToSize()
网友评论