4.2 鏈結串列¶

記憶體空間是所有程式的公共資源，在一個複雜的系統執行環境下，空閒的記憶體空間可能散落在記憶體各處。我們知道，儲存陣列的記憶體空間必須是連續的，而當陣列非常大時，記憶體可能無法提供如此大的連續空間。此時鏈結串列的靈活性優勢就體現出來了。

鏈結串列（linked list）是一種線性資料結構，其中的每個元素都是一個節點物件，各個節點透過“引用”相連線。引用記錄了下一個節點的記憶體位址，透過它可以從當前節點訪問到下一個節點。

鏈結串列的設計使得各個節點可以分散儲存在記憶體各處，它們的記憶體位址無須連續。

圖 4-5 鏈結串列定義與儲存方式

觀察圖 4-5 ，鏈結串列的組成單位是節點（node）物件。每個節點都包含兩項資料：節點的“值”和指向下一節點的“引用”。

鏈結串列的首個節點被稱為“頭節點”，最後一個節點被稱為“尾節點”。
尾節點指向的是“空”，它在 Java、C++ 和 Python 中分別被記為 null、nullptr 和 None 。
在 C、C++、Go 和 Rust 等支持指標的語言中，上述“引用”應被替換為“指標”。

如以下程式碼所示，鏈結串列節點 ListNode 除了包含值，還需額外儲存一個引用（指標）。因此在相同資料量下，鏈結串列比陣列佔用更多的記憶體空間。

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRubyZig

class ListNode:
    """鏈結串列節點類別"""
    def __init__(self, val: int):
        self.val: int = val               # 節點值
        self.next: ListNode | None = None # 指向下一節點的引用

/* 鏈結串列節點結構體 */
struct ListNode {
    int val;         // 節點值
    ListNode *next;  // 指向下一節點的指標
    ListNode(int x) : val(x), next(nullptr) {}  // 建構子
};

/* 鏈結串列節點類別 */
class ListNode {
    int val;        // 節點值
    ListNode next;  // 指向下一節點的引用
    ListNode(int x) { val = x; }  // 建構子
}

/* 鏈結串列節點類別 */
class ListNode(int x) {  //建構子
    int val = x;         // 節點值
    ListNode? next;      // 指向下一節點的引用
}

/* 鏈結串列節點結構體 */
type ListNode struct {
    Val  int       // 節點值
    Next *ListNode // 指向下一節點的指標
}

// NewListNode 建構子，建立一個新的鏈結串列
func NewListNode(val int) *ListNode {
    return &ListNode{
        Val:  val,
        Next: nil,
    }
}

/* 鏈結串列節點類別 */
class ListNode {
    var val: Int // 節點值
    var next: ListNode? // 指向下一節點的引用

    init(x: Int) { // 建構子
        val = x
    }
}

/* 鏈結串列節點類別 */
class ListNode {
    constructor(val, next) {
        this.val = (val === undefined ? 0 : val);       // 節點值
        this.next = (next === undefined ? null : next); // 指向下一節點的引用
    }
}

/* 鏈結串列節點類別 */
class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = val === undefined ? 0 : val;        // 節點值
        this.next = next === undefined ? null : next;  // 指向下一節點的引用
    }
}

/* 鏈結串列節點類別 */
class ListNode {
  int val; // 節點值
  ListNode? next; // 指向下一節點的引用
  ListNode(this.val, [this.next]); // 建構子
}

use std::rc::Rc;
use std::cell::RefCell;
/* 鏈結串列節點類別 */
#[derive(Debug)]
struct ListNode {
    val: i32, // 節點值
    next: Option<Rc<RefCell<ListNode>>>, // 指向下一節點的指標
}

/* 鏈結串列節點結構體 */
typedef struct ListNode {
    int val;               // 節點值
    struct ListNode *next; // 指向下一節點的指標
} ListNode;

/* 建構子 */
ListNode *newListNode(int val) {
    ListNode *node;
    node = (ListNode *) malloc(sizeof(ListNode));
    node->val = val;
    node->next = NULL;
    return node;
}

/* 鏈結串列節點類別 */
// 建構子
class ListNode(x: Int) {
    val _val: Int = x          // 節點值
    val next: ListNode? = null // 指向下一個節點的引用
}

# 鏈結串列節點類別
class ListNode
  attr_accessor :val  # 節點值
  attr_accessor :next # 指向下一節點的引用

  def initialize(val=0, next_node=nil)
    @val = val
    @next = next_node
  end
end

// 鏈結串列節點類別
pub fn ListNode(comptime T: type) type {
    return struct {
        const Self = @This();

        val: T = 0, // 節點值
        next: ?*Self = null, // 指向下一節點的指標

        // 建構子
        pub fn init(self: *Self, x: i32) void {
            self.val = x;
            self.next = null;
        }
    };
}

