資料結構和算法之連結清單 | 連結清單介紹（難度級别：簡單）

與數組一樣，連結清單是一種線性資料結構。與數組不同，連結清單元素不存儲在連續的位置；元素使用指針連結。

為什麼使用連結清單？

數組可用于存儲類似類型的線性資料，但數組有以下限制。

1）數組的大小是固定的：是以我們必須提前知道元素數量的上限。此外，一般而言，配置設定的記憶體與使用情況無關，等于上限。

2)在元素數組中插入一個新元素是昂貴的，因為必須為新元素建立房間，并且必須移動現有元素才能建立房間。

例如，在一個系統中，如果我們在數組 id[] 中維護一個已排序的 ID 清單。

id[] = [1000, 1010, 1050, 2000, 2040]。

而如果我們要插入一個新的ID 1005，那麼為了保持排序順序，我們必須将1000之後的所有元素（不包括1000）移動。

除非使用某些特殊技術，否則删除數組的代價也很高。例如，要删除 id[] 中的 1010，必須移動 1010 之後的所有内容。

優于數組的優點

1)動态大小

2)易于插入/删除

缺點：

1)不允許随機通路。我們必須從第一個節點開始按順序通路元素。是以我們不能用它的預設實作有效地對連結清單進行二分搜尋。在這裡閱讀。

2)清單的每個元素都需要額外的指針存儲空間。

3) 對緩存不友好。由于數組元素是連續的位置，是以存在引用的局部性，而在連結清單的情況下則不存在。

表示：

連結清單由指向連結清單第一個節點的指針表示。第一個節點稱為頭部。如果連結清單為空，則頭部的值為NULL。

清單中的每個節點至少由兩部分組成：

1) 資料

2) 指向下一個節點的指針（或引用）

在 C 中，我們可以使用結構來表示一個節點。下面是一個帶有整數資料的連結清單節點的例子。

在 Java 或 C# 中，LinkedList 可以表示為一個類，而一個 Node 可以表示為一個單獨的類。LinkedList 類包含一個 Node 類類型的引用。

第一個簡單連結清單

1.C

//一個連結清單節點
struct Node {
    int data;
    struct Node* next;
};      

2.C++

class Node {
public:
    int data;
    Node* next;
};      

3.Java

class LinkedList {
    Node head; // head of the list
    /* 連結清單節點*/
    class Node {
        int data;
        Node next;
        // 建立新節點的構造函數
        // next  預設初始化為 null
        Node(int d) { data = d; }
    }
}      

4.Python

class Node:
    # 初始化節點對象的函數
    def __init__(self, data):
  self.data = data # 配置設定資料
  self.next = None # 将 next 初始化為 null
class LinkedList:   
    # 初始化連結清單對象的函數
    def __init__(self):
  self.head = None      

5.C#

class LinkedList {
    // 連結清單的第一個節點（head）
    // 将是 Node 類型的對象（預設為 null）
    Node head;
    class Node {
  int data;
  Node next;
  // 建立新節點的構造函數
  Node(int d) { data = d; }
    }
}      

讓我們建立一個具有 3 個節點的簡單連結清單。

// 一個示例 C++ 程式來介紹
// 一個連結清單
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
    int data;
    Node* next;
};
// 程式建立一個簡單的連結
// 包含 3 個節點的清單
int main()
{
    Node* head = NULL;
    Node* second = NULL;
    Node* third = NULL;
    // 在堆中配置設定 3 個節點
    head = new Node();
    second = new Node();
    third = new Node();
    /* 三個塊已被動态配置設定。
  我們有指向這三個塊的指針作為頭部，
  第二個和第三個
    head   second   third
  |    |    |
  |    |    |
    +---+-----+  +----+----+  +----+----+
    | # | # |  | # | # |  | # | # |
    +---+-----+  +----+----+  +----+----+
# 代表任何随機值。
資料是随機的，因為我們沒有配置設定
什麼都還沒有 */
    head->data = 1; // 在第一個節點配置設定資料
    head->next = second; // 将第一個節點與
    // 第二個節點
    /* 資料已配置設定到第一個的資料部分
  塊（頭部指向的塊）。 接下來
  第一個塊的指針指向第二個。
  是以他們兩個是有聯系的。
    head   second   third
  |    |    |
  |    |    |
    +---+---+  +----+----+  +-----+----+
    | 1 | o----->| # | # |  | # | # |
    +---+---+  +----+----+  +-----+----+    
*/
    // 将資料配置設定給第二個節點
    second->data = 2;
    // 将第二個節點與第三個節點連接配接起來
    second->next = third;
    /* 資料已經配置設定到第二個資料部分
    塊（由秒指向的塊）。 接下來
    第二個塊的指針指向第三個
    堵塞。 是以所有三個塊都是連結的。
    head   second   third
  |    |    |
  |    |    |
    +---+---+  +---+---+  +----+----+
    | 1 | o----->| 2 | o-----> | # | # |
    +---+---+  +---+---+  +----+----+  */
    third->data = 3; // 将資料配置設定給第三個節點
    third->next = NULL;
    /* 資料已配置設定到第三個資料部分
    塊（由第三個指向的塊）。 和下一個指針
    第三塊的 NULL 表示
    連結清單在這裡終止。
    我們已經準備好了連結清單。
  head  
    |
    |
  +---+---+  +---+---+  +----+------+
  | 1 | o----->| 2 | o-----> | 3 | NULL |
  +---+---+  +---+---+  +----+------+   
    請注意，隻有頭部足以表示
    整個清單。 我們可以周遊完整的
    按照下一個指針列出。*/
    return 0;
}      

連結清單周遊

在前面的程式中，我們建立了一個簡單的具有三個節點的連結清單。讓我們周遊建立的清單并列印每個節點的資料。對于周遊，讓我們編寫一個通用函數 printList() 來列印任何給定的清單。

// 一個用于周遊連結清單的簡單 C++ 程式
#include <bits/stdc++.h>
using namespace std;

class Node {
public:
    int data;
    Node* next;
};

// 此函數列印連結清單的内容
// 從給定節點開始
void printList(Node* n)
{
    while (n != NULL) {
        cout << n->data << " ";
        n = n->next;
    }
}

// 驅動程式代碼
int main()
{
    Node* head = NULL;
    Node* second = NULL;
    Node* third = NULL;

    // 在堆中配置設定 3 個節點
    head = new Node();
    second = new Node();
    third = new Node();

    head->data = 1; // 在第一個節點配置設定資料
    head->next = second; // 将第一個節點與第二個節點連接配接起來

    second->data = 2; // 将資料配置設定給第二個節點
    second->next = third;

    third->data = 3; // 将資料配置設定給第三個節點
    third->next = NULL;

    printList(head);

    return 0;
}