DSA 記憶體中的連結串列

計算機記憶體

為了解釋連結串列是什麼，以及連結串列與陣列的區別，我們需要了解一些關於計算機記憶體工作原理的基礎知識。

計算機記憶體是程式執行時使用的儲存空間。這是你的變數、陣列和連結串列儲存的地方。

記憶體中的變數

讓我們假設我們想在變數 myNumber 中儲存整數 "17"。為了簡化，我們假設這個整數儲存為兩個位元組（16 位），並且 myNumber 在記憶體中的地址是 0x7F30。

0x7F30 實際上是儲存 myNumber 整數值的兩個位元組記憶體中的第一個位元組的地址。當計算機訪問 0x7F30 來讀取整數值時，它知道必須讀取第一個和第二個位元組，因為在這個特定的計算機上整數是兩個位元組。

下圖顯示了變數 myNumber = 17 在記憶體中的儲存方式。

上面的例子展示了在簡單但流行的 Arduino Uno 微控制器上如何儲存整數值。這個微控制器具有 8 位架構和 16 位地址匯流排，整數和記憶體地址使用兩個位元組。相比之下，個人電腦和智慧手機使用 32 位或 64 位來儲存整數和地址，但記憶體的工作方式基本相同。

記憶體中的陣列

為了理解連結串列，先了解陣列在記憶體中的儲存方式是有益的。

陣列中的元素在記憶體中是連續儲存的。這意味著每個元素都儲存在前一個元素的正後面。

下圖顯示了整數陣列 myArray = [3,5,13,2] 在記憶體中的儲存方式。我們在這裡使用一種簡單的記憶體，每個整數佔用兩個位元組，就像前面的例子一樣，只是為了說明這個概念。

計算機只知道 myArray 第一個位元組的地址，所以要透過程式碼 myArray[2] 訪問第 3 個元素，計算機從 0x7F28 開始，跳過前兩個整數。計算機知道一個整數佔用兩個位元組，所以它從 0x7F28 向前跳 2x2 位元組，並在地址 0x7F32 處讀取值 13。

在陣列中刪除或插入元素時，所有後面的元素都必須向上移動以給新元素騰出空間，或者向下移動以填補被刪除元素的位置。這種移動操作非常耗時，並且可能在例如即時系統中引起問題。

下圖顯示了刪除陣列元素時元素如何移動。

如果你在 C 語言中程式設計，那麼運算元組也是你需要考慮的事情，因為在插入或刪除元素時，你必須顯式地移動其他元素。在 C 語言中，這不會在後臺自動發生。

在 C 語言中，你還需要確保一開始為陣列分配了足夠的空間，以便以後可以新增更多元素。

你可以在 這個之前的 DSA 教程頁面 上閱讀更多關於陣列的內容。

記憶體中的連結串列

與將資料集合儲存為陣列不同，我們可以建立一個連結串列。

連結串列在許多場景中都有使用，例如動態資料儲存、棧和佇列的實現或圖表示，僅舉幾例。

連結串列由節點組成，節點包含某種資料，以及至少一個指向其他節點的指標或連結。

使用連結串列的一個主要優點是節點儲存在記憶體中的任何可用空間中，節點不必像陣列中的元素那樣連續地儲存在一起。連結串列的另一個優點是，在新增或刪除節點時，列表中的其餘節點不必移動。

下圖顯示了連結串列如何在記憶體中儲存。連結串列有四個節點，值為 3、5、13 和 2，每個節點都有一個指向列表中下一個節點的指標。

每個節點佔用四個位元組。兩個位元組用於儲存整數值，兩個位元組用於儲存指向列表中下一個節點的地址。如前所述，儲存整數和地址所需的位元組數取決於計算機的體系結構。這個例子，就像前面的陣列例子一樣，適合簡單的 8 位微控制器架構。

為了更容易地看到節點之間的關係，我們將以一種更簡單的方式顯示連結串列中的節點，而不是與它們的記憶體位置相關聯，如下面的影像所示。

如果我們使用這種新的視覺化方法將前面例子中的四個節點放在一起，看起來是這樣的。

正如你所見，連結串列中的第一個節點稱為“頭”（Head），最後一個節點稱為“尾”（Tail）。