4.2.1 鏈結串列常用操作¶

1. 初始化鏈結串列¶

建立鏈結串列分為兩步，第一步是初始化各個節點物件，第二步是構建節點之間的引用關係。初始化完成後，我們就可以從鏈結串列的頭節點出發，透過引用指向 next 依次訪問所有節點。

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRubyZig

linked_list.py

# 初始化鏈結串列 1 -> 3 -> 2 -> 5 -> 4
# 初始化各個節點
n0 = ListNode(1)
n1 = ListNode(3)
n2 = ListNode(2)
n3 = ListNode(5)
n4 = ListNode(4)
# 構建節點之間的引用
n0.next = n1
n1.next = n2
n2.next = n3
n3.next = n4

linked_list.cpp

/* 初始化鏈結串列 1 -> 3 -> 2 -> 5 -> 4 */
// 初始化各個節點
ListNode* n0 = new ListNode(1);
ListNode* n1 = new ListNode(3);
ListNode* n2 = new ListNode(2);
ListNode* n3 = new ListNode(5);
ListNode* n4 = new ListNode(4);
// 構建節點之間的引用
n0->next = n1;
n1->next = n2;
n2->next = n3;
n3->next = n4;

linked_list.java

/* 初始化鏈結串列 1 -> 3 -> 2 -> 5 -> 4 */
// 初始化各個節點
ListNode n0 = new ListNode(1);
ListNode n1 = new ListNode(3);
ListNode n2 = new ListNode(2);
ListNode n3 = new ListNode(5);
ListNode n4 = new ListNode(4);
// 構建節點之間的引用
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;

linked_list.cs

/* 初始化鏈結串列 1 -> 3 -> 2 -> 5 -> 4 */
// 初始化各個節點
ListNode n0 = new(1);
ListNode n1 = new(3);
ListNode n2 = new(2);
ListNode n3 = new(5);
ListNode n4 = new(4);
// 構建節點之間的引用
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;

linked_list.go

/* 初始化鏈結串列 1 -> 3 -> 2 -> 5 -> 4 */
// 初始化各個節點
n0 := NewListNode(1)
n1 := NewListNode(3)
n2 := NewListNode(2)
n3 := NewListNode(5)
n4 := NewListNode(4)
// 構建節點之間的引用
n0.Next = n1
n1.Next = n2
n2.Next = n3
n3.Next = n4

linked_list.swift

/* 初始化鏈結串列 1 -> 3 -> 2 -> 5 -> 4 */
// 初始化各個節點
let n0 = ListNode(x: 1)
let n1 = ListNode(x: 3)
let n2 = ListNode(x: 2)
let n3 = ListNode(x: 5)
let n4 = ListNode(x: 4)
// 構建節點之間的引用
n0.next = n1
n1.next = n2
n2.next = n3
n3.next = n4

linked_list.js

/* 初始化鏈結串列 1 -> 3 -> 2 -> 5 -> 4 */
// 初始化各個節點
const n0 = new ListNode(1);
const n1 = new ListNode(3);
const n2 = new ListNode(2);
const n3 = new ListNode(5);
const n4 = new ListNode(4);
// 構建節點之間的引用
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;

linked_list.ts

/* 初始化鏈結串列 1 -> 3 -> 2 -> 5 -> 4 */
// 初始化各個節點
const n0 = new ListNode(1);
const n1 = new ListNode(3);
const n2 = new ListNode(2);
const n3 = new ListNode(5);
const n4 = new ListNode(4);
// 構建節點之間的引用
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;

linked_list.dart

/* 初始化鏈結串列 1 -> 3 -> 2 -> 5 -> 4 */\
// 初始化各個節點
ListNode n0 = ListNode(1);
ListNode n1 = ListNode(3);
ListNode n2 = ListNode(2);
ListNode n3 = ListNode(5);
ListNode n4 = ListNode(4);
// 構建節點之間的引用
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;

linked_list.rs

/* 初始化鏈結串列 1 -> 3 -> 2 -> 5 -> 4 */
// 初始化各個節點
let n0 = Rc::new(RefCell::new(ListNode { val: 1, next: None }));
let n1 = Rc::new(RefCell::new(ListNode { val: 3, next: None }));
let n2 = Rc::new(RefCell::new(ListNode { val: 2, next: None }));
let n3 = Rc::new(RefCell::new(ListNode { val: 5, next: None }));
let n4 = Rc::new(RefCell::new(ListNode { val: 4, next: None }));

// 構建節點之間的引用
n0.borrow_mut().next = Some(n1.clone());
n1.borrow_mut().next = Some(n2.clone());
n2.borrow_mut().next = Some(n3.clone());
n3.borrow_mut().next = Some(n4.clone());

