算法與數(shù)據(jù)結(jié)構(gòu)（1），List
算法與數(shù)據(jù)結(jié)構(gòu)（2）温眉，Map
算法與數(shù)據(jù)結(jié)構(gòu)（3）缸匪，并發(fā)結(jié)構(gòu)
前一陣子，遇到一個(gè)問題类溢，大概的意思就是說凌蔬，不使用List集合，實(shí)現(xiàn)對(duì)象的增加和刪除闯冷，我之所要寫這篇博砂心，是因?yàn)槲椰F(xiàn)在仍然不能寫出滿意的結(jié)果，希望你能在看過之后蛇耀，有所靈感辩诞，然后實(shí)現(xiàn)它。
本篇蒂窒，依然從我的知識(shí)和思路出發(fā)躁倒，帶大家了解List數(shù)據(jù)結(jié)構(gòu)。
可以說三種List均來自AbstractList洒琢，而AbstractList又實(shí)現(xiàn)了List接口秧秉，并繼承了AbstractCollection。
ArrayList和Vector底層實(shí)現(xiàn)為數(shù)組衰抑，可以說這兩種List內(nèi)部封裝了數(shù)組的操作象迎，幾乎使用了同樣的算法，唯一的區(qū)別就是對(duì)多線程的支持呛踊。ArrayList沒有對(duì)任何一個(gè)方法做線程同步砾淌，因此不是線程安全的。Vector中絕大部分方法都做了線程同步谭网，是一種線程安全的實(shí)現(xiàn)汪厨。因此，ArrayList和Vector的性能特性相差無幾愉择，雖然從理論上來說劫乱，沒有實(shí)現(xiàn)線程同步的ArrayList要稍好于Vector，但是我依然查看了很多其他技術(shù)文章锥涕，得出的結(jié)論是衷戈，他倆在實(shí)際生產(chǎn)環(huán)境中的差異并不明顯，幾乎可以忽略不計(jì)层坠。
LinkedList使用了循環(huán)雙向列表數(shù)據(jù)結(jié)構(gòu)殖妇，由一系列表項(xiàng)連接而成。一個(gè)表項(xiàng)總是包括三個(gè)部分：元素內(nèi)容破花，前驅(qū)表項(xiàng)和后驅(qū)表項(xiàng)谦趣。（為了節(jié)省圖片寬度疲吸，嚴(yán)格意義上的前驅(qū)表項(xiàng)應(yīng)該指向前方，與后驅(qū)表項(xiàng)方向相反蔚润，在此不做修改磅氨。）
下圖展示了一個(gè)包含了三個(gè)元素的LinkedList，元素之間各個(gè)表項(xiàng)的連接關(guān)系嫡纠。無論LinkedList是否為空烦租，鏈表內(nèi)部都有一個(gè)header表項(xiàng)，它既表示鏈表的開始除盏，也表示鏈表的結(jié)尾叉橱。表項(xiàng)header，的后驅(qū)表項(xiàng)表示第一個(gè)元素者蠕，前驅(qū)表項(xiàng)表示鏈表中最后一個(gè)元素窃祝。
由于沒能拿到libcore的源碼，這里只能貼出JDK的實(shí)現(xiàn)踱侣，通過比較粪小，個(gè)人感覺還是JDK的實(shí)現(xiàn)更好一些。
增加元素到列表尾端
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1);//確保內(nèi)部數(shù)組有足夠的空間
elementData[size++] = e; //將元素添加到數(shù)組末尾
return true;
}
private void ensureCapacityInternal(int minCapacity) {
modCount++; //修改次數(shù)加一
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); //擴(kuò)容到原始容量的1.5倍
if (newCapacity - minCapacity < 0) //如果新容量小于最小需要的抡句，則使用最小需要容量
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0) //如果新容量大于最大數(shù)組容量探膊，計(jì)算出一個(gè)更龐大的新容量
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);//完成擴(kuò)容，并復(fù)制數(shù)組
}
當(dāng)ArrayList對(duì)容量的需求超過當(dāng)前數(shù)組大小時(shí)待榔，才需要擴(kuò)容逞壁，擴(kuò)容過程中，會(huì)進(jìn)行大量的數(shù)組復(fù)制操作锐锣，最終調(diào)用是本地方法System.arraycopy( )腌闯，雖然本地復(fù)制效率較高，速度較快雕憔，但是姿骏，如果ArrayList，內(nèi)部數(shù)組增長(zhǎng)過快斤彼，頻繁的進(jìn)行擴(kuò)容分瘦，add( )操作還是較慢的，但一般情況我們并不會(huì)瘋狂的向ArrayList中塞數(shù)據(jù)畅卓，因此擅腰，ArrayList.add( )蟋恬，效率還是不錯(cuò)的翁潘。
LinkedList構(gòu)造函數(shù)中初始化了一個(gè)header表項(xiàng)，前驅(qū)表項(xiàng)和后驅(qū)表項(xiàng)均是自己歼争，是一個(gè)只有一個(gè)元素的拜马，閉合的鏈表結(jié)構(gòu)渗勘。
LinkedList.add( )，將元素添加至鏈表末端俩莽。header元素的前驅(qū)表項(xiàng)正是List中最后一個(gè)元素旺坠，因此將新元素創(chuàng)建出來的同時(shí)增加到header之前，就相當(dāng)于在List最后插入元素扮超。
/**
* Constructs a new empty instance of {@code LinkedList}.
*/
public LinkedList() {
voidLink = new Link<E>(null, null, null);
voidLink.previous = voidLink;
voidLink.next = voidLink;
}
@Override
public boolean add(E object) {
return addLastImpl(object);
}
private boolean addLastImpl(E object) {
Link<E> oldLast = voidLink.previous;
Link<E> newLink = new Link<E>(object, oldLast, voidLink);
voidLink.previous = newLink;
oldLast.next = newLink;
size++;
modCount++;
return true;
}
雖然取刃，LinkedList使用了鏈表結(jié)構(gòu)，不需要考慮容量的大小出刷，從這一點(diǎn)上說效率是高于ArrayList璧疗，然而每次元素的增加都需要新建一個(gè)Link對(duì)象，并進(jìn)行賦值操作馁龟，如果頻繁使用崩侠，依然會(huì)消耗資源，對(duì)效率產(chǎn)生一定影響坷檩，在JDK中（SDK中由于沒能拿到libcore源碼却音，初始容量未知）ArrayList的初始容量是10，所以絕大情況下的追加操作矢炼，ArrayList不需要頻繁擴(kuò)容系瓢，效率還是蠻高的。
增加元素到列表任意位置
由于實(shí)現(xiàn)不同裸删，ArrayList和LinkedList在這個(gè)方法上存在很大差異八拱，由于ArrayList是基于數(shù)組實(shí)現(xiàn)的，而所謂的數(shù)組就是一塊連續(xù)的內(nèi)存空間涯塔，如果在數(shù)組的任意位置插入元素肌稻，必然導(dǎo)致在該位置后的所有元素都要重新排列，因此匕荸，效率會(huì)相對(duì)較低爹谭。
/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}
/**
* A version of rangeCheck used by add and addAll.
*/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
可以看到每次插入操作，都會(huì)進(jìn)行一次數(shù)組復(fù)制榛搔。而這個(gè)操作在增加元素到List尾端的時(shí)候是不存在的诺凡。大量的數(shù)組操作會(huì)導(dǎo)致系統(tǒng)性能低下。并且践惑，插入的元素在List中的位置越靠前腹泌，數(shù)組充足的開銷也越大。所以尔觉，使用ArrayList應(yīng)盡可能的將元素插入List尾端附近凉袱，有助于提高該方法的性能。
LinkedList的插入在此時(shí)便顯出優(yōu)勢(shì)，首先判斷插入元素位置专甩，如果處于整個(gè)List前半段钟鸵，則從前向后遍歷，若其位置處于后半段涤躲，則從后向前遍歷棺耍，找到插入位置的元素Link，進(jìn)行鏈表的重新連接种樱。
/**
* Inserts the specified object into this {@code LinkedList} at the
* specified location. The object is inserted before any previous element at
* the specified location. If the location is equal to the size of this
* {@code LinkedList}, the object is added at the end.
*
* @param location the index at which to insert.
* @param object the object to add.
* @throws IndexOutOfBoundsException if {@code location < 0 || location > size()}
*/
@Override
public void add(int location, E object) {
if (location >= 0 && location <= size) {
Link<E> link = voidLink;
if (location < (size / 2)) {
for (int i = 0; i <= location; i++) {
link = link.next;
}
} else {
for (int i = size; i > location; i--) {
link = link.previous;
}
}
Link<E> previous = link.previous;
Link<E> newLink = new Link<E>(object, previous, link);
previous.next = newLink;
link.previous = newLink;
size++;
modCount++;
} else {
throw new IndexOutOfBoundsException();
}
}
可見對(duì)LinkedList來說蒙袍，在List尾端插入數(shù)據(jù)和在任意位置插入數(shù)據(jù)是一樣的。并不會(huì)因?yàn)椴迦霐?shù)據(jù)的位置靠前而導(dǎo)致性能的降低嫩挤。所以左敌，如果在實(shí)際生成環(huán)境中，需要頻繁的在任意位置插入元素俐镐，可以考慮用LinkedList代替ArrayList矫限。
刪除任意位置元素
對(duì)ArrayList來說，remove( )和add( )方法是類似的佩抹，在任意位置移除元素之后叼风，都要進(jìn)行數(shù)組的復(fù)制和重組。
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices).
*
* @param index the index of the element to be removed
* @return the element that was removed from the list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
//將刪除元素所在位置棍苹，后面的所有元素往前移動(dòng)一位
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
//最后一個(gè)位置元素置null
elementData[--size] = null; // Let gc do its work
return oldValue;
}
由源碼可以看到无宿，在ArrayList的每一次有效的元素刪除操作之后，都要進(jìn)行數(shù)組的復(fù)制和重組枢里，并將List隊(duì)列尾端的元素置null孽鸡，如果刪除的元素越靠前，數(shù)組重組時(shí)的開銷就越大栏豺，位置越靠后彬碱，開銷越小。
LinkedList中的remove( )和添加任意位置元素是類似的奥洼，首先通過循環(huán)找到要?jiǎng)h除的元素巷疼，如果要?jiǎng)h除的元素處于List位置前半段，則從前往后找灵奖；若其位置處于后半段嚼沿，則從后往前找。因此無論要?jiǎng)h除較為靠前或者靠后的元素都是非常高效的：但要移除List中間的元素幾乎要遍歷完半個(gè)List瓷患，在List擁有大量元素的情況下骡尽，效率很低。
/**
* Removes the object at the specified location from this {@code LinkedList}.
*
* @param location the index of the object to remove
* @return the removed object
* @throws IndexOutOfBoundsException if {@code location < 0 || location >= size()}
*/
@Override
public E remove(int location) {
if (location >= 0 && location < size) {
Link<E> link = voidLink;
if (location < (size / 2)) {
for (int i = 0; i <= location; i++) {
link = link.next;
}
} else {
for (int i = size; i > location; i--) {
link = link.previous;
}
}
Link<E> previous = link.previous;
Link<E> next = link.next;
previous.next = next;
next.previous = previous;
size--;
modCount++;
return link.data;
}
throw new IndexOutOfBoundsException();
}
List遍歷
List集合擅编，三種遍歷方式攀细。
List<String> list = null;
String temp;
/*迭代器循環(huán)*/
for (Iterator iterator = list.iterator(); iterator.hasNext(); ) {
temo= (String) iterator.next();
}
/*ForEach*/
for (String string : list) {
temp = string;
}
/*for循環(huán)，隨機(jī)訪問*/
for (int i = 0; i < list.size(); i++) {
temp = list.get(i);
}
迭代器：ArrayList和LinkedList在迭代器模式中都表現(xiàn)出良好的性能。
ForEach：ArrayList和LinkedList在該遍歷模式中效率不及迭代器辨图，通過度娘，找到了ForEach反編譯后的樣子肢藐，性能降低原因是故河，多余的一步字符串賦值操作。
/*ForEach反編譯解析*/
for (Iterator iterator = list.iterator(); iterator.hasNext(); ) {
String s = (String) iterator.next();
String s1 = s; //多余的操作
}
fot循環(huán)：基于數(shù)組的List都實(shí)現(xiàn)了RandomAccess接口吆豹，如ArrayList和Vector鱼的，沒有實(shí)現(xiàn)的以LinkedList為代表。實(shí)現(xiàn)RandomAccess接口的List痘煤，當(dāng)元素?cái)?shù)量較多時(shí)凑阶，通過直接的隨機(jī)訪問比通過迭代的方式，可提升大約10%的性能（謝謝度娘）衷快。如果LinkedList采用隨機(jī)訪問宙橱，總是要進(jìn)行一次遍歷查找，雖然通過雙向循環(huán)鏈表的特性蘸拔，將平均查找的次數(shù)減半师郑，但是其遍歷過程依然會(huì)消耗大量cpu資源。
片尾Tip：通過RandomAccess可知道List是否支持快速隨機(jī)訪問调窍。同時(shí)宝冕，需要記住，如果程序需要使用通過下標(biāo)對(duì)List進(jìn)行隨機(jī)訪問邓萨，盡量不要使用LinkedList地梨，ArrayList和Vector都是不錯(cuò)的選擇。
