Java LinkedList同時實作了List與Deque介面。為雙鏈接串列(Double-linked List)，串列中的每個節點都有指向前一個及下一個節點的指標。
Double-linked List的圖示
LinkedList不是線性儲存，也就是儲存在記憶體中的位置是不連貫的，而是在每個元素節點額外儲存上一個及下一個節點的指標，雖然在建立時不用給定初始容量，不過也因為多儲存了指標資訊，所以所占用的記憶體較多。
LinkedList允許元素重複且為null。
LinkedList是非同步化的(unsynchronized)，也就是非執行緒安全的(non thread safe)，可使用Collections.synchronizedList(List<T> list)來取得同步化的物件，不過同步化後若轉成Iterator時仍不保證執行緒安全，因此要在同步區塊內執行走訪。
List<String> list = new LinkedList<String>();
Collections.synchronizedList(list); // 同步化
Iterator<String> i = list.iterator(); // 轉成Iterator不保證執行緒安全，因此走訪時要在同步化區塊進行
Thread a = new Thread(() ->{
synchronized(i){
while(i.hasNext()){
// ...
}
}
});
下面是LinkedList的簡單實作，僅有單向連結，List中的元素用一個節點Node來包裝，每個Node皆會指到下一個節點（即有下個節點的reference）。
SimpleLinkedList
public class SimpleLinkedList<T> {
private class Node {
T t;
Node next; // 指到下一個節點
Node(T t) {
this.t = t;
}
}
private Node first; // 第一個節點
public void add(T element) {
Node node = new Node(element);
if (first == null) {
first = node;
} else {
append(node);
}
}
private void append(Node node) {
Node last = first;
while (last.next != null) { // 取得最後一個節點
last = last.next;
}
last.next = node;
}
public void add(int index, T element) {
try {
checkSize(index - 1); // 允許插入位置在最後一個節點之後的後一個位置。
} catch(IndexOutOfBoundsException e){
index = size();
}
Node node = new Node(element); // 新節點
node.next = findNode(index); // 將原節點接到新節點後
if (index > 0) {
findNode(index - 1).next = node; // 把新節點接在前一個節點後
} else {
first = node;
}
}
public T get(int index) {
checkSize(index);
return findElemOf(index);
}
private void checkSize(int index) throws IndexOutOfBoundsException {
int size = size();
if (index >= size()) {
throw new IndexOutOfBoundsException(String.format("Index: %d, Size: %d", index, size));
}
}
private T findElemOf(int index) {
return findNode(index).t;
}
private Node findNode(int index) {
int count = 0;
Node last = first;
while (count < index) {
last = last.next;
count++;
}
return last;
}
public int size() {
int count = 0;
Node last = first;
while (last != null) {
last = last.next;
count++;
}
return count;
}
}
LinkedList與ArrayList的比較
ArrayList常拿來和LinkedList比較，以下是兩者差異：
ArrayList的實作是陣列(Array)，資料以連續的方式儲存在記憶體，可支援隨機存取及循序存取，所以循序讀取或排序(sort)時的效能好。每個節點不用另外儲存下一個節點的指標，每個節點所占用的記憶體較少，但也因為是線性儲存，所以在串列中插入或刪除節點時的效能差，因為必須移動大量節點的索引。而新增的元素超過原本的長度時要配置新的陣列並將舊陣列複製過去，此時占用的記憶體也會比較大。LinkedList的實作是雙鏈接串列(Double-linked List)，資料以不連續的方式儲存，因此不需使用連續的記憶體空間，也不需事先指定串列大小。每個節點都會記錄著下個節點的指標，所以在串列中插入或刪除節點時只需修改相關節點的指標，插入或刪除的效能較好。因非線性儲存，讀取時無法快速索引到該節點，只能以循序存取讀取每一個節點的指標，一個一個節點往下找，所以讀取的效能較差。又每個節點額外記錄著下個節點的指標，占記憶體比較大。每個節點是透過指標來連結彼此，所以一旦指標斷裂會造成資料遺失，可靠度較差。LinkedList與ArrayList都是非執行緒安全的。LinkedList與ArrayList都允許重複且為null的元素。
因此在使用時機上，若只需要讀取List中的元素或做排序，就使用ArrayList。若需要經常新增或刪除List中的元素，就使用LinkedList。
如果覺得文章有幫助的話還幫忙點個Google廣告，感恩。
沒有留言:
張貼留言