linked_list.c

/* 初始化鏈結串列 1 -> 3 -> 2 -> 5 -> 4 */
// 初始化各個節點
ListNode* n0 = newListNode(1);
ListNode* n1 = newListNode(3);
ListNode* n2 = newListNode(2);
ListNode* n3 = newListNode(5);
ListNode* n4 = newListNode(4);
// 構建節點之間的引用
n0->next = n1;
n1->next = n2;
n2->next = n3;
n3->next = n4;

linked_list.kt

/* 初始化鏈結串列 1 -> 3 -> 2 -> 5 -> 4 */
// 初始化各個節點
val n0 = ListNode(1)
val n1 = ListNode(3)
val n2 = ListNode(2)
val n3 = ListNode(5)
val n4 = ListNode(4)
// 構建節點之間的引用
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;

linked_list.rb

# 初始化鏈結串列 1 -> 3 -> 2 -> 5 -> 4
# 初始化各個節點
n0 = ListNode.new(1)
n1 = ListNode.new(3)
n2 = ListNode.new(2)
n3 = ListNode.new(5)
n4 = ListNode.new(4)
# 構建節點之間的引用
n0.next = n1
n1.next = n2
n2.next = n3
n3.next = n4

linked_list.zig

// 初始化鏈結串列
// 初始化各個節點
var n0 = inc.ListNode(i32){.val = 1};
var n1 = inc.ListNode(i32){.val = 3};
var n2 = inc.ListNode(i32){.val = 2};
var n3 = inc.ListNode(i32){.val = 5};
var n4 = inc.ListNode(i32){.val = 4};
// 構建節點之間的引用
n0.next = &n1;
n1.next = &n2;
n2.next = &n3;
n3.next = &n4;

視覺化執行

全螢幕觀看 >

陣列整體是一個變數，比如陣列 nums 包含元素 nums[0] 和 nums[1] 等，而鏈結串列是由多個獨立的節點物件組成的。我們通常將頭節點當作鏈結串列的代稱，比如以上程式碼中的鏈結串列可記作鏈結串列 n0 。

2. 插入節點¶

在鏈結串列中插入節點非常容易。如圖 4-6 所示，假設我們想在相鄰的兩個節點 n0 和 n1 之間插入一個新節點 P ，則只需改變兩個節點引用（指標）即可，時間複雜度為 \(O(1)\) 。

相比之下，在陣列中插入元素的時間複雜度為 \(O(n)\) ，在大資料量下的效率較低。

圖 4-6 鏈結串列插入節點示例

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRubyZig

linked_list.py

def insert(n0: ListNode, P: ListNode):
    """在鏈結串列的節點 n0 之後插入節點 P"""
    n1 = n0.next
    P.next = n1
    n0.next = P

linked_list.cpp

/* 在鏈結串列的節點 n0 之後插入節點 P */
void insert(ListNode *n0, ListNode *P) {
    ListNode *n1 = n0->next;
    P->next = n1;
    n0->next = P;
}

linked_list.java

/* 在鏈結串列的節點 n0 之後插入節點 P */
void insert(ListNode n0, ListNode P) {
    ListNode n1 = n0.next;
    P.next = n1;
    n0.next = P;
}

linked_list.cs

/* 在鏈結串列的節點 n0 之後插入節點 P */
void Insert(ListNode n0, ListNode P) {
    ListNode? n1 = n0.next;
    P.next = n1;
    n0.next = P;
}

linked_list.go

/* 在鏈結串列的節點 n0 之後插入節點 P */
func insertNode(n0 *ListNode, P *ListNode) {
    n1 := n0.Next
    P.Next = n1
    n0.Next = P
}

linked_list.swift

/* 在鏈結串列的節點 n0 之後插入節點 P */
func insert(n0: ListNode, P: ListNode) {
    let n1 = n0.next
    P.next = n1
    n0.next = P
}

linked_list.js

/* 在鏈結串列的節點 n0 之後插入節點 P */
function insert(n0, P) {
    const n1 = n0.next;
    P.next = n1;
    n0.next = P;
}

linked_list.ts

/* 在鏈結串列的節點 n0 之後插入節點 P */
function insert(n0: ListNode, P: ListNode): void {
    const n1 = n0.next;
    P.next = n1;
    n0.next = P;
}

linked_list.dart

/* 在鏈結串列的節點 n0 之後插入節點 P */
void insert(ListNode n0, ListNode P) {
  ListNode? n1 = n0.next;
  P.next = n1;
  n0.next = P;
}

linked_list.rs