與陣列不同，連結串列中的節點不直接放在記憶體中。這意味著在插入或刪除節點時，不需要移動其他節點，這是一個優點。

連結串列的一個不太好的地方是，我們不能像訪問陣列那樣直接訪問節點，例如透過編寫 myArray[5]。要訪問連結串列中的第 5 個節點，我們必須從第一個節點“head”開始，使用該節點的指標訪問下一個節點，並在此過程中跟蹤已訪問節點的數量，直到到達第 5 個節點。

學習連結串列有助於我們更好地理解記憶體分配和指標等概念。

在學習樹和圖等更復雜的資料結構之前，理解連結串列也很重要，因為這些資料結構可以使用連結串列來實現。

現代計算機中的記憶體

到目前為止，在本頁中，我們使用了 8 位微控制器的記憶體作為示例，以使其簡單易懂。

現代計算機中的記憶體原則上與 8 位微控制器中的記憶體工作方式相同，但儲存整數和記憶體地址使用的記憶體更多。

下面的程式碼顯示了我們在執行這些示例的伺服器上整數的大小和記憶體地址的大小。

#include <stdio.h>

int main() {

    int myVal = 13;
    
    printf("Value of integer 'myVal': %d\n", myVal);
    printf("Size of integer 'myVal': %lu bytes\n", sizeof(myVal)); // 4 bytes
    printf("Address to 'myVal': %p\n", &myVal);
    printf("Size of the address to 'myVal': %lu bytes\n", sizeof(&myVal)); // 8 bytes

    return 0;
}

上面的程式碼示例僅在 C 語言中執行，因為 Java 和 Python 在特定/直接記憶體分配的抽象級別上執行。

C 語言中的連結串列實現

讓我們實現前面提到的連結串列

讓我們在 C 語言中實現這個連結串列，以檢視連結串列在記憶體中儲存的具體示例。

在下面的程式碼中，在包含庫之後，我們建立了一個節點結構，它類似於一個類，代表了一個節點是什麼：節點包含資料和指向下一個節點的指標。

函式 createNode() 為新節點分配記憶體，用作為函式引數給定的整數填充節點的 data 部分，並返回指向新節點的指標（記憶體地址）。

函式 printList() 只是用於遍歷連結串列並列印每個節點的值。

在 main() 函式內部，建立了四個節點，將它們連結在一起，打印出來，然後釋放記憶體。在使用完記憶體後釋放記憶體是一個好習慣，以避免記憶體洩漏。記憶體洩漏是指記憶體在使用後未被釋放，逐漸佔用越來越多的記憶體。

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

void printList(Node* node) {
    while (node) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("null\n");
}

int main() {
    Node* node1 = createNode(3);
    Node* node2 = createNode(5);
    Node* node3 = createNode(13);
    Node* node4 = createNode(2);

    node1->next = node2;
    node2->next = node3;
    node3->next = node4;

    printList(node1);

    // Free the memory
    free(node1);
    free(node2);
    free(node3);
    free(node4);

    return 0;
}

要列印上面的程式碼中的連結串列，函式 printList() 使用“next”指標從一個節點移動到下一個節點，這稱為連結串列的“遍歷”。你將在“連結串列操作”頁面上了解更多關於連結串列遍歷和其他連結串列操作的內容。

Python 和 Java 中的連結串列實現

我們現在將使用 Python 和 Java 來實現相同的連結串列。

在下面的 Python 程式碼中，Node 類代表節點是什麼：節點包含資料和指向下一個節點的連結。

該 Node 類用於建立四個節點，然後將這些節點連結在一起，最後打印出來。

正如你所見，Python 程式碼比 C 程式碼短得多，如果你只是想理解連結串列的概念，而不是連結串列在記憶體中的儲存方式，Python 程式碼可能更好。

Java 程式碼與 Python 程式碼非常相似。單擊下面的“執行示例”按鈕，然後選擇“Java”選項卡以檢視 Java 程式碼。

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
    
node1 = Node(3)
node2 = Node(5)
node3 = Node(13)
node4 = Node(2)

node1.next = node2
node2.next = node3
node3.next = node4

currentNode = node1
while currentNode:
    print(currentNode.data, end=" -> ")
    currentNode = currentNode.next
print("null")

A good thing about Linked Lists 
is that when inserting or 
removing a node, other elements 
do not have to be  in memory.