連結串列 - tw511教學網

連結串列是一種隨機儲存在記憶體中的叫做節點的物件集合。
節點包含兩個欄位，即儲存在該地址的資料和包含下一個節點地址的指標。
連結串列的最後一個節點包含指向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.退出

......