/* 在鏈結串列的節點 n0 之後插入節點 P */
#[allow(non_snake_case)]
pub fn insert<T>(n0: &Rc<RefCell<ListNode<T>>>, P: Rc<RefCell<ListNode<T>>>) {
    let n1 = n0.borrow_mut().next.take();
    P.borrow_mut().next = n1;
    n0.borrow_mut().next = Some(P);
}

linked_list.c

/* 在鏈結串列的節點 n0 之後插入節點 P */
void insert(ListNode *n0, ListNode *P) {
    ListNode *n1 = n0->next;
    P->next = n1;
    n0->next = P;
}

linked_list.kt

/* 在鏈結串列的節點 n0 之後插入節點 P */
fun insert(n0: ListNode?, p: ListNode?) {
    val n1 = n0?.next
    p?.next = n1
    n0?.next = p
}

linked_list.rb

### 在鏈結串列的節點 n0 之後插入節點 _p ###
# Ruby 的 `p` 是一個內建函式， `P` 是一個常數，所以可以使用 `_p` 代替
def insert(n0, _p)
  n1 = n0.next
  _p.next = n1
  n0.next = _p
end

linked_list.zig

// 在鏈結串列的節點 n0 之後插入節點 P
fn insert(n0: ?*inc.ListNode(i32), P: ?*inc.ListNode(i32)) void {
    var n1 = n0.?.next;
    P.?.next = n1;
    n0.?.next = P;
}

視覺化執行

全螢幕觀看 >

3. 刪除節點¶

如圖 4-7 所示，在鏈結串列中刪除節點也非常方便，只需改變一個節點的引用（指標）即可。

請注意，儘管在刪除操作完成後節點 P 仍然指向 n1 ，但實際上走訪此鏈結串列已經無法訪問到 P ，這意味著 P 已經不再屬於該鏈結串列了。

圖 4-7 鏈結串列刪除節點

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRubyZig

linked_list.py

def remove(n0: ListNode):
    """刪除鏈結串列的節點 n0 之後的首個節點"""
    if not n0.next:
        return
    # n0 -> P -> n1
    P = n0.next
    n1 = P.next
    n0.next = n1

linked_list.cpp

/* 刪除鏈結串列的節點 n0 之後的首個節點 */
void remove(ListNode *n0) {
    if (n0->next == nullptr)
        return;
    // n0 -> P -> n1
    ListNode *P = n0->next;
    ListNode *n1 = P->next;
    n0->next = n1;
    // 釋放記憶體
    delete P;
}

linked_list.java

/* 刪除鏈結串列的節點 n0 之後的首個節點 */
void remove(ListNode n0) {
    if (n0.next == null)
        return;
    // n0 -> P -> n1
    ListNode P = n0.next;
    ListNode n1 = P.next;
    n0.next = n1;
}

linked_list.cs

/* 刪除鏈結串列的節點 n0 之後的首個節點 */
void Remove(ListNode n0) {
    if (n0.next == null)
        return;
    // n0 -> P -> n1
    ListNode P = n0.next;
    ListNode? n1 = P.next;
    n0.next = n1;
}

linked_list.go

/* 刪除鏈結串列的節點 n0 之後的首個節點 */
func removeItem(n0 *ListNode) {
    if n0.Next == nil {
        return
    }
    // n0 -> P -> n1
    P := n0.Next
    n1 := P.Next
    n0.Next = n1
}

linked_list.swift

/* 刪除鏈結串列的節點 n0 之後的首個節點 */
func remove(n0: ListNode) {
    if n0.next == nil {
        return
    }
    // n0 -> P -> n1
    let P = n0.next
    let n1 = P?.next
    n0.next = n1
}

linked_list.js

/* 刪除鏈結串列的節點 n0 之後的首個節點 */
function remove(n0) {
    if (!n0.next) return;
    // n0 -> P -> n1
    const P = n0.next;
    const n1 = P.next;
    n0.next = n1;
}

linked_list.ts

/* 刪除鏈結串列的節點 n0 之後的首個節點 */
function remove(n0: ListNode): void {
    if (!n0.next) {
        return;
    }
    // n0 -> P -> n1
    const P = n0.next;
    const n1 = P.next;
    n0.next = n1;
}

linked_list.dart

/* 刪除鏈結串列的節點 n0 之後的首個節點 */
void remove(ListNode n0) {
  if (n0.next == null) return;
  // n0 -> P -> n1
  ListNode P = n0.next!;
  ListNode? n1 = P.next;
  n0.next = n1;
}

linked_list.rs

/* 刪除鏈結串列的節點 n0 之後的首個節點 */
#[allow(non_snake_case)]
pub fn remove<T>(n0: &Rc<RefCell<ListNode<T>>>) {
    if n0.borrow().next.is_none() {
        return;
    };
    // n0 -> P -> n1
    let P = n0.borrow_mut().next.take();
    if let Some(node) = P {
        let n1 = node.borrow_mut().next.take();
        n0.borrow_mut().next = n1;
    }
}

