1.Linked_List.md

Linked List 是一種基本的資料結構,由一系列節點(Node)組成,每個節點包含資料與指向下一個節點的指標(pointer)。


一、鍊結串列的分類

類型
描述

單向鍊結串列

每個節點只指向下一個節點

雙向鍊結串列

每個節點有前後兩個指標

循環鍊結串列

最後一個節點指回第一個節點

雙向循環鍊結串列

同時具備雙向與循環特性


二、基本節點結構(Python 範例)

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

三、單向鍊結串列操作

1. 建立鏈表與新增節點

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, value):
        new_node = Node(value)
        if not self.head:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

2. 顯示所有節點

    def display(self):
        current = self.head
        while current:
            print(current.value, end=" → ")
            current = current.next
        print("None")

3. 插入、刪除、搜尋

    def insert(self, index, value):
        new_node = Node(value)
        if index == 0:
            new_node.next = self.head
            self.head = new_node
            return
        current = self.head
        for _ in range(index - 1):
            if current:
                current = current.next
        new_node.next = current.next
        current.next = new_node

    def delete(self, value):
        current = self.head
        if current and current.value == value:
            self.head = current.next
            return
        while current.next:
            if current.next.value == value:
                current.next = current.next.next
                return
            current = current.next

    def search(self, value):
        current = self.head
        while current:
            if current.value == value:
                return True
            current = current.next
        return False

四、Linked List 特性

  • 插入與刪除快:操作不需移動其他元素

  • 隨機訪問慢:需從頭開始搜尋

  • 動態長度:不需預先分配空間


五、Linked List vs Array 比較

特性
Linked List
Array(List)

記憶體配置

分散

連續

訪問速度

O(n)

O(1)

插入刪除

O(1)(已知位置)

O(n)

空間效率

多一點指標空間

純資料


Linked List 是所有資料結構的基礎之一,尤其適合插入與刪除操作頻繁的場景,例如實作 queue、stack、hash table 或圖結構等。

Last updated