鏈表是一種隨機存儲在內存中的叫做節點的對象集合。
節點包含兩個字段，即存儲在該地址的數據和包含下一個節點地址的指針。
鏈表的最後一個節點包含指向null的指針。
1. 鏈表的用途
- 鏈表不需要連續存在於記憶體中。節點可以是記憶體中的任何位置並鏈接在一起以形成鏈表。這實現了空間的優化利用。
- 鏈表大小僅限於記憶體大小，不需要提前聲明。
- 空節點不能出現在鏈表中。
- 在單鏈表中存儲基元類型或對象的值。
2. 為什麼鏈表比數組有優勢？
到目前為止，學習了如何使用數組數據結構來組織要在內存中單獨存儲的元素組。 但是，數組有幾個優點和缺點，必須知道這些優點和缺點才能確定將在整個程式中使用的什麼樣類型的數據結構。
數組有以下限制：
- 在程式中使用數組之前，必須事先知道數組的大小。
- 增加數組的大小是一個耗時的過程。在運行時幾乎不可能擴展數組的大小。
- 數組中的所有元素都需要連續存儲在內存中。在數組中插入任何元素都需要移動元素之前所有的數據。
鏈表是可以克服數組所有限制的數據結構。 鏈表是非常有用的，因為，
- 它動態分配記憶體。鏈表的所有節點都是非連續存儲在記憶體中，並使用指針鏈接在一起。
- 大小調整不再是問題，因為不需要在聲明時定義大小。鏈表根據程式的需求增長，並且僅限於可用的記憶體空間。
3. 單鏈表或單向鏈
單鏈表是有序元素集的集合。元素的數量可以根據程式的需要而變化。 單鏈表中的節點由兩部分組成：數據部分和鏈接部分。 節點的數據部分存儲將由節點表示的實際資訊，而節點的鏈接部分存儲其直接後繼的地址。
單向鏈或單鏈表可以僅在一個方向上遍曆。也就是說每個節點只包含下一個節點的指針，因此不能反向遍曆鏈表。
考慮一個例子，學生在三個科目的成績存儲在如圖所示的鏈表中 -
在上圖中，箭頭表示鏈接。每個節點的數據部分包含學生在不同科目成績。鏈表中的最後一個節點由空指針標識，該空指針存在於最後一個節點的地址部分中。可在鏈表的數據部分中包含所需的數據元素。
複雜度
時間複雜度 -
| 操作 | 平均複雜度 | 最壞複雜度 |
|---|---|---|
| 訪問 | θ(n) | θ(n) |
| 搜索 | θ(n) | θ(n) |
| 插入 | θ(1) | θ(1) |
| 刪除 | θ(1) | θ(1) |
4. 單鏈表上的操作
可以在單鏈表上執行各種操作。下麵給出了所有這些操作列表。
4.1. 節點創建
struct node
{
int data;
struct node *next;
};
struct node *head, *ptr;
ptr = (struct node *)malloc(sizeof(struct node *));
4.2. 插入
在不同位置執行插入節點到單個鏈表。根據插入的新節點的位置，插入分為以下類別。
| 編號 | 操作 | 描述 |
|---|---|---|
| 1 | 插入到鏈表開頭 | 它涉及在鏈表的前面插入任何元素。只需要進行一些鏈接調整，以使新節點成為鏈表的頭部。 |
| 2 | 插入到鏈表末尾 | 它涉及插入鏈表的最後一個位置。 新節點可以作為列表中的唯一節點插入，也可以作為最後一個插入。在每個場景中實現不同的邏輯。 |
| 3 | 在指定節點之後插入 | 它涉及在鏈表的指定節點之後插入。需要跳過所需數量的節點才能到達指定節點，之後插入新節點。 |
4.3. 刪除和遍曆
在不同位置執行從單鏈表中刪除節點。根據要刪除的節點的位置，操作分為以下類別。
| 編號 | 操作 | 描述 |
|---|---|---|
| 1 | 刪除鏈表開頭節點 | 它涉及從鏈表的開頭節點刪除。這是所有操作中最簡單的操作。它只需要在節點指針中進行一些調整。 |
| 2 | 刪除鏈表末尾節點 | 它涉及刪除列表的最後一個節點。鏈表可以為空或完整。針對不同場景實現不同的邏輯。 |
| 3 | 刪除指定節點之後節點 | 它涉及刪除鏈表中指定節點之後的節點。需要跳過所需數量的節點才能到達節點，之後的節點將被刪除。這需要遍曆鏈表。 |
| 4 | 遍曆 | 在遍曆中，簡單地訪問鏈表的每個節點至少一次，以便對其執行某些特定操作，例如，列印列表中存在的每個節點的數據部分。 |
| 5 | 搜索 | 在搜索中，將鏈表的每個元素與給定元素匹配。 如果在任何位置找到該元素，則返回該元素的位置，否則返回null。。 |
菜單驅動程式，用於實現單鏈表上的所有操作(使用C語言實現)，代碼如下所示 -
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head;
void beginsert();
void lastinsert();
void randominsert();
void begin_delete();
void last_delete();
void random_delete();
void display();
void search();
void main()
{
int choice = 0;
while (choice != 9)
{
printf("\n\n********* 主菜單 *********\n");
printf("從以下菜單列表中選擇一個選項操作 ...\n");
printf("===============================================\n");
printf("1.插入到開頭\n");
printf("2.插入到結尾\n");
printf("3.插入任何隨機位置\n");
printf("4.從頭部刪除\n");
printf("5.從尾部刪除\n");
printf("6.刪除指定位置後的節點\n");
printf("7.搜索元素\n");
printf("8.顯示鏈表中的數據\n");
printf("9.退出\n\n");
printf("===============================================\n");
printf("請輸入您的選擇：");
scanf("%d", &choice);
switch (choice)
{
case 1:
beginsert();
break;
case 2:
lastinsert();
break;
case 3:
randominsert();
break;
case 4:
begin_delete();
break;
case 5:
last_delete();
break;
case 6:
random_delete();
break;
case 7:
search();
break;
case 8:
display();
break;
case 9:
exit(0);
break;
default:
printf("請輸入有效的選項...");
}
}
}
void beginsert()
{
struct node *ptr;
int item;
ptr = (struct node *) malloc(sizeof(struct node *));
if (ptr == NULL)
{
printf("記憶體不夠！\n");
}
else
{
printf("請輸入一個整數值：");
scanf("%d", &item);
ptr->data = item;
ptr->next = head;
head = ptr;
printf("節點已經成功插入\n");
}
}
void lastinsert()
{
struct node *ptr, *temp;
int item;
ptr = (struct node*)malloc(sizeof(struct node));
if (ptr == NULL)
{
printf("記憶體不夠！\n");
}
else
{
printf("請輸入一個整數值：");
scanf("%d", &item);
ptr->data = item;
if (head == NULL)
{
ptr->next = NULL;
head = ptr;
printf("節點已經成功插入\n");
}
else
{
temp = head;
while (temp->next != NULL)
{
temp = temp->next;
}
temp->next = ptr;
ptr->next = NULL;
printf("節點已經成功插入\n");
}
}
}
void randominsert()
{
int i, loc, item;
struct node *ptr, *temp;
ptr = (struct node *) malloc(sizeof(struct node));
if (ptr == NULL)
{
printf("記憶體不夠！\n");
}
else
{
printf("請輸入一個整數值：");
scanf("%d", &item);
ptr->data = item;
printf("輸入要插入的位置：");
scanf("%d", &loc);
temp = head;
for (i = 0;i < loc;i++)
{
temp = temp->next;
if (temp == NULL)
{
printf("此處不能插入節點\n");
return;
}
}
ptr->next = temp->next;
temp->next = ptr;
printf("節點已經成功插入\n");
}
}
void begin_delete()
{
struct node *ptr;
if (head == NULL)
{
printf("鏈表為空，沒有什麼可以刪除！\n");
}
else
{
ptr = head;
head = ptr->next;
free(ptr);
printf("已經刪除頭部節點 ...\n");
}
}
void last_delete()
{
struct node *ptr, *ptr1;
if (head == NULL)
{
printf("鏈表為空，沒有什麼可以刪除！\n");
}
else if (head->next == NULL)
{
head = NULL;
free(head);
printf("唯一的節點已經被刪除了...\n");
}
else
{
ptr = head;
while (ptr->next != NULL)
{
ptr1 = ptr;
ptr = ptr->next;
}
ptr1->next = NULL;
free(ptr);
printf("已刪除最後一個節點...\n");
}
}
void random_delete()
{
struct node *ptr, *ptr1;
int loc, i;
printf("輸入要在此節點之後執行刪除的節點的位置：");
scanf("%d", &loc);
ptr = head;
for (i = 0;i < loc;i++)
{
ptr1 = ptr;
ptr = ptr->next;
if (ptr == NULL)
{
printf("不能刪除\n");
return;
}
}
ptr1->next = ptr->next;
free(ptr);
printf("\n第 %d 個節點已經被刪除了", loc + 1);
}
void search()
{
struct node *ptr;
int item, i = 0, flag;
ptr = head;
if (ptr == NULL)
{
printf("鏈表為空！\n");
}
else
{
printf("請輸入要搜索的專案：");
scanf("%d", &item);
while (ptr != NULL)
{
if (ptr->data == item)
{
printf("在 %d 位置找到資料項目\n", i + 1);
flag = 0;
}
else
{
flag = 1;
}
i++;
ptr = ptr->next;
}
if (flag == 1)
{
printf("資料項目未找到\n");
}
}
}
/**
* 顯示鏈表中的數據
*/
void display()
{
struct node *ptr;
ptr = head;
if (ptr == NULL)
{
printf("鏈表為空，沒有數據可以顯示。");
}
else
{
printf("鏈表中的數據值如下所示：\n");
printf("--------------------------------------------------\n");
while (ptr != NULL)
{
printf("\n%d", ptr->data);
ptr = ptr->next;
}
}
printf("\n\n\n");
}
輸出結果如下 -
********* 主菜單 *********
從以下菜單列表中選擇一個選項操作 ...
===============================================
1.插入到開頭
2.插入到結尾
3.插入任何隨機位置
4.從頭部刪除
5.從尾部刪除
6.刪除指定位置後的節點
7.搜索元素
8.顯示鏈表中的數據
9.退出
===============================================
請輸入您的選擇：1
請輸入一個整數值：111
節點已經成功插入
********* 主菜單 *********
從以下菜單列表中選擇一個選項操作 ...
===============================================
1.插入到開頭
2.插入到結尾
3.插入任何隨機位置
4.從頭部刪除
5.從尾部刪除
6.刪除指定位置後的節點
7.搜索元素
8.顯示鏈表中的數據
9.退出
===============================================
請輸入您的選擇：2
請輸入一個整數值：2222
節點已經成功插入
********* 主菜單 *********
從以下菜單列表中選擇一個選項操作 ...
===============================================
1.插入到開頭
2.插入到結尾
3.插入任何隨機位置
4.從頭部刪除
5.從尾部刪除
6.刪除指定位置後的節點
7.搜索元素
8.顯示鏈表中的數據
9.退出
......