鏈結串列是一種把資料一個個串起來的資料結構。它與陣列類似，所儲存的資料都具備索引（index），在取得資料時便可透過索引來獲取它。然而兩者對資料的管理方式又有不同之處。
本文會解說鏈結串列的原理，再撰寫 Java 程式實作出新增、讀取與刪除，並適時地與陣列做比較。最後反轉整個串列的資料前後順序。
一、鏈結串列的構成
鏈結串列是由「標頭」（header）與「節點」（node）所構成。節點會有一到多個，就像列車車廂一節接著一節。節點包含了資料和指向下一個節點的鏈結，就像車廂載有乘客，且有連結器接在下一節車廂，而最後一節車廂沒有接在任何地方。
若節點也有指向上一個節點，我們稱為「雙向鏈結串列」，否則屬於「單向鏈結串列」。本文均以單向作為範例，以下為節點的程式實作。
public class Node<E> {
private E data;
private Node<E> next;
public Node(E data) {
this.data = data;
}
public E getData() {
return data;
}
public Node<E> getNext() {
return next;
}
public void setNext(Node<E> next) {
this.next = next;
}
@Override
public String toString() {
return data.toString();
}
}
而標頭至少會紀錄鏈結串列的首節點（first）和尾節點（last），首節點可說是從頭開始拜訪串列的進入點。紀錄它們也是為了在資料的新增與刪除更方便。以下是鏈結串列的程式雛型，在後面的小節還會實作其他方法。
public class LinkedList<E> {
private Node<E> first;
private Node<E> last;
private int size;
public int size() {
return this.size;
}
public E getFirst() {
return this.first.getData();
}
public E getLast() {
return this.last.getData();
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Node<E> node = this.first;
while (node != null) {
sb.append(node.toString()).append(" ");
node = node.getNext();
}
return sb.toString();
}
}
二、實作取得節點
由於鏈結串列各個節點的記憶體位置是不連續的，因此必須從第一個節點開始往後數，數到指定的索引後再回傳資料。
private Node<E> getNode(int index) {
if (index < 0 || index >= this.size) {
throw new IndexOutOfBoundsException();
}
Node<E> currentNode = this.first;
for (int i = 0; i < index; i++) {
currentNode = currentNode.getNext();
}
return currentNode;
}
public E get(int index) {
return getNode(index).getData();
}
相較之下，陣列元素的記憶體空間是連續的，所以元素的位址就像等差數列，可以透過起始位址和索引計算出來。這項差別讓串列取得資料的效率比陣列差。
三、實作新增節點
首先是在串列尾端新增資料。當串列原本是空的，只要更新標頭的首節點和尾節點即可，以提供拜訪串列的進入點。若串列已經有其他節點，則需將尾節點指向新節點，並更新標頭的尾節點。以下是示意圖與範例程式。
public void add(E data) {
Node<E> node = new Node<>(data);
if (this.size == 0) {
this.first = node;
} else {
this.last.setNext(node);
}
this.last = node;
this.size++;
}
讀者要知道，size 的值代表串列的節點數量，它會比最後一個節點的索引大1。因此當在指定位置新增節點，且位置參數 index 等於 size 時，就相當於在串列最後面新增節點。此處利用上述一般的 add 方法處理。
如果串列已有其他節點，且新節點指定要放在第一個位置，則將新節點的鏈結指向原本的首節點，並更新標頭的首節點即可。
若新增在其他位置，也就是串列中間，首先要找到目標位置的前一個節點，再透過它獲取下一個節點。接著調整鏈結，將新節點安插在兩者之間，使得順序為 previousNode → node→ nextNode。以下是示意圖與範例程式。
public void add(int index, E data) {
if (index < 0 || index > this.size) {
throw new IndexOutOfBoundsException();
}
if (index == this.size) {
add(data);
return;
}
Node<E> node = new Node<>(data);
if (index == 0) {
node.setNext(this.first);
this.first = node;
} else {
Node<E> previousNode = getNode(index - 1);
Node<E> nextNode = previousNode.getNext();
previousNode.setNext(node);
node.setNext(nextNode);
}
this.size++;
}
陣列在新增元素時較為劣勢，必須將目標位置後方的元素往後搬移，才能挪出空間。此外，由於陣列在建立時就必須決定容量（即長度），可能會有空間不足的問題。若想新增更多，就得將現有元素複製到空間足夠的陣列，造成時間的耗費。
而串列在新增節點時相對彈性。在串列中間新增節點，會需要從首節點尋找到目標位置，雖然看起來也是一種相當的時間耗費，但若是新增在第一個或最後一個，反而比陣列更有效率。
就串列的記憶體使用空間而言，在新增資料時才會索取新的記憶體。所以不像陣列會有空間不足，或索取太多用不到的空間而形成造成浪費的狀況。
四、實作刪除節點
我們從刪除串列的第一個節點開始解說，其分為兩種情形。若串列只有一個節點，只要將標頭的首節點和尾節點清空（設為null），使得拜訪串列的進入點消失即可。若串列有多個節點，則首節點的下一個節點將會是新的首節點，故將其更新到標頭。
接著是刪除其他位置節點的情形。首先要找到目標位置的前一個和後一個節點，接著調整鏈結，讓前者直接連結到後者，使得順序為 previousNode → nextNode。此外，假設要刪除的又正好是尾節點，那麼還需要更新標頭的尾節點。以下是示意圖與範例程式。
public void remove(int index) {
if (index < 0 || index >= this.size) {
throw new IndexOutOfBoundsException();
}
if (index == 0) {
if (this.size == 1) {
this.last = null;
}
this.first = this.first.getNext();
} else {
Node<E> previousNode = getNode(index - 1);
Node<E> targetNode = previousNode.getNext();
Node<E> nextNode = targetNode.getNext();
previousNode.setNext(nextNode);
if (index == size - 1) {
this.last = previousNode;
}
}
this.size--;
}
對於刪除的節點，它前面的節點會接上後面的節點，故能保持一個接著一個的狀態。而陣列為了使元素之間是連續的，不要有間隔，會將目標位置後方的元素往前搬移，造成額外的時間耗費。
在串列中間刪除節點，會需要從首節點拜訪到目標位置（使用 getNode 方法）。雖然看起來也是一種相當的時間耗費，但若是刪除第一個節點，仍比陣列有效率，畢竟不用搬移元素。且如果是雙向鏈結串列，刪除尾節點時亦可輕易找到倒數第二個做為新的尾節點，不必從頭拜訪串列。
五、反轉鏈結串列
最後來了解如何將鏈結串列的節點順序反轉過來。我們需要三個節點變數，藉此一邊在串列中前進，一邊將鏈結轉向。範例程式的 currentNode 代表正在處理的節點，而 previousNode 與
nextNode 分別是它的前、後節點。以下是示意圖與範例程式。
public void reverse() {
Node<E> previousNode = null;
Node<E> currentNode = this.first;
Node<E> nextNode;
while (currentNode != null) {
nextNode = currentNode.getNext();
currentNode.setNext(previousNode);
previousNode = currentNode;
currentNode = nextNode;
}
this.last = this.first;
this.first = previousNode;
}
首先從首節點開始處理，由於它沒有前一個節點，所以 previousNode 的值是null。反轉的做法不難，就是將目前的節點改成連接到前一個節點。此處使用 while 迴圈，依序處理每個節點。
在迴圈中，需要先準備好下一輪要處理的節點（nextNode），再反轉目前節點的鏈結。處理完畢後，我們將目前節點存入 previousNode，做為「下一輪的上個節點」。並將 nextNode 存入 currentNode，當作下一輪的目標。
如果某一輪所處理的節點已經沒有下個節點了，就代表所有鏈節都已經反轉完成，可以離開迴圈。最後再更新標頭的首節點和尾節點。
以下是本文的完整程式碼：
https://gist.github.com/ntub46010/1aa38cf238d43b514352510b40702c65
留言
張貼留言