linked_list.c

/* 刪除鏈結串列的節點 n0 之後的首個節點 */
// 注意：stdio.h 佔用了 remove 關鍵詞
void removeItem(ListNode *n0) {
    if (!n0->next)
        return;
    // n0 -> P -> n1
    ListNode *P = n0->next;
    ListNode *n1 = P->next;
    n0->next = n1;
    // 釋放記憶體
    free(P);
}

linked_list.kt

/* 刪除鏈結串列的節點 n0 之後的首個節點 */
fun remove(n0: ListNode?) {
    if (n0?.next == null)
        return
    // n0 -> P -> n1
    val p = n0.next
    val n1 = p?.next
    n0.next = n1
}

linked_list.rb

### 刪除鏈結串列的節點 n0 之後的首個節點 ###
def remove(n0)
  return if n0.next.nil?

  # n0 -> remove_node -> n1
  remove_node = n0.next
  n1 = remove_node.next
  n0.next = n1
end

linked_list.zig

// 刪除鏈結串列的節點 n0 之後的首個節點
fn remove(n0: ?*inc.ListNode(i32)) void {
    if (n0.?.next == null) return;
    // n0 -> P -> n1
    var P = n0.?.next;
    var n1 = P.?.next;
    n0.?.next = n1;
}

視覺化執行

全螢幕觀看 >

4. 訪問節點¶

在鏈結串列中訪問節點的效率較低。如上一節所述，我們可以在 \(O(1)\) 時間下訪問陣列中的任意元素。鏈結串列則不然，程式需要從頭節點出發，逐個向後走訪，直至找到目標節點。也就是說，訪問鏈結串列的第 \(i\) 個節點需要迴圈 \(i - 1\) 輪，時間複雜度為 \(O(n)\) 。

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRubyZig

linked_list.py

def access(head: ListNode, index: int) -> ListNode | None:
    """訪問鏈結串列中索引為 index 的節點"""
    for _ in range(index):
        if not head:
            return None
        head = head.next
    return head

linked_list.cpp

/* 訪問鏈結串列中索引為 index 的節點 */
ListNode *access(ListNode *head, int index) {
    for (int i = 0; i < index; i++) {
        if (head == nullptr)
            return nullptr;
        head = head->next;
    }
    return head;
}

linked_list.java

/* 訪問鏈結串列中索引為 index 的節點 */
ListNode access(ListNode head, int index) {
    for (int i = 0; i < index; i++) {
        if (head == null)
            return null;
        head = head.next;
    }
    return head;
}

linked_list.cs

/* 訪問鏈結串列中索引為 index 的節點 */
ListNode? Access(ListNode? head, int index) {
    for (int i = 0; i < index; i++) {
        if (head == null)
            return null;
        head = head.next;
    }
    return head;
}

linked_list.go

/* 訪問鏈結串列中索引為 index 的節點 */
func access(head *ListNode, index int) *ListNode {
    for i := 0; i < index; i++ {
        if head == nil {
            return nil
        }
        head = head.Next
    }
    return head
}

linked_list.swift

/* 訪問鏈結串列中索引為 index 的節點 */
func access(head: ListNode, index: Int) -> ListNode? {
    var head: ListNode? = head
    for _ in 0 ..< index {
        if head == nil {
            return nil
        }
        head = head?.next
    }
    return head
}

linked_list.js

/* 訪問鏈結串列中索引為 index 的節點 */
function access(head, index) {
    for (let i = 0; i < index; i++) {
        if (!head) {
            return null;
        }
        head = head.next;
    }
    return head;
}

linked_list.ts

/* 訪問鏈結串列中索引為 index 的節點 */
function access(head: ListNode | null, index: number): ListNode | null {
    for (let i = 0; i < index; i++) {
        if (!head) {
            return null;
        }
        head = head.next;
    }
    return head;
}

linked_list.dart

/* 訪問鏈結串列中索引為 index 的節點 */
ListNode? access(ListNode? head, int index) {
  for (var i = 0; i < index; i++) {
    if (head == null) return null;
    head = head.next;
  }
  return head;
}

linked_list.rs

/* 訪問鏈結串列中索引為 index 的節點 */
pub fn access<T>(head: Rc<RefCell<ListNode<T>>>, index: i32) -> Rc<RefCell<ListNode<T>>> {
    if index <= 0 {
        return head;
    };
    if let Some(node) = &head.borrow().next {
        return access(node.clone(), index - 1);
    }

    return head;
}

linked_list.c

