使用 Python 學習資料結構（二）：鏈表

Data Structures
, ,

前言

本文為〈資料結構與演算法〉一文的學習筆記。

鏈表

鏈表或連結串列（Linked list），是一種常見的基礎資料結構。鏈表是一種線性表，但是並不會按線性的順序儲存資料，而是在每一個節點裡儲存下一個節點的指標（Pointer）。

鏈表的基本要素：

  • 節點：又稱元素，每一個節點有兩個域，左邊儲存節點的値，右邊儲存下一個節點的指標。
  • Head 節點：永遠指向第一個節點。
  • Tail 節點：永遠指向最後一個節點。
  • None：又稱接地點，是被 Tail 節點指向的 None 値。

鏈表的常用函式：

  • is_empty()，檢查鏈表是否為空。
  • append(data)，在尾部增加一個節點，參數為要增加節點的値。
  • iter()，疊代鏈表，此方法一般是一個產成器。
  • insert(idx, value)，插入一個節點，參數為要插入節點的索引和値。
  • remove(idx)，移除節點，參數為要移除節點的索引。
  • size()，獲取鏈表的節點個數。
  • search(item)，查找節點，參數為要查找節點的値或索引。

函數實作

節點類別

一個 Node 類別的建構函式如下：

1
2
3
4
>>> class Node(object):
        def __init__(self, data):
            self.data = data
            self.next = None

實例化一個節點類別。

1
2
3
>>> node = Node(4)
    node.data
4

鏈表類別

一個 LinkedList 類別的建構函式如下：

1
2
3
4
>>> class LinkedList(object):
        def __init__(self):
            self.head = None
            self.tail = None

實例化一個鏈表類別。

1
>>> link_list = LinkedList()

檢查鏈表是否為空

在 LinkedList 類別建立一個 is_empty() 函式，以檢查鏈表是否為空。

1
2
3
>>> def is_empty(self):
        # 如果 head 節點為空，則返回 True
        return self.head is None

檢查鏈表是否為空。

1
2
3
>>> link_list = LinkedList()
    link_list.is_empty()
True

增加節點

在 LinkedList 類別建立一個 append() 函式，以在鏈表尾部增加一個節點。

1
2
3
4
5
6
7
8
9
10
11
>>> def append(self, data):
        # 實例化一個新節點
        node = Node(data)
        # 如果 head 節點為空，將 head 節點和 tail 節點指向新節點
        if self.head is None:
            self.head = node
            self.tail = node
        # 否則將最後一個節點的 next 和 tail 節點設為新節點
        else:
            self.tail.next = node
            self.tail = node

新增一個節點。

1
2
3
4
5
6
7
>>> link_list.append(4)
>>> print(link_list.head)
    print(link_list.head.data)
    print(link_list.head.next)
<__main__.Node object at 0x000001FE0C61C0F0>
4
None

新增第二個節點。

1
2
3
4
5
6
7
8
9
10
11
12
13
>>> link_list.append(5)
>>> print(link_list.head)
    print(link_list.head.data)
    print(link_list.head.next)
    print(link_list.tail)
    print(link_list.tail.data)
    print(link_list.tail.next)
<__main__.Node object at 0x000001FE0C61C0F0>
4
<__main__.Node object at 0x000001FE0C613E80>
<__main__.Node object at 0x000001FE0C613E80>
5
None

產生器

在 LinkedList 類別建立一個 iter() 函式，以疊代鏈表的所有節點。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
>>> def iter(self):
        # 如果 head 節點為 None（形成 not False），則直接返回 None
        if not self.head:
            return
        # 將 cur 設為 head 節點
        cur = self.head
        # 產生第一個節點的値
        yield cur.data
        # 直到 cur 的 next 指向 None 値
        while cur.next is not None:
            # 將 cur 設為下一個節點
            cur = cur.next
            # 產生下一個節點的値
            yield cur.data

使用產生器疊代鏈表的所有節點。

1
2
3
4
>>> for i in link_list.iter():
        print(i)
4
5

插入節點

