單鏈表採用非連續記憶體儲存，每個節點包含資料域與指標域，指標指向下一個節點。透過頭節點（哨兵節點）統一操作邏輯，避免頭尾特殊情況判斷。優勢在於插入刪除 O(1)（已知前驅節點），劣勢為查找 O(n)、額外指標空間開銷。
typedef int ElemType;
typedef struct Node {
ElemType data;
struct Node *next;
} Node, *LinkList; // LinkList 即 Node* 指向頭節點void InitList(LinkList *L) {
*L = (LinkList)malloc(sizeof(Node));
(*L)->next = NULL;
}
void DestroyList(LinkList *L) {
LinkList p = *L, q;
while (p) { q = p->next; free(p); p = q; }
*L = NULL; // 避免野指標
}
void ClearList(LinkList *L) { // 保留頭節點，釋放資料節點
LinkList p = (*L)->next, q;
while (p) { q = p->next; free(p); p = q; }
(*L)->next = NULL;
}頭插法：新節點插在頭節點後，順序與輸入相反，適合堆疊語意。
尾插法：維護尾指標，新節點接在尾部，保持輸入順序，適合佇列語意。
void HeadCreateList(LinkList *L, int n) {
for (int i=1; i<=n; i++) {
LinkList s = (LinkList)malloc(sizeof(Node));
scanf("%d", &s->data);
s->next = (*L)->next;
(*L)->next = s;
}
}
void TailCreateList(LinkList *L, int n) {
LinkList tail = *L;
for (int i=1; i<=n; i++) {
LinkList s = (LinkList)malloc(sizeof(Node));
scanf("%d", &s->data);
tail->next = s; s->next = NULL; tail = s;
}
}bool ListEmpty(LinkList L) { return L->next == NULL; }
int ListLength(LinkList L) {
int cnt=0; LinkList p=L->next;
while(p){ cnt++; p=p->next; } return cnt;
}
bool GetElem(LinkList L, int i, ElemType *e) { // 按位查找
if (i<1) return false;
LinkList p = L->next;
for (int j=1; p && jvoid GetPriorElem(LinkList L, ElemType cur, ElemType *pre) {
LinkList p = L->next;
while (p->next) {
if (p->next->data == cur) { *pre = p->data; return; }
p = p->next;
}
printf("無前驅或元素不存在\n");
}
void GetNextElem(LinkList L, ElemType cur, ElemType *next) {
LinkList p = L->next;
while (p) {
if (p->data == cur && p->next) { *next = p->next->data; return; }
p = p->next;
}
printf("無後繼或元素不存在\n");
}bool ListInsert(LinkList *L, int i, ElemType e) { // 第 i 個位置前插入
LinkList p = *L; int cnt = 0;
while (p && cnt < i-1) { p = p->next; cnt++; }
if (!p) return false;
LinkList s = (LinkList)malloc(sizeof(Node));
s->data = e; s->next = p->next; p->next = s;
return true;
}
bool ListDelete(LinkList *L, int i, ElemType *e) { // 刪除第 i 個
LinkList p = *L; int cnt = 0;
while (p && cnt < i-1) { p = p->next; cnt++; }
if (!p || !p->next) return false;
LinkList q = p->next; *e = q->data;
p->next = q->next; free(q); return true;
}void DisplayList(LinkList L) {
if (!L) { puts("List destroyed"); return; }
LinkList p = L;
while (p->next) { printf("%d ", p->next->data); p = p->next; }
puts("\n********displayList executed!");
}int main() {
LinkList L; InitList(&L);
TailCreateList(&L,4); DisplayList(L);
ClearList(&L); ListEmpty(L); DisplayList(L);
DestroyList(&L); DisplayList(L); // 驗證銷毀後狀態
InitList(&L); TailCreateList(&L,5);
printf("Length=%d\n", ListLength(L)); DisplayList(L);
ElemType r;
GetElem(L,5,&r) ? printf("GetElem 5=%d\n",r) : puts("Failed");
GetElem(L,6,&r) ? printf("GetElem 6=%d\n",r) : puts("Failed");
GetPriorElem(L,3,&r); printf("Prior of 3=%d\n",r);
GetNextElem(L,3,&r); printf("Next of 3=%d\n",r);
ListInsert(&L,5,999); DisplayList(L);
ListDelete(&L,2,&r); DisplayList(L); printf("Deleted=%d\n",r);
return 0;
}prior 指標，支援 O(1) 反向遍歷與刪除已知節點；unique_ptr/shared_ptr 自動管理生命週期，消除記憶體洩漏風險。單鏈表以指標串聯離散節點，實現動態擴容、高效插刪，是實作堆疊、佇列、哈希桶、圖鄰接表等高階結構的基石。熟練掌握「找前驅、改指標、管記憶體」三步驟，並養成畫圖驗證指標變化習慣，是攻克鏈表題目的關鍵。