/* 訪問鏈結串列中索引為 index 的節點 */
ListNode *access(ListNode *head, int index) {
    for (int i = 0; i < index; i++) {
        if (head == NULL)
            return NULL;
        head = head->next;
    }
    return head;
}

linked_list.kt

/* 訪問鏈結串列中索引為 index 的節點 */
fun access(head: ListNode?, index: Int): ListNode? {
    var h = head
    for (i in 0..<index) {
        if (h == null)
            return null
        h = h.next
    }
    return h
}

linked_list.rb

### 訪問鏈結串列中索引為 index 的節點 ###
def access(head, index)
  for i in 0...index
    return nil if head.nil?
    head = head.next
  end

  head
end

linked_list.zig

// 訪問鏈結串列中索引為 index 的節點
fn access(node: ?*inc.ListNode(i32), index: i32) ?*inc.ListNode(i32) {
    var head = node;
    var i: i32 = 0;
    while (i < index) : (i += 1) {
        head = head.?.next;
        if (head == null) return null;
    }
    return head;
}

視覺化執行

全螢幕觀看 >

5. 查詢節點¶

走訪鏈結串列，查詢其中值為 target 的節點，輸出該節點在鏈結串列中的索引。此過程也屬於線性查詢。程式碼如下所示：

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRubyZig

linked_list.py

def find(head: ListNode, target: int) -> int:
    """在鏈結串列中查詢值為 target 的首個節點"""
    index = 0
    while head:
        if head.val == target:
            return index
        head = head.next
        index += 1
    return -1

linked_list.cpp

/* 在鏈結串列中查詢值為 target 的首個節點 */
int find(ListNode *head, int target) {
    int index = 0;
    while (head != nullptr) {
        if (head->val == target)
            return index;
        head = head->next;
        index++;
    }
    return -1;
}

linked_list.java

/* 在鏈結串列中查詢值為 target 的首個節點 */
int find(ListNode head, int target) {
    int index = 0;
    while (head != null) {
        if (head.val == target)
            return index;
        head = head.next;
        index++;
    }
    return -1;
}

linked_list.cs

/* 在鏈結串列中查詢值為 target 的首個節點 */
int Find(ListNode? head, int target) {
    int index = 0;
    while (head != null) {
        if (head.val == target)
            return index;
        head = head.next;
        index++;
    }
    return -1;
}

linked_list.go

/* 在鏈結串列中查詢值為 target 的首個節點 */
func findNode(head *ListNode, target int) int {
    index := 0
    for head != nil {
        if head.Val == target {
            return index
        }
        head = head.Next
        index++
    }
    return -1
}

linked_list.swift

/* 在鏈結串列中查詢值為 target 的首個節點 */
func find(head: ListNode, target: Int) -> Int {
    var head: ListNode? = head
    var index = 0
    while head != nil {
        if head?.val == target {
            return index
        }
        head = head?.next
        index += 1
    }
    return -1
}

linked_list.js

/* 在鏈結串列中查詢值為 target 的首個節點 */
function find(head, target) {
    let index = 0;
    while (head !== null) {
        if (head.val === target) {
            return index;
        }
        head = head.next;
        index += 1;
    }
    return -1;
}

linked_list.ts

/* 在鏈結串列中查詢值為 target 的首個節點 */
function find(head: ListNode | null, target: number): number {
    let index = 0;
    while (head !== null) {
        if (head.val === target) {
            return index;
        }
        head = head.next;
        index += 1;
    }
    return -1;
}

linked_list.dart

/* 在鏈結串列中查詢值為 target 的首個節點 */
int find(ListNode? head, int target) {
  int index = 0;
  while (head != null) {
    if (head.val == target) {
      return index;
    }
    head = head.next;
    index++;
  }
  return -1;
}

linked_list.rs

/* 在鏈結串列中查詢值為 target 的首個節點 */
pub fn find<T: PartialEq>(head: Rc<RefCell<ListNode<T>>>, target: T, index: i32) -> i32 {
    if head.borrow().val == target {
        return index;
    };
    if let Some(node) = &head.borrow_mut().next {
        return find(node.clone(), target, index + 1);
    }
    return -1;
}

linked_list.c

/* 在鏈結串列中查詢值為 target 的首個節點 */
int find(ListNode *head, int target) {
    int index = 0;
    while (head) {
        if (head->val == target)
            return index;
        head = head->next;
        index++;
    }
    return -1;
}

linked_list.kt

/* 在鏈結串列中查詢值為 target 的首個節點 */
fun find(head: ListNode?, target: Int): Int {
    var index = 0
    var h = head
    while (h != null) {
        if (h._val == target)
            return index
        h = h.next
        index++
    }
    return -1
}

linked_list.rb

