1、LinkedList底層實作原理
LinkedList底層的資料結構是基于雙向循環連結清單的，且頭結點中不存放資料,如下：
從圖中可以看出，有頭節點和資料節點，頭節點是結構必須的，資料節點即是存放資料的節點。
每一個節點都有三個元素，一個是目前節點的資料，也就是data部分，data左邊就是指向該節點的上一個節點的指針，右邊就是指向該節點的下一個節點的指針。
既然是雙向連結清單，那麼必定存在一種資料結構——我們可以稱之為節點，節點執行個體儲存業務資料，前一個節點的位置資訊和後一個節點位置資訊，如下圖所示：
(1)、數組與連結清單的結構比較
數組是将元素在記憶體中連續存放，由于每個元素占用記憶體相同，可以通過下标迅速通路數組中任何元素。但是如果要在數組中增加一個元素，需要移動大量元素，在記憶體中空出一個元素的空間，然後将要增加的元素放在其中。同樣的道理，如果想删除一個元素，同樣需要移動大量元素去填掉被移動的元素。如果應用需要快速通路資料，很少插入和删除元素，就應該用數組。
連結清單中的元素在記憶體中不是順序存儲的，而是通過存在元素中的指針聯系到一起，每個結點包括兩個部分：一個是存儲資料元素的資料域，另一個是存儲下一個結點位址的指針。
如果要通路連結清單中一個元素，需要從第一個元素開始，一直找到需要的元素位置。但是增加和删除一個元素對于連結清單資料結構就非常簡單了，隻要修改元素中的指針就可以了。如果應用需要經常插入和删除元素你就需要用連結清單。
a)、記憶體存儲差別
數組從棧中配置設定空間, 對于程式員友善快速,但自由度小。
連結清單從堆中配置設定空間, 自由度大但申請管理比較麻煩.
b)、邏輯結構差別
數組必須事先定義固定的長度（元素個數），不能适應資料動态地增減的情況。當資料增加時，可能超出原先定義的元素個數；當資料減少時，造成記憶體浪費。
連結清單動态地進行存儲配置設定，可以适應資料動态地增減的情況，且可以友善地插入、删除資料項。（數組中插入、删除資料項時，需要移動其它資料項）
c)總的來說
1、存取方式上，數組可以順序存取或者随機存取，而連結清單隻能順序存取；
2、存儲位置上，數組邏輯上相鄰的元素在實體存儲位置上也相鄰，而連結清單不一定；
3、存儲空間上，連結清單由于帶有指針域，存儲密度不如數組大；
4、按序号查找時，數組可以随機通路，時間複雜度為O(1)，而連結清單不支援随機通路，平均需要O(n)；
5、按值查找時，若數組無序，數組和連結清單時間複雜度均為O(1)，但是當數組有序時，可以采用折半查找将時間複雜度降為O(logn)；
6、插入和删除時，數組平均需要移動n/2個元素，而連結清單隻需修改指針即可；
7、空間配置設定方面：
數組在靜态存儲配置設定情形下，存儲元素數量受限制，動态存儲配置設定情形下，雖然存儲空間可以擴充，但需要移動大量元素，導緻操作效率降低，而且如果記憶體中沒有更大塊連續存儲空間将導緻配置設定失敗；
連結清單存儲的節點空間隻在需要的時候申請配置設定，隻要記憶體中有空間就可以配置設定，操作比較靈活高效；
2、自定義LinkedList
ExtList接口跟 上一篇的一樣 Java基礎(二)集合之ArrayList(集合第二篇)
ExtLinkedList實作類，完全根據源碼的業務邏輯實作，并添加注釋+自己的了解
public class ExtLinkedList<E> implements ExtList<E>{
/**
* 連結清單的大小
*/
transient int size = 0;
/**
* 指向第一個節點的指針。
*/
transient Node first;
/**
* 指向最後一個節點的指針。
*/
transient Node<E> last;
@Override
public void add(E e) {
//預設在清單的尾部添加元素
linkLast(e);
}
//在指定下标位置添加元素
@Override
public void add(int index, E e) {
//檢查索引下标是否越界
checkPositionIndex(index);
if (index == size)
//如果索引的位置是在連結清單的最後，直接調用在尾部添加元素
linkLast(e);
else
//否則，在下标之後插入元素
linkBefore(e, node(index));
}
/**
* 在下标位置插入元素
* @param e 元素
* @param succ 要插入索引位置的節點
*/
void linkBefore(E e, Node<E> succ) {
//擷取原索引位置的節點的上一個節點
final Node<E> pred = succ.prev;
//1、建立一個節點，該節點的左節點指向原索引位置節點的上一個節點,
// 右節點指向原索引位置節點，元素為傳入的元素
final Node<E> newNode = new Node<>(pred, e, succ);
//2、将原索引位置節點的左節點指定為新添加的節點
succ.prev = newNode;
if (pred == null)
//3、如果索引位置節點的上一個節點為空，則是空連結清單，将新添加的節點設定為第一個節點
first = newNode;
else
//4、如果索引位置節點的上一個節點不為空，則将其右節點設定為新添加的節點
pred.next = newNode;
//5、連結清單數量加1
size++;
}
//在清單末尾添加元素
private void linkLast(E e) {
//擷取最後一個節點
final Node<E> l = last;
//1、建立一個節點，将該節點的左節點指向原來的最後一個節點，
// 右節點指向null(最後一個節點都是指向null)，元素為傳入元素
final Node<E> newNode = new Node<>(l, e, null);
//2、将目前的連結清單的最後一個節點設定為新添加的節點
last = newNode;
if (l == null)
//3、如果最後一個節點為空，則是空連結清單，将新添加的節點設定為第一個節點
first = newNode;
else
//4、如果最後一個節點不為空，将原來最後一個節點的右節點指針指向新添加的節點
l.next = newNode;
//5、連結清單數量加1
size++;
}
@Override
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
//根據傳入對象删除節點
@Override
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;
}
@Override
public int getSize() {
return size;
}
@Override
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
/**
* 自定義Node節點
* @param <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;
}
}
/**
* 傳回指定元素索引處的（非null）節點。
*/
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;
}
}
/**
* 取消連結清單非空節點x。
*/
E unlink(Node<E> x) {
final E element = x.item;//目前節點元素
final Node<E> prev = x.prev;//左節點
final Node<E> next = x.next;//右節點
if (prev == null) {
//1、如果上一個節點為空，則是删除第一個節點，将将連結清單的頭部設定原來第二個節點即可
first = next;
} else {
//2、如果上一個節點不為空，則将要要删除節點的上一個節點的右節點指向要删除節點的下一個節點
prev.next = next;
//删除目前節點的左指針(将目前節點的左節點設定為空)
x.prev = null;
}
if (next == null) {
//3、如果下一個節點為空，則要删除的節點是最後一個節點，将将連結清單的尾部設定原來倒數第二個節點即可
last = prev;
} else {
//4、如果下一個節點不為空，則要将要删除節點的下一個節點的左節點指向要删除節點的上一個節點
next.prev = prev;
//删除目前節點的右指針(将目前節點的右節點設定為空)
x.next = null;
}
//5、删除目前節點元素
x.item = null;
//6、連結清單數量減一
size--;
//7、傳回删除的元素
return element;
}
//檢查索引下标是否越界
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//檢查元素索引是否越界
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* 判斷參數是否是現有元素的索引。
*/
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
/**
* 判斷參數是否是疊代器或添加操作的有效位置的索引。
*/
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
/**
* 抛出數組下标越界異常資訊
*/
private String outOfBoundsMsg(int index) {
return "索引位置: "+index+", 數組大小: "+size;
}
}
測試代碼：
//測試ArrayList的删除元素速度
@Test
public void testExtArrayList1(){
ExtList<User> list = new ExtArrayList<>();
for (int i = 0; i < 10000000; i++) {
list.add(new User((long)i,"張三"+i));
}
System.out.println("删除元素開始時間："+System.currentTimeMillis());
list.remove(0);
System.out.println("删除元素結束時間："+System.currentTimeMillis());
}
//測試LinkedList的删除元素速度
@Test
public void testExtLInkedList(){
ExtList<User> list = new ExtLinkedList<>();
for (int i = 0; i < 10000000; i++) {
list.add(new User((long)i,"張三"+i));
}
System.out.println("删除元素開始時間："+System.currentTimeMillis());
list.remove(0);
System.out.println("删除元素結束時間："+System.currentTimeMillis());
}
可以得出結果：
LinkedList的删除速度比ArrayList快一些。
學習Java基礎知識，做一個簡單的記錄。
上一篇：Java基礎(二)集合之ArrayList(集合第二篇)
下一篇：暫無