鏈表

本頁面將簡要介紹鏈表。

引入

鏈表是一種用於存儲數據的數據結構，通過如鏈條一般的指針來連接元素。它的特點是插入與刪除數據十分方便，但尋找與讀取數據的表現欠佳。

與數組的區別

鏈表和數組都可用於存儲數據。與鏈表不同，數組將所有元素按次序依次存儲。不同的存儲結構令它們有了不同的優勢：

鏈表因其鏈狀的結構，能方便地刪除、插入數據，操作次數是 \(O(1)\)。但也因為這樣，尋找、讀取數據的效率不如數組高，在隨機訪問數據中的操作次數是 \(O(n)\)。

數組可以方便地尋找並讀取數據，在隨機訪問中操作次數是 \(O(1)\)。但刪除、插入的操作次數是 \(O(n)\) 次。

構建鏈表

Tip

構建鏈表時，使用指針的部分比較抽象，光靠文字描述和代碼可能難以理解，建議配合作圖來理解。

單向鏈表

單向鏈表中包含數據域和指針域，其中數據域用於存放數據，指針域用來連接當前結點和下一節點。

實現

C++Python

struct Node {
  int value;
  Node *next;
};

class Node:
    def __init__(self, value = None, next = None): 
        self.value = value
        self.next = next

雙向鏈表

雙向鏈表中同樣有數據域和指針域。不同之處在於，指針域有左右（或上一個、下一個）之分，用來連接上一個結點、當前結點、下一個結點。

實現

C++Python

struct Node {
  int value;
  Node *left;
  Node *right;
};

class Node:
    def __init__(self, value = None, left = None, right = None): 
        self.value = value
        self.left = left
        self.right = right

向鏈表中插入（寫入）數據

單向鏈表

流程大致如下：

初始化待插入的數據 node；
將 node 的 next 指針指向 p 的下一個結點；
將 p 的 next 指針指向 node。

具體過程可參考下圖：

代碼實現如下：

實現

C++Python

void insertNode(int i, Node *p) {
  Node *node = new Node;
  node->value = i;
  node->next = p->next;
  p->next = node;
}

def insertNode(i, p):
    node = Node()
    node.value = i
    node.next = p.next
    p.next = node

單向循環鏈表

將鏈表的頭尾連接起來，鏈表就變成了循環鏈表。由於鏈表首尾相連，在插入數據時需要判斷原鏈表是否為空：為空則自身循環，不為空則正常插入數據。

大致流程如下：

初始化待插入的數據 node；
判斷給定鏈表 p 是否為空；
若為空，則將 node 的 next 指針和 p 都指向自己；
否則，將 node 的 next 指針指向 p 的下一個結點；
將 p 的 next 指針指向 node。

具體過程可參考下圖：

代碼實現如下：

實現

C++Python

void insertNode(int i, Node *p) {
  Node *node = new Node;
  node->value = i;
  node->next = NULL;
  if (p == NULL) {
    p = node;
    node->next = node;
  } else {
    node->next = p->next;
    p->next = node;
  }
}

def insertNode(i, p):
    node = Node()
    node.value = i
    node.next = None
    if p == None:
        p = node
        node.next = node
    else:
        node.next = p.next
        p.next = node

雙向循環鏈表

在向雙向循環鏈表插入數據時，除了要判斷給定鏈表是否為空外，還要同時修改左、右兩個指針。

大致流程如下：

初始化待插入的數據 node；
判斷給定鏈表 p 是否為空；
若為空，則將 node 的 left 和 right 指針，以及 p 都指向自己；
否則，將 node 的 left 指針指向 p;
將 node 的 right 指針指向 p 的右結點；
將 p 右結點的 left 指針指向 node；
將 p 的 right 指針指向 node。

代碼實現如下：

實現

C++Python

void insertNode(int i, Node *p) {
  Node *node = new Node;
  node->value = i;
  if (p == NULL) {
    p = node;
    node->left = node;
    node->right = node;
  } else {
    node->left = p;
    node->right = p->right;
    p->right->left = node;
    p->right = node;
  }
}

def insertNode(i, p):
    node = Node()
    node.value = i
    if p == None:
        p = node
        node.left = node
        node.right = node
    else:
        node.left = p
        node.right = p.right
        p.right.left = node
        p.right = node

從鏈表中刪除數據

單向（循環）鏈表

設待刪除結點為 p，從鏈表中刪除它時，將 p 的下一個結點 p->next 的值覆蓋給 p 即可，與此同時更新 p 的下下個結點。

流程大致如下：

將 p 下一個結點的值賦給 p，以抹掉 p->value；
新建一個臨時結點 t 存放 p->next 的地址；
將 p 的 next 指針指向 p 的下下個結點，以抹掉 p->next；
刪除 t。此時雖然原結點 p 的地址還在使用，刪除的是原結點 p->next 的地址，但 p 的數據被 p->next 覆蓋，p 名存實亡。

具體過程可參考下圖：

代碼實現如下：

實現

C++Python

void deleteNode(Node *p) {
  p->value = p->next->value;
  Node *t = p->next;
  p->next = p->next->next;
  delete t;
}

def deleteNode(p):
    p.value = p.next.value
    p.next = p.next.next

雙向循環鏈表

流程大致如下：

將 p 左結點的右指針指向 p 的右節點；
將 p 右結點的左指針指向 p 的左節點；
新建一個臨時結點 t 存放 p 的地址；
將 p 的右節點地址賦給 p，以避免 p 變成懸垂指針；
刪除 t。

代碼實現如下：

實現

C++Python

void deleteNode(Node *&p) {
  p->left->right = p->right;
  p->right->left = p->left;
  Node *t = p;
  p = p->right;
  delete t;
}

def deleteNode(p):
    p.left.right = p.right
    p.right.left = p.left
    p = p.right

技巧

異或鏈表

異或鏈表（XOR Linked List）本質上還是 雙向鏈表，但它利用按位異或的值，僅使用一個指針的內存大小便可以實現雙向鏈表的功能。

我們在結構 Node 中定義 lr = left ^ right，即前後兩個元素地址的 按位異或值。正向遍歷時用前一個元素的地址異或當前節點的 lr 可得到後一個元素的地址，反向遍歷時用後一個元素的地址異或當前節點的 lr 又可得到前一個的元素地址。這樣一來，便可以用一半的內存實現雙向鏈表同樣的功能。

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用