### 在鏈結串列中查詢值為 target 的首個節點 ###
def find(head, target)
  index = 0
  while head
    return index if head.val == target
    head = head.next
    index += 1
  end

  -1
end

linked_list.zig

// 在鏈結串列中查詢值為 target 的首個節點
fn find(node: ?*inc.ListNode(i32), target: i32) i32 {
    var head = node;
    var index: i32 = 0;
    while (head != null) {
        if (head.?.val == target) return index;
        head = head.?.next;
        index += 1;
    }
    return -1;
}

視覺化執行

全螢幕觀看 >

4.2.2 陣列 vs. 鏈結串列¶

表 4-1 總結了陣列和鏈結串列的各項特點並對比了操作效率。由於它們採用兩種相反的儲存策略，因此各種性質和操作效率也呈現對立的特點。

表 4-1 陣列與鏈結串列的效率對比

	陣列	鏈結串列
儲存方式	連續記憶體空間	分散記憶體空間
容量擴展	長度不可變	可靈活擴展
記憶體效率	元素佔用記憶體少、但可能浪費空間	元素佔用記憶體多
訪問元素	\(O(1)\)	\(O(n)\)
新增元素	\(O(n)\)	\(O(1)\)
刪除元素	\(O(n)\)	\(O(1)\)

4.2.3 常見鏈結串列型別¶

如圖 4-8 所示，常見的鏈結串列型別包括三種。

單向鏈結串列：即前面介紹的普通鏈結串列。單向鏈結串列的節點包含值和指向下一節點的引用兩項資料。我們將首個節點稱為頭節點，將最後一個節點稱為尾節點，尾節點指向空 None 。
環形鏈結串列：如果我們令單向鏈結串列的尾節點指向頭節點（首尾相接），則得到一個環形鏈結串列。在環形鏈結串列中，任意節點都可以視作頭節點。
雙向鏈結串列：與單向鏈結串列相比，雙向鏈結串列記錄了兩個方向的引用。雙向鏈結串列的節點定義同時包含指向後繼節點（下一個節點）和前驅節點（上一個節點）的引用（指標）。相較於單向鏈結串列，雙向鏈結串列更具靈活性，可以朝兩個方向走訪鏈結串列，但相應地也需要佔用更多的記憶體空間。

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRubyZig

class ListNode:
    """雙向鏈結串列節點類別"""
    def __init__(self, val: int):
        self.val: int = val                # 節點值
        self.next: ListNode | None = None  # 指向後繼節點的引用
        self.prev: ListNode | None = None  # 指向前驅節點的引用

/* 雙向鏈結串列節點結構體 */
struct ListNode {
    int val;         // 節點值
    ListNode *next;  // 指向後繼節點的指標
    ListNode *prev;  // 指向前驅節點的指標
    ListNode(int x) : val(x), next(nullptr), prev(nullptr) {}  // 建構子
};

/* 雙向鏈結串列節點類別 */
class ListNode {
    int val;        // 節點值
    ListNode next;  // 指向後繼節點的引用
    ListNode prev;  // 指向前驅節點的引用
    ListNode(int x) { val = x; }  // 建構子
}

/* 雙向鏈結串列節點類別 */
class ListNode(int x) {  // 建構子
    int val = x;    // 節點值
    ListNode next;  // 指向後繼節點的引用
    ListNode prev;  // 指向前驅節點的引用
}

/* 雙向鏈結串列節點結構體 */
type DoublyListNode struct {
    Val  int             // 節點值
    Next *DoublyListNode // 指向後繼節點的指標
    Prev *DoublyListNode // 指向前驅節點的指標
}

// NewDoublyListNode 初始化
func NewDoublyListNode(val int) *DoublyListNode {
    return &DoublyListNode{
        Val:  val,
        Next: nil,
        Prev: nil,
    }
}

/* 雙向鏈結串列節點類別 */
class ListNode {
    var val: Int // 節點值
    var next: ListNode? // 指向後繼節點的引用
    var prev: ListNode? // 指向前驅節點的引用

    init(x: Int) { // 建構子
        val = x
    }
}

/* 雙向鏈結串列節點類別 */
class ListNode {
    constructor(val, next, prev) {
        this.val = val  ===  undefined ? 0 : val;        // 節點值
        this.next = next  ===  undefined ? null : next;  // 指向後繼節點的引用
        this.prev = prev  ===  undefined ? null : prev;  // 指向前驅節點的引用
    }
}

/* 雙向鏈結串列節點類別 */
class ListNode {
    val: number;
    next: ListNode | null;
    prev: ListNode | null;
    constructor(val?: number, next?: ListNode | null, prev?: ListNode | null) {
        this.val = val  ===  undefined ? 0 : val;        // 節點值
        this.next = next  ===  undefined ? null : next;  // 指向後繼節點的引用
        this.prev = prev  ===  undefined ? null : prev;  // 指向前驅節點的引用
    }
}