在 LinkedList 類別建立一個 insert() 函式，以在指定索引插入一個節點。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
>>> def insert(self, idx, value):
        cur = self.head
        cur_idx = 0
        # 如果 head 節點為空，則抛出例外
        if cur is None:
            raise Exception('串列為空')
        # 從 0 開始疊代到指定索引 - 1
        while cur_idx < idx - 1:
            # 指定索引的前一個節點
            cur = cur.next
            # 如果指定索引的前一個節點的 next 為空，則抛出例外
            if cur.next is None:
                raise Exception('索引超過範圍')
            # 每一次疊代都把 cur_idx 加上 1
            cur_idx += 1
        # 實例化一個新節點
        node = Node(value)
        # 將新節點的 next 指向指定索引的前一個節點的 next
        node.next = cur.next
        # 將指定索引的前一個節點指向新節點
        cur.next = node
        # 如果新節點的 next 為空，則將 tail 節點指向新節點
        if node.next is None:
            self.tail = node
  • 程式碼第 12 列改判斷 cur.next 是否為空。

插入一個節點。

1
2
3
4
5
6
>>> link_list.insert(1, 9)
>>> for i in link_list.iter():
        print(i)
4
9
5
  • 此處設定為不可在第一個節點前插入，也不可在最後一個節點後插入。

刪除節點

在 LinkedList 類別建立一個 remove() 函式，以在指定索引刪除節點。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
>>> def remove(self, idx):
        cur = self.head
        cur_idx = 0
        # 如果 head 節點為空，則抛出例外
        if cur is None:
            raise Exception('串列為空')
        # 從 0 開始疊代到指定索引 - 1
        while cur_idx < idx - 1:
            # 指定索引的前一個節點
            cur = cur.next
            # 如果指定索引的前一個節點的 next 為空，則抛出例外
            if cur.next is None:
                raise Exception('索引超過範圍')
            # 每一次疊代都把 cur_idx 加上 1
            cur_idx += 1
        # 如果刪除的節點為第一個，則將 head 節點和 cur 指向原來 head 節點的 next
        if idx == 0:
            self.head = cur.next
            cur = cur.next
            # 不再往下執行
            return
        # 如果鏈表只有一個節點，則將 head 節點和 tail 節點都設為空
        if self.head is self.tail:
            self.head = None
            self.tail = None
            # 不再往下執行
            return
        # 將指定索引的前一個節點的 next 指向下一個節點的 next
        cur.next = cur.next.next
        # 如果刪除的節點為最後一個，則將 tail 節點指向 cur
        if cur.next is None:
            self.tail = cur
  • 程式碼第 12 列改判斷 cur.next 是否為空。

刪除一個節點。

1
2
3
4
5
>>> link_list.remove(1)
>>> for i in link_list.iter():
        print(i)
4
5

獲取節點個數

在 LinkedList 類別建立一個 size() 函式，以獲取鏈表的節點個數。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
>>> def size(self):
        cur = self.head
        count = 0
        # 如果 head 節點為空，則返回字串
        if cur is None:
            return '串列為空'
        # 直到 cur 為 None 値
        while cur is not None:
            # 將 cur 設為下一個節點
            cur = cur.next
            # 每一次疊代都把 count 加上 1
            count += 1
        # 返回個數
        return count

獲取鏈表的節點個數。

1
2
>>> link_list.size()
1

查找節點

在 LinkedList 類別建立一個 search() 函式，以查找指定値。

1
2
3
4
5
6
7
8
9
10
11
12
13
>>> def search(self, item):
        cur = self.head
        found = False
        # 直到 cur 的 next 指向 None 値或 found 是 Ture
        while cur is not None and not found:
            # 如果 cur 的値是指定値，則 found 是 True（停止疊代）
            if cur.data == item:
                found = True
            # 否則將 cur 設為下一個節點（繼續疊代）
            else:
                cur = cur.next
        # 返回布林値
        return found

獲得鏈表的節點個數。

1
2
>>> link_list.search(5)
True

程式碼

參考資料