鏈結串列

出自維基百科,自由嘅百科全書
跳去導覽 跳去搵嘢

鏈結串列英文linked list)係一種攞嚟裝相關嘅數據循序存取數據結構。一條鏈結串列由若干件叫做節點(node)嘅數據組成,每個節點含有一個值(可以係單一數據,或者概念上係任何數據結構)同下一個節點嘅位置。當要喺鏈結串列入面任何一個節點裝嘅數據嘅時候,就一定要由頭開始,跟住條鏈,順次序噉嚟搵,冇得話(例如好似陣列噉)隨機存取是但一件數據,不過鏈結串列好處係可以容易噉由柞數據當中攞走其中一件而唔使重新排過嗮柞數據(一個陣列攞走咗其中一件再排過就要改嗮後面嗰啲數據嘅位置數值)。

Singly-linked-list.svg


喺低階嘅層次,下一個節點嘅位置通常係指指標。但係鏈結串列亦都可以作為一種抽象概念,運用喺例如陣列之上;喺呢類情形,下一個節點嘅位置就未必係指標,例如,如果鏈結串列係建立喺陣列上面,下一個節點嘅位置就會係整數嘅陣列索引值。

鏈嘅終結係用一個冇可能嘅位置表示。例如,如果位置係指標,呢個冇可能嘅位置喺 C 語系叫做 NULL(數值通常係零);又例如,如果位置係陣列索引值,冇可能嘅位置可以用負數代表(如果索引唔可以係負數);又或者,喺某一啲嘅高楷語言,呢種冇可能嘅位置可以係唔同嘅一種數據類型(或者物件類型),或者甚至係唔存在。

[編輯]

例如以下嘅 Python (睇埋物件導向編程):

class Node:
    # Node 係個物件類別
    def __init__(self, data):
        self.data = data  # Node 裝住件數據 (data)
        self.next = None  # 亦帶有 next(下一個 Node 係乜),呢個值初始化嗰陣係 None

鏈結串列係 Lisp 嘅基礎。如果有任何一個串列 aa 嘅頭一個節點嘅值就叫做 (car a),下一個節點開始嘅鏈就叫 (cdr a)[註 1],即係第二個節點係 (car (cdr a)),如此類推。

睇埋[編輯]

[編輯]

  1. cdr 讀 /ˈkudɚ/,類似粵讀 ku1 daa4