来源:互联网
List
-----------
1.ArrayList(jdk1.5以前版本中Vector)
2.LinkedList(jdk1.5以前版本中Stack)
3.CopyOnWriteArrayList
------------------------------
ArrayList是数组的实现形式(内部存储结构是一个数组):
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
private transient Object[] elementData;//存储元素的数组
//ArrayList的构造方法
public ArrayList(int initialCapacity) {//initialCapacity表示要创建的数组的容量
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
this.elementData = new Object[initialCapacity];//创建initialCapacity长度的数组
}
/**
*默认的构造 容量为10
*/
public ArrayList() {
this(10);
}
/**
* 通过传入集合变量的形式初始化创建list的数组
*/
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);
}
-----------------------------
//添加新的元素到数组末尾时,如果超过了当前容量,就要对数组进行扩容,扩充为原来大小的1.5倍,
//由于扩容牵涉到整个数组的copy,对性能影响较大,所以如果知道要存放容量的大小,尽量在创建ArrayList时指定
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
-----------------------------------
//get方法实现很简单,就是指定到数组的index下标处,效率很高
public E get(int index) {
RangeCheck(index);
return (E) elementData[index];
}
------
添加元素后扩容情况的效果图:
//添加元素的方法,注意先调用ensureCapacity,保证有足够的容量(如果不足就扩容,上面有该方法介绍)
//由于add方法添加元素时,可能导致扩容操作,这也影响了其效率
public boolean add(E e) {
ensureCapacity(size + 1);
elementData[size++] = e;
return true;
}
-----
删除元素的效果图:
//删除元素的remove操作,牵涉到删除位置index后边元素的copy,所以ArrayList的remove操作效率不高
public E remove(int index) {
RangeCheck(index);
modCount++;
E oldValue = (E) elementData[index];
int numMoved = size - index - 1;//删除位置后边的元素个数
if (numMoved > 0)//把要删除位置index后边的元素重新copy到数组的index处及以后
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null; // 把最后一个位置的元素置空,便于垃圾回收
return oldValue;
}
------------------
ensureCapacity
说明:ArrayList就是一个数组实现,适用于, 查找操作较多,而修改操作(add和delete)较少的情况,由于实现较为简单,就不再过多介绍,如果想更详细了解其实现,可以查看其源码。
下面要介绍的LinkedList适用于:查找较少,修改较多的情况(这与LinkedList的链式结构是有关系的)。
-------------------------------
LinkedList是链表结构的实现形式(内部存储结构是一个链表形式):
存储结构图示
LinkedList的类结构
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
LinkedList的成员变量
private transient Entry<E> header = new Entry<E>(null, null, null);//链表的头结点
private transient int size = 0;//链表中元素的个数
LinkedList的构造方法
/**
* 构造一个空链表
*/
public LinkedList() {
header.next = header.previous = header;
}
/**
* 通过传入一个集合初始化新链表
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
//addAll方法
public boolean addAll(int index, Collection<? extends E> c) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew==0)
return false;
modCount++;
Entry<E> successor = (index==size ? header : entry(index));//后继结点,如果index==size时,后继结点指向header头结点
Entry<E> predecessor = successor.previous;//前驱结点
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;//更新size大小
return true;
}
LinkedList的节点存储结构
private static class Entry<E> {//以内部类的形式定义Entry
E element;//元素值
Entry<E> next;//后继
Entry<E> previous;//前驱
Entry(E element, Entry<E> next, Entry<E> previous) {
this.element = element;
this.next = next;
this.previous = previous;
}
}
------------------------
LinkedList的get操作
//get操作,调用entry(index)方法,获得位置index位置的Entry对象
public E get(int index) {
return entry(index).element;
}
//通过index得到指定位置的Entry结点
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)) {//优化了查找操作,如果index<size/2就从头结点向后遍历
for (int i = 0; i <= index; i++)
e = e.next;
} else {//否则,向前遍历
for (int i = size; i > index; i--)
e = e.previous;
}
return e;
}
LinkedList的add操作
添加新元素到链表的末端,图示如下:
//add操作,把元素添加到链表的未段
public boolean add(E e) {
addBefore(e, header);
return true;
}
//把新元素e添加到entry的前面,当entry为header头结点时,相当于添加到链表的末端,如上图所示
private Entry<E> addBefore(E e, Entry<E> entry) {
Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);//以entry作为后继,以entry的前驱作为前驱
newEntry.previous.next = newEntry;//更新引用
newEntry.next.previous = newEntry;
size++;//元素个数 加1
modCount++;//修改次数 加1
return newEntry;
}
----------------------------
LinkedList的delete操作
删除元素E3,图示如下:
//remove操作,先调用entry(index)方法(上面有介绍)获得Entry对象,然后调用remove(entry)
public E remove(int index) {
return remove(entry(index));
}
//执行删除操作
private E remove(Entry<E> e) {
if (e == header)
throw new NoSuchElementException();
E result = e.element;
e.previous.next = e.next;//改变e前驱结点的next引用
e.next.previous = e.previous;//改变e后继结点的previous引用
e.next = e.previous = null;//把e置空,便于GC回收
e.element = null;
size--;//元素个数 减1
modCount++;//修改次数 加1
return result;
}
----------
另外,由于LinkedList实现了双向队列Deque接口,所以也具有队列的相关操作,可以当做一个队列使用。
http://hi.baidu.com/yao1111yao/item/3f358a5dd43f8314aaf6d791