鏈結串列的抽象資料結構
以下是鏈結串列的抽象資料結構 (ADT)：
L is a list
sub IsEmpty(L): bool
sub PeekFront(L): result
sub PeekRear(L): result
sub At(L, index): result, 0 <= index < size
sub SetAt(L, index, value): bool, 0 <= index < size
sub Unshift(L, value): bool
sub Push(L, value): bool
sub Shift(L): result
sub Pop(L): result
sub InsertAt(L, index, value): bool
sub RemoveAt(L, index): (result, bool)由此可知，串列有以下和狀態相關的行為：
IsEmpty(L)：確認串列是否為空PeekFront(L)：檢視串列頭端的元素PeekRear(L)：檢視串列尾端的元素At(L, index)：檢視串列任意位置的元素SetAt(L, index, value)：設置串列任意位置的元素
除此之外，串列可透過以下方式來操作：
Unshift(L, value)：從串列頭端放入元素Push(L, value)：從串列尾端放入元素Shift(L)：從串列頭端移出元素Pop(L)：從串列尾端移出元素InsertAt(L, index, value)：從串列任意位置放入元素RemoveAt(L, index)：從串列任意位置移出元素
鏈結串列一部分的操作和佇列或雙向佇列重疊，讀者若不熟悉這些部分可再回頭閱讀。
宣告鏈結串列的類別
鏈結串列的類別宣告如下：
class Node:
data <- empty
prev <- null
next <- null
class List:
head <- null
tail <- null
size <- 0如同我們先前實作佇列般，串列分為內部節點 Node 和主類別 List。等效的 C 語言宣告如下：
typedef struct node node_t;
struct node {
int data;
node_t *prev;
node_t *next;
};
typedef struct list list_t;
struct list {
node_t *head;
node_t *tail;
size_t size;
};鏈結串列的建構函式
以下是 C 語言版本的串列建構函式：
list_t * list_new(void)
{
list_t *lt = malloc(sizeof(list_t));
if (!lt) {
return lt;
}
lt->head = NULL;
lt->tail = NULL;
lt->size = 0;
return lt;
}上述建構函式會建立一個空串列，這是傳統的建構函式的寫法。也可以在初始化時塞入一些值，使用方式如下：
list_t *lt = list_init(4, 6, 8, 5, 7);在 list_init 建構函式中，第一個參數代表串列長度，第二個以後的參數代表實際填入的值。以下是其 C 語言實作：
list_t * list_init(size_t size, int value, ...) /* 1 */
{ /* 2 */
list_t *lt = malloc(sizeof(list_t)); /* 3 */
if (!lt) /* 4 */
return lt; /* 5 */
node_t *first = node_new(value); /* 6 */
if (!first) { /* 7 */
list_delete(lt); /* 8 */
lt = NULL; /* 9 */
return lt; /* 10 */
} /* 11 */
lt->head = first; /* 12 */
lt->tail = first; /* 13 */
lt->size = 0; /* 14 */
va_list args; /* 15 */
va_start(args, value); /* 16 */
lt->size++; /* 17 */
node_t *temp; /* 18 */
for (size_t i = 1; i < size; i++) { /* 19 */
temp = node_new(va_arg(args, int)); /* 20 */
if (temp == NULL) { /* 21 */
list_delete(lt); /* 22 */
lt = NULL; /* 23 */
va_end(args); /* 24 */
return lt; /* 25 */
} /* 26 */
lt->tail->next = temp; /* 27 */
temp->prev = lt->tail; /* 28 */
lt->tail = temp; /* 29 */
lt->size++; /* 30 */
} /* 31 */
va_end(args); /* 32 */
return lt; /* 33 */
} /* 34 */在第 3 行至第 14 行，和先前的建構函式中建立 list_t 型態的物件 lt 的方式雷同，故不重覆說明。
在第 15 行至第 17 行，我們將不定參數物件 args 初始化，並填入第一個參數 value。
在第 18 行至第 31 行，我們依序填入其他的參數。每個參數在填入時，都要建立新的內部節點。我們在第 20 行建立內部節點，並在第 21 行至第 26 行檢查該節點是否成功地建立。若建立失敗，則清除 lt 物件及 args 物件，並回傳空指標。
在第 32 行，將 args 物件清除。
最後，在第 33 行，回傳 lt 物件。
在此建構函式中，我們使用到不定參數相關的一些巨集，這些巨集由 stdarg.h 函式庫所提供。使用時會依序使用以下四個巨集：
va_list：建立代表參數串列的變數va_start：設置參數串列起始位置va_arg：從參數串列取值va_end：結束此參數串列
讀者可參考本建構函式來學習如何使用不定參數。
鏈結串列的解構函式
以下是以 C 語言實作的解構函式：
void list_delete(void *self) /* 1 */
{ /* 2 */
if (!self) { /* 3 */
return; /* 4 */
} /* 5 */
node_t *curr = ((list_t *) self)->head; /* 6 */
while (curr) { /* 7 */
node_t *temp = curr; /* 8 */
curr = curr->next; /* 9 */
free(temp); /* 10 */
} /* 11 */
free(self); /* 12 */
} /* 13 */同樣的，要先逐一釋放內部節點後，再釋放掉物件本身。我們在第 6 行至第 11 行中，逐一走訪內部節點，邊走訪邊釋放其記憶體。最後在第 12 行中，釋放 self 物件本身。
檢查鏈結串列是否為空
以下是檢查串列是否為空的虛擬碼：
sub IsEmpty(L):
check whether L->head == null檢查其頭端 head 是否為空即可。以下是等效的 C 語言實作：
bool list_is_empty(const list_t *self)
{
assert(self);
return self->head == NULL;
}檢視鏈結串列頭端的資料
以下是檢視串列頭端資料的虛擬碼：
sub PeekFront(L):
assert not IsEmpty(L)
return L->head->data先確認串列不為空，再回傳頭端的資料 data 即可。以下是等效的 C 語言實作：
int list_peek_front(const list_t *self)
{
assert(!list_is_empty(self));
return self->head->data;
}檢視鏈結串列尾端的資料
和檢視頭端的情境類似，先確認串列不為空，再回傳其尾端的資料 data 即可。以下是等效的 C 語言實作：
int list_peek_rear(const list_t *self)
{
assert(!list_is_empty(self));
return self->tail->data;
}檢視鏈結串列中任意位置的資料
以下是檢視串列任意元置元素的虛擬碼：
sub At(L, index):
assert not IsEmpty(L)
assert 0 <= index < Size(L)
p <- L->head
i <- 0
while p != null do
if i == index then
return p->data
end if
p <- p->next
i <- i + 1
end while
throw Error("No available data")要先確認串列不為空以及索引值是合法的，接著再進行下一步動作。由於本範例內部以鏈結串列實作，需逐一走訪串列元素，直到符合索引值所在的位置為止。以下是等效的 C 語言實作：
bool list_at(const list_t *self, size_t index, int *out) /* 1 */
{ /* 2 */
assert(index < list_size(self)); /* 3 */
node_t* curr = self->head; /* 4 */
size_t i = 0; /* 5 */
while (curr) { /* 6 */
if (i == index) { /* 7 */
*out = curr->data; /* 8 */
return true; /* 9 */
} /* 10 */
curr = curr->next; /* 11 */
i++; /* 12 */
} /* 13 */
return false; /* 14 */
} /* 15 */由於 C 語言沒有錯誤處理的機制且僅能回傳單一值，所以我們在這裡修改一下該函式的介面。注意第 1 行的函式界面，除了回傳函式狀態的布林值外，我們另外用指向整數的指標 out 回傳資料。此函式會回傳執行成功與否的狀態，並將回傳值寫在 out 中。
由於串列無法像陣列般直接用索引值存取，我們我們在第 6 行至第 13 行間，以迴圈逐一走訪內部節點。走到索引值所在的地方，將資料傳至 out，回傳的動件在第 8 行。
使用實例如下：
/* Allocate some memory for `out`. */
int *out = malloc(sizeof(int));
if (!list_at(lt, 2, out)) {
/* `out` is invalid. */
/* Handle the error. */
}
/* Free `out` later. */修改鏈結串列任意位置的資料
以下虛擬碼展示如何修改串列中任意位置的資料：
sub SetAt(L, index, value):
assert L != null
assert 0 <= index < L->size
p <- L->head
i <- 0
while p != null do
if i == index then
p->data <- value
end if
p <- p->next
i <- i + 1
end while同樣地，要先確認串列不為空且索引值合法。接著，逐一走訪串列直到符合索引所在的位置，修改元素的值後結束程式。以下是等效的 C 語言實作：
bool list_set_at(list_t *self, size_t index, int data)
{
assert(self);
assert(index < list_size(self));
node_t* curr = self->head;
size_t i = 0;
while (curr) {
if (i == index) {
curr->data = data;
return true;
}
curr = curr->next;
i++;
}
return false;
}同樣地，由於 C 語言沒有錯誤處理的機制，此函式會回傳程式執行成功與否的狀態。
從鏈結串列尾端放入一個元素
以下是從鏈結串列尾端放入元素的虛擬碼：
sub Push(L, data): void
node <- node_t(data)
if L.size == 0 then
L.head <- node
L.tail <- node
else
L.tail.next <- node
node.prev <- L.tail
L.tail <- node
end if
L.size += 1根據串列本身是否為空的處理方式略為不同。以下是等效的 C 程式實作：
bool list_push(list_t *self, int value) /* 1 */
{ /* 2 */
assert(self); /* 3 */
node_t *node = node_new(value); /* 4 */
if (!node) { /* 5 */
return false; /* 6 */
} /* 7 */
if (!(self->tail)) { /* 8 */
self->head = node; /* 9 */
self->tail = node; /* 10 */
} /* 11 */
else { /* 12 */
self->tail->next = node; /* 13 */
node->prev = self->tail; /* 14 */
self->tail = node; /* 15 */
} /* 16 */
self->size++; /* 17 */
return true; /* 18 */
} /* 19 */在推入資料時，要考慮串列本身是否為空。
在第 8 行至第 11 行間，是串列為空的情境，這時候串列的頭端和尾端都會指向同一個節點。
在第 12 行至第 16 行間，是串列不為空的情境，這裡候將新的節點推入串列的尾端即可。
從鏈結串列頭端放入一個元素
以下是從鏈結串列頭端放入元素的虛擬碼：
sub Unshift(L, value): void
node <- node_t(value)
if L.head == null then
L.head <- node
L.tail <- node
else
node.next <- L.head
L.head.prev <- node
L.head <- node
end if
L.size += 1根據串列本身是否為空的處理方式略為不同。以下是等效的 C 程式實作：
bool list_unshift(list_t *self, int value) /* 1 */
{ /* 2 */
assert(self); /* 3 */
node_t *node = node_new(value); /* 4 */
if (!node) { /* 5 */
return false; /* 6 */
} /* 7 */
if (!(self->head)) { /* 8 */
self->head = node; /* 9 */
self->tail = node; /* 10 */
} /* 11 */
else { /* 12 */
node->next = self->head; /* 13 */
self->head->prev = node; /* 14 */
self->head = node; /* 15 */
} /* 16 */
self->size++; /* 17 */
return true; /* 18 */
} /* 19 */在推入資料時，要考慮串列本身是否為空。
在第 8 行至第 11 行間，是串列為空的情境，這時候頭端和尾端都會指向新節點。
在第 12 行至第 16 行間，是串列不為空的情境，這時候會將新節點推入串列的頭端。
本節的實作和前一節類似，讀者可相互比較一下。
從鏈結串列尾端取出一個元素
以下是從鏈結串列尾端放入元素的虛擬碼：
sub Pop(L): result
assert not IsEmpty(L)
result <- L.tail.data
if L.head == L.tail then
delete L.tail
L.head <- null
L.tail <- null
else
p <- L.tail
L.tail <- p.prev
delete p
L.tail.next <- null
end if
L.size -= 1
return result根據串列本身的元素為單個或多個，處理方式相異。以下是等效的 C 程式實作：
int list_pop(list_t *self) /* 1 */
{ /* 2 */
assert(!list_is_empty(self)); /* 3 */
int popped = self->tail->data; /* 4 */
if (self->head == self->tail) { /* 5 */
free(self->tail); /* 6 */
self->head = NULL; /* 7 */
self->tail = NULL; /* 8 */
} /* 9 */
else { /* 10 */
node_t *curr = self->tail; /* 11 */
self->tail = curr->prev; /* 12 */
free(curr); /* 13 */
self->tail->next = NULL; /* 14 */
} /* 15 */
self->size--; /* 16 */
return popped; /* 17 */
} /* 18 */在移出資料時，有三個情境：
- 串列為空
- 串列僅存一個節點
- 串列還有多個節點
串列為空時，沒有資料可推出，這是不應當發生的情境，所以我們在第 3 行用斷言確認串列不為鑋。
由於推出的節點皆在尾端，我們一律在第 4 行先將推出的資料預存好。
第 5 行至第 9 行是串列僅單一節點的情境，這時候將僅存的節點釋放掉。
第 10 行至第 15 行則是串列還存在多個節點的情境，這時候將尾端的指標前移一個節點，然後釋放原本尾端的節點。
最後，在第 17 行回傳推出的資料。
從鏈結串列頭端取出一個元素
以下是從串列頭端取出元素的虛擬碼：
sub Shift(L): result
assert not IsEmpty(L)
result <- L.head
if L.head == L.tail then
delete L.head
L.head <- null
L.tail <- null
else
p <- L.head
L.head <- p.next
delete p
L.head.prev <- null
end
L.size -= 1
return result根據串列元素為單個或多個，處理方式有所不同。以下是等效的 C 程式實作：
int list_shift(list_t *self)
{
assert(!list_is_empty(self));
int popped = self->head->data;
if (self->head == self->tail) {
free(self->head);
self->head = NULL;
self->tail = NULL;
}
else {
node_t *curr = self->head;
self->head = curr->next;
free(curr);
self->head->prev = NULL;
}
self->size--;
return popped;
}從鏈結串列中任意位置放入元素
以下是從串列中任意位置放入元素的虛擬碼：
sub InsertAt(L, index, data): void
if L.size == 0 then
assert index == 0
else
assert 0 <= index <= L.size
end
node <- node_t(data)
if L.size == 0 then
L.head <- node
L.tail <- node
L.size += 1
return
end if
p <- null
q <- L.head
i <- 0
while q.next != null do
if i == index then
if p == null then
node.next <- q
q.prev <- node
q <- node
else
p.next <- node
q.prev <- node
node.prev <- p
node.next <- q
end if
break
end if
p <- q
q <- q.next
i += 1
end while
if q == L.tail then
L.tail.next <- node
node.prev <- L.tail
L.tail <- node
end
L.size += 1當串列為空時，直接放入元素即可。
走訪串列的方式是以兩個指標來走訪，一個指標指向目前的元素，一個則指向前一個元素。當串列不為空時，可再細分為三個情境：
- 放在串列頭端
- 放在串列尾端
- 放在串列其他位置
當放在串列頭 (或尾) 端時，會影響串列頭 (或尾) 端指標所指向的元素，故需獨立處理。以下是等效的 C 語言程式碼：
bool list_insert_at(list_t *self, size_t index, int value)
{
assert(self);
if (!(self->head)) {
assert(index == 0);
} else {
assert(0 <= index && index <= self->size);
}
node_t *node = node_new(value);
if (!node) {
return false;
}
if (!(self->head)) {
self->head = node;
self->tail = node;
self->size++;
return true;
}
node_t *p = NULL;
node_t *q = self->head;
size_t i = 0;
while(q->next) {
if (i == index) {
if (!p) {
node->next = q;
q->prev = node;
q = node;
self->head = q;
} else {
p->next = node;
node->prev = p;
q->prev = node;
node->next = q;
}
break;
}
p = q;
q = q->next;
i++;
}
if (q == self->tail) {
q->next = node;
node->prev = q;
q = node;
self->tail = q;
}
self->size++;
return true;
}從鏈結串列中任意位置取出元素
在從串列中移出元素時，需考慮以下情境：
- 串列為空
- 串列僅單個元素
- 串列有多個元素
在本例中，第一個情形直接以錯誤排除，第三個情形需再細分，下文會說明。以下是虛擬碼：
sub RemoveAt(L, index): result
assert not IsEmpty(L)
if L.size == 1 then
assert index == 0
else
assert 0 <= index < L.size
end if
if L.size == 1 then
result <- L.head.data
delete L.head
L.head <- null
L.tail <- null
L.size -= 1
return result
end if
p <- null
q <- L.head
i <- 0
while q.next != null do
if i == index then
result <- q.data
if p == null then
L.head <- q.next
delete q
L.head.prev <- null
else
p.next <- q.next
q.next.prev <- p
delete q
end if
break
end if
p <- q
q <- q.next
i += 1
end while
if q == L.tail then
result <- q.data
L.tail <- q.prev
delete q
L.tail.next <- null
end if
L.size -= 1
return result當串列僅單個元素時，直接移出該元素即可。
走訪串列的方式是以兩個指標來走訪，一個指標指向目前的元素，一個則指向前一個元素。當串列有多個元素時，需再區分：
- 從串列頭端移出元素
- 從串列尾端移出元素
- 從串列其他位置移出元素
當從串列頭 (或尾) 端移出串列時，會影響頭 (或尾) 端指標所指向的元素，故需獨立出來處理。
int list_remove_at(list_t *self, size_t index)
{
assert(!list_is_empty(self));
if (list_size(self) == 1) {
assert(index == 0);
}
else {
assert(index < list_size(self));
}
if (list_size(self) == 1) {
int result = self->head->data;
free(self->head);
self->head = NULL;
self->tail = NULL;
self->size--;
return result;
}
int result;
node_t *p = NULL;
node_t *q = self->head;
size_t i = 0;
while (q->next) {
if (i == index) {
result = q->data;
if (!p) {
self->head = q->next;
free(q);
self->head->prev = NULL;
}
else {
p->next = q->next;
q->next->prev = p;
free(q);
}
break;
}
p = q;
q = q->next;
i++;
}
if (q == self->tail) {
result = q->data;
self->tail = p;
free(q);
self->tail->next = NULL;
}
self->size--;
return result;
}在演算法上的效率
以下和狀態相關的行為的演算法效率如下：
IsEmpty(L)：O(1)PeekFront(L)：O(1)PeekRear(L)：O(1)At(L, index)：O(n)SetAt(L, index, value)：O(n)
由此可見，以索引操作串列的效率會比陣列差，如果串列大小不會更動或更動不頻繁的話，或許可考慮改用陣列。
以下操作串列的方法的演算法效率如下：
Unshift(L, value)：O(1)Push(L, value)：O(1)Shift(L)：O(1)Pop(L)：O(1)InsertAt(L, index, value)：O(n)RemoveAt(L, index)：O(n)
由此可見若串列大小會頻繁更動時，串列的效率會比陣列好。