/* 雙向鏈結串列節點類別 */
class ListNode {
    int val;        // 節點值
    ListNode? next;  // 指向後繼節點的引用
    ListNode? prev;  // 指向前驅節點的引用
    ListNode(this.val, [this.next, this.prev]);  // 建構子
}

use std::rc::Rc;
use std::cell::RefCell;

/* 雙向鏈結串列節點型別 */
#[derive(Debug)]
struct ListNode {
    val: i32, // 節點值
    next: Option<Rc<RefCell<ListNode>>>, // 指向後繼節點的指標
    prev: Option<Rc<RefCell<ListNode>>>, // 指向前驅節點的指標
}

/* 建構子 */
impl ListNode {
    fn new(val: i32) -> Self {
        ListNode {
            val,
            next: None,
            prev: None,
        }
    }
}

/* 雙向鏈結串列節點結構體 */
typedef struct ListNode {
    int val;               // 節點值
    struct ListNode *next; // 指向後繼節點的指標
    struct ListNode *prev; // 指向前驅節點的指標
} ListNode;

/* 建構子 */
ListNode *newListNode(int val) {
    ListNode *node;
    node = (ListNode *) malloc(sizeof(ListNode));
    node->val = val;
    node->next = NULL;
    node->prev = NULL;
    return node;
}

/* 雙向鏈結串列節點類別 */
// 建構子
class ListNode(x: Int) {
    val _val: Int = x           // 節點值
    val next: ListNode? = null  // 指向後繼節點的引用
    val prev: ListNode? = null  // 指向前驅節點的引用
}

# 雙向鏈結串列節點類別
class ListNode
  attr_accessor :val    # 節點值
  attr_accessor :next   # 指向後繼節點的引用
  attr_accessor :prev   # 指向前驅節點的引用

  def initialize(val=0, next_node=nil, prev_node=nil)
    @val = val
    @next = next_node
    @prev = prev_node
  end
end

// 雙向鏈結串列節點類別
pub fn ListNode(comptime T: type) type {
    return struct {
        const Self = @This();

        val: T = 0, // 節點值
        next: ?*Self = null, // 指向後繼節點的指標
        prev: ?*Self = null, // 指向前驅節點的指標

        // 建構子
        pub fn init(self: *Self, x: i32) void {
            self.val = x;
            self.next = null;
            self.prev = null;
        }
    };
}

圖 4-8 常見鏈結串列種類

4.2.4 鏈結串列典型應用¶

單向鏈結串列通常用於實現堆疊、佇列、雜湊表和圖等資料結構。

堆疊與佇列：當插入和刪除操作都在鏈結串列的一端進行時，它表現的特性為先進後出，對應堆疊；當插入操作在鏈結串列的一端進行，刪除操作在鏈結串列的另一端進行，它表現的特性為先進先出，對應佇列。
雜湊表：鏈式位址是解決雜湊衝突的主流方案之一，在該方案中，所有衝突的元素都會被放到一個鏈結串列中。
圖：鄰接表是表示圖的一種常用方式，其中圖的每個頂點都與一個鏈結串列相關聯，鏈結串列中的每個元素都代表與該頂點相連的其他頂點。

雙向鏈結串列常用於需要快速查詢前一個和後一個元素的場景。

高階資料結構：比如在紅黑樹、B 樹中，我們需要訪問節點的父節點，這可以透過在節點中儲存一個指向父節點的引用來實現，類似於雙向鏈結串列。
瀏覽器歷史：在網頁瀏覽器中，當用戶點選前進或後退按鈕時，瀏覽器需要知道使用者訪問過的前一個和後一個網頁。雙向鏈結串列的特性使得這種操作變得簡單。
LRU 演算法：在快取淘汰（LRU）演算法中，我們需要快速找到最近最少使用的資料，以及支持快速新增和刪除節點。這時候使用雙向鏈結串列就非常合適。

環形鏈結串列常用於需要週期性操作的場景，比如作業系統的資源排程。

時間片輪轉排程演算法：在作業系統中，時間片輪轉排程演算法是一種常見的 CPU 排程演算法，它需要對一組程序進行迴圈。每個程序被賦予一個時間片，當時間片用完時，CPU 將切換到下一個程序。這種迴圈操作可以透過環形鏈結串列來實現。
資料緩衝區：在某些資料緩衝區的實現中，也可能會使用環形鏈結串列。比如在音訊、影片播放器中，資料流可能會被分成多個緩衝塊並放入一個環形鏈結串列，以便實現無縫播放。