• Data Structures 資料結構：從 Array 到 Linked List、Tree、Graph 的核心概念

參考書籍

參考網站

NTNU

VISUALGO

Leetcode 學習 探索知識地圖

什麼是Data Structure資料結構?

也有人叫數據結構
ADT（Abstract Data Type，抽象資料類型）是一種用來描述資料結構的數學模型，強調資料的邏輯結構而不是具體的實現方式

資料結構是一種組織和存儲資料的方式，結構的設計取決於不同的應用需求

基本資料結構： 包括陣列、鏈結串列、堆疊、佇列等

複雜資料結構： 包括樹、圖、散列表等，通常用於解決複雜的問題，提高效率

資料結構

set集合: 無順序，類型無限制

list(線性)列表: 有索引，有順序，類型無限制，python長度可變

tuple元組: 有索引，有順序，類型無限制，長度不可變

array數組: 有索引，有順序，類型相同，長度不可變

Array數組/List列表/Tuple元組 O(1),O(n)

在Python中，資料結構沒有Array數組，比較接近list，可以增加、減少。但在C語言中，數組一開始要指定大小，若要更動，只能開一個新的數組複製過去

# array/list  O(1)

list1 = [1,2,3,4,5,6]
print(list1[0])

list2 = [[1,2,3,4,5,6],[7,8,9,10,11,12]]
print(list2[1][4])

# 增加數據 O(1)

list1.append(9)
print(list)

list2[0].extend([7, 8])
list2[1].extend([13, 14])
print(list2)

# 隨機增加數據 O(1)末尾,O(n)
import random

random_index = random.randint(0, len(list1))
list1.insert(random_index, 10)
print(list1)

random_index1 = random.randint(0, len(list2)-1)
random_index2 = random.randint(0, len(list2[random_index1])-1)
list2[random_index1].insert(random_index2, 15)
print(list2)

# .extend() 是列表方法，用來將另一個序列中的元素逐個添加到列表末尾 O(k), k為list02的長度

list01 = [1, 2, 3]
list02 = [4, 5, 6]

list01.extend(list02)
print(list01)

# 刪除數據 O(1)末尾,O(n)

list1.remove(10)
print(list1)


list2[1].remove(10)
print(list2)

# 反轉 O(n/2) = O(n)
from typing import List


# way1
def reverse_array(list1):
    start = 0
    end = len(list1) - 1

    while start < end:
        list1[start], list1[end] = list1[end], list1[start]
        start += 1
        end -= 1
    return list1

# way2
def reverse_array_pythonic(list1):
    return list1[::-1]


if __name__ == "__main__":
    list1 = [1, 3, 5, 7, 11, 10]
    print(reverse_array(list1))
    print(reverse_array_pythonic(list1))

# palindrome 迴文 O(n)

def is_palindrome(s):
    start_index = 0
    end_index = len(s) - 1

    while start_index < end_index:
        if s[start_index] != s[end_index]:
            return False
        start_index += 1
        end_index -= 1
    return True


def is_palindrome_pythonic(s):
    return s == s[::-1]


s = "ABCBA"
print(is_palindrome(s))
print(is_palindrome_pythonic(s))


# JS 寫法
# function isPalindrome(string) {
#   return string === string.split('').reverse().join('');
#  }

tuple

tuple元組，是不可變的，所以無法添加或刪除元素，但可以創建一個新的元組

# tuple
# 增加數據

my_tuple = (1, 2, 3)

new_tuple = my_tuple + (4,)
new_tuple

my_tuple = (1, "apple", 3.14)

first_element = my_tuple[0]
partial_tuple = my_tuple[1:]
print("First Element:", first_element)
print("Partial Tuple:", partial_tuple)

指定位置插入，可以先轉換為list，插入值後再轉回tuple

# 指定位置插入，可以先轉換為list，插入值後再轉回tuple

my_tuple = (1, "apple", 3.14)

tuple_list = list(my_tuple)
tuple_list.insert(2, 10)
my_tuple = tuple(tuple_list)
print("Tuple:", my_tuple)

tuple元組，是不可變的，所以無法添加或刪除元素，但可以創建一個新的元組

# tuple元組，是不可變的，所以無法添加或刪除元素，但可以創建一個新的元組

my_tuple = (1, 2, 3)

new_tuple = tuple(t for t in my_tuple if t != 2)
new_tuple

指定位置刪除，可以先轉換為list，插入值後再轉回

# 指定位置刪除，可以先轉換為list，插入值後再轉回

my_tuple = (1, 10, "apple", 3.14)

tuple_list = list(my_tuple)
del tuple_list[1]
my_tuple = tuple(tuple_list)

print("Tuple:", my_tuple)

反轉，可以先轉換為list，反轉後再轉回

# 反轉，可以先轉換為list，反轉後再轉回

my_tuple = (1, 10, "apple", 3.14)

tuple_list = list(my_tuple)
tuple_list = reverse_array_pythonic(tuple_list)
my_tuple = tuple(tuple_list)

print("Reverse Tuple:", my_tuple)

Linked List 鏈結串列

Linked List長度可以增加、刪除，分為單向和雙向，數據節點稱為Node，單向只會指向下一個Node，雙向會指向前一個和下一個Node。頭部Node稱為”head”,尾部Node稱為”tail”

Singly Linked List

# single linked lists
# 知道tail情況下

class Node:
    def __init__(self, data) -> None::
        self.data = data
        self.next = None

if __name__ == "__main__":
    head = Node(data=1)
    tail = head
    node1 =Node(data=2)
    tail = node1
    node2 =Node(data=3)

    head.next = node1
    node1.next = node2
    tail = node2

class Node:
    def __init__(self, data) -> None:
        self.data = data
        self.next = None

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

    # 末尾插入 O(1)知道尾部, 不知道尾部、任意位置O(n)
    def append(self, value):
        new_node = Node(value)
        if self.head == None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node

    # 頭部插入 O(1)
    def prepend(self, value):
        new_node = Node(value)
        if self.head == None:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head = new_node

    # 印出
    def print_list(self):
        tmp = self.head
        while tmp:
            print(tmp.data, end=" ")
            tmp = tmp.next
            if tmp:
                print("-> ", end=" ")
        print()


if __name__ ==  "__main__":
    linkedlist = LinkedList()

    linkedlist.append(1)
    linkedlist.append(2)
    linkedlist.append(3)
    linkedlist.print_list()

    linkedlist.prepend(4)
    linkedlist.print_list()

class Node:
    def __init__(self, data) -> None:
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self, values=None) -> None:
        self.head = None
        self.tail = None

        if values:
            self.head = Node(values[0])
            current = self.head
            for value in values[1:]:
                new_node = Node(value)
                current.next = new_node
                current = new_node
            self.tail = current

    # 末尾刪除 O(1)知道尾部, 不知道尾部、任意位置O(n)
    def postdelete(self):
        if self.head == None:
            return
        elif self.head.next == None: # 只有一個
            self.head = None
            self.tail = None
            return
        else:
            tmp = self.head
            while tmp.next.next:
                tmp = tmp.next
            tmp.next = None
            self.tail = tmp
            return tmp

    # 頭部刪除 O(1)
    def popdelete(self):
        if self.head == None:
            return
        elif self.head.next == None: # 只有一個
            self.head = None
            self.tail = None
            return
        else:
            tmp = self.head
            self.head = self.head.next
            tmp.next = None 
            return tmp # 返回tmp，之後可以查看被刪掉的值

    # 反轉 O(n)
    def reverse(self):
        if self.head == None: 
            return
        if self.head.next == None: 
            return

        prev = None
        curr = self.head
        after = curr.next

        while after:
            curr.next = prev
            prev = curr
            curr = after
            after = after.next

        curr.next = prev
        self.head = self.tail  


    # 印出
    def print_list(self):
        tmp = self.head
        while tmp:
            print(tmp.data, end=" ")
            tmp = tmp.next
            if tmp:
                print("-> ", end=" ")
        print()


if __name__ ==  "__main__":
    linkedlist = LinkedList(values=[1, 2, 3, 6, 7, 8])
    linkedlist.print_list()

    tmp = linkedlist.postdelete()
    print(f"post tmp : {tmp.data}")
    linkedlist.print_list()

    tmp = linkedlist.popdelete()
    print(f"pop tmp : {tmp.data}")
    linkedlist.print_list()

    linkedlist.reverse()
    linkedlist.print_list()

Doubly Linked List

# double linked lists
# 知道tail情況下

class Node:
    def _init_(self, data) -> None:
        self.data = data
        self.prev = None
        self.next = None

if __name__ == "__main__":
    head = Node(data=1)    
    node1 =Node(data=2)
    node2 =Node(data=3)

    head.next = node1
    node1.prev = head
    node1.next = node2
    node2.prev = node1

    tail = node2

class Node:
    def __init__(self, data) -> None:
        self.data = data
        self.prev = None
        self.next = None

class DoublyLinkedList:
    def __init__(self) -> None:
        self.head = None
        self.tail = None

    # 末尾插入 O(1)
    def append(self, value):
        new_node = Node(value)
        if self.head == None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node

    # 頭部插入 O(1)
    def prepend(self, value):
        new_node = Node(value)
        if self.head == None:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node

    # 印出
    def print_list(self):
        tmp = self.head
        while tmp:
            print(tmp.data, end=" ")
            tmp = tmp.next
            if tmp:
                print("<-> ", end=" ")
        print()


if __name__ ==  "__main__":
    doublylinkedlist = DoublyLinkedList()

    doublylinkedlist.append(1)
    doublylinkedlist.append(2)
    doublylinkedlist.append(3)
    doublylinkedlist.print_list()

    doublylinkedlist.prepend(4)
    doublylinkedlist.print_list()

class Node:
    def __init__(self, data) -> None:
        self.data = data  # Correctly store the data
        self.prev = None  # For doubly linked list
        self.next = None  # For doubly linked list

class DoublyLinkedList:
    def __init__(self, values=None) -> None:
        self.head = None
        self.tail = None
        if values:
            self.head = Node(values[0])
            current = self.head
            for value in values[1:]:
                new_node = Node(value)
                current.next = new_node
                new_node.prev = current  # Set the previous pointer for doubly linked list
                current = new_node
            self.tail = current

    # 末尾刪除 O(1)
    def postdelete(self):
        if self.head is None:
            return
        elif self.head.next is None:  # 只有一個
            tmp = self.head
            self.head = None
            self.tail = None
            return tmp
        else:
            tmp = self.tail
            self.tail = self.tail.prev
            self.tail.next = None
            tmp.prev = None 
            return tmp  # 返回tmp，之後可以查看被刪掉的值

    # 頭部刪除 O(1)
    def popdelete(self):
        if self.head is None:
            return
        elif self.head.next is None:  # 只有一個
            tmp = self.head
            self.head = None
            self.tail = None
            return tmp
        else:
            tmp = self.head
            self.head = self.head.next
            self.head.prev = None
            tmp.next = None 
            return tmp  # 返回tmp，之後可以查看被刪掉的值

    # 印出
    def print_list(self):
        tmp = self.head
        while tmp:
            print(tmp.data, end=" ")
            tmp = tmp.next
            if tmp:
                print("<-> ", end=" ")
        print()

if __name__ == "__main__":
    doublylinkedlist = DoublyLinkedList(values=[1, 2, 3, 6, 7, 8])
    doublylinkedlist.print_list()

    tmp = doublylinkedlist.postdelete()
    print(f"Post-deleted node: {tmp.data}")
    doublylinkedlist.print_list()

    tmp = doublylinkedlist.popdelete()
    print(f"Pop-deleted node: {tmp.data}")
    doublylinkedlist.print_list()

Hash Table 哈希表

Set集合

set集合，只會顯示不重複值

# python set  O(1)

my_set = set()

my_set.add(1)
my_set.add(1)
my_set.add(3.14)
print("Set:", my_set)

Stacks and Queues 堆疊和佇列

Stacks: 先進後出（Last In, First Out，LIFO）。Push： 把元素壓入堆疊的頂部、Pop： 從堆疊的頂部彈出元素

Queues: 先進先出（First In, First Out，FIFO）。Enqueue： 把元素添加到佇列的尾部、Dequeue： 從佇列的頭部移除元素

Stack

# Stack  都O(1)

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()

    def peek(self):  # 查看頭部
        if not self.is_empty():
            return self.items[-1]

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

if __name__ == "__main__":
    my_stack = Stack()
    my_stack.push(10)
    my_stack.push(20)
    my_stack.push(30)
    print(my_stack.items)
    print()

    print("頭部元素:", my_stack.peek())
    print()

    popped_item = my_stack.pop()
    print("彈出的元素:", popped_item)
    print("彈出後:", my_stack.items)
    print()

    print("是否為空:", my_stack.is_empty())
    print()

    print("堆疊大小:", my_stack.size())

Queue

# Queues  都O(1)

class Queue:
    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.items.pop(0)

    def peek(self):
        if not self.is_empty():
            return self.items[0]
        else:
            return None

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)


if __name__ == "__main__":
    my_queue = Queue()
    my_queue.enqueue(10)
    my_queue.enqueue(20)
    my_queue.enqueue(30)
    print(my_queue.items)
    print()

    print("頭部元素:", my_queue.peek())
    print()

    removed_item = my_queue.dequeue()
    print("彈出的元素:", removed_item) 
    print("彈出後:", my_queue.items)   
    print()

    print("是否為空:", my_queue.is_empty())   
    print()

    print("佇列大小:", my_queue.size())

Recursion 遞迴

Recursion: 把一個大問題分解成多個相似但規模較小的子問題，然後遞迴地解決這些子問題，常用於處理樹、鏈表等

通常會使用 call stack，每次都會將新的函數呼叫加入到呼叫堆疊的”頂端”

每個函數呼叫都需要一些記憶體來儲存局部變數、參數和返回地址，這些資訊被儲存在呼叫棧的幀中，當遞歸深度增加時，呼叫棧的大小也會增加

如果每一層遞歸都是O(1)的時間複雜度，而遞迴深度為log n，整體的時間複雜度就是O(log n)

如果每一層遞歸都是O(1)的時間複雜度，但遞歸深度為n，那麼整體的時間複雜度就是O(n)

“`=
def factorial(n):
if n == 0 :
return 1
else:
return n * factorial(n – 1)

使用遞迴計算階乘

result = factorial(5)
print(result)

![螢幕擷取畫面 2023-12-23 174126](https://hackmd.io/_uploads/SkDUim4wp.png)

```=
from typing import Optional  # O(n)


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:

        if not head:
            return None

        new_head = head
        if head.next:
            new_head = self.reverseList(head=head.next)
            head.next.next = head

        head.next = None
        return new_head

def print_list(head: Optional[ListNode]) -> None:
    current = head
    while current:
        print(current.val, end=" -> " if current.next else "\n")
        current = current.next

head = ListNode(val=1,
    next=ListNode(val=2,
    next=ListNode(val=3,
    next=ListNode(val=4,
    next=ListNode(val=5)))))

print("Original list:")
print_list(head)


# 反轉
s = Solution()
reversed_head = s.reverseList(head=head)

print("Reversed list:")
print_list(reversed_head)

Trees 樹

參考

tree: 以分層的方式組織和存儲資訊。樹由節點（Node）組成，每個節點包含一個數據元素，並連接到其他節點

根節點（Root Node）： 樹的頂部節點，是樹的唯一起始點

葉節點（Leaf Node）： 沒有子節點的節點，位於樹的最底層

父節點（Parent Node）： 有子節點的節點

子節點（Child Node）： 由父節點指向的節點
邊(Edge)：樹中兩個節點之間的連線

兄弟姐妹 (Siblings): 具有相同父節點的節點

Level（層級）:樹的第一層從根節點開始，稱為第 1 層。根據樹的結構，每個節點的層級是相對於根節點的深度

深度（Depth）： 一個節點到根節點的唯一路徑上的節點數稱為節點的深度

高度（Height）： 樹中任意節點的深度的最大值被稱為樹的高度

子樹（Subtree）： 由樹中的節點和其所有後代節點構成的樹

二元樹（Binary Tree）： 每個節點最多有兩個子節點的樹 (log n)、O(n)鏈表型

二元搜尋樹(Binary Search Tree) : 左子樹中的所有節點都”小於”該節點，而其右子樹中的所有節點都”大於”該節點。並且不允許有相同值的節點存在，每個節點的值都必須是唯一的 O(log n)、O(n)鏈表型

滿二元樹（Full Binary Tree）: 每個非葉節點的子節點都有兩個子節點，所有葉子節點都在同一層，除了最底層可能不是滿的外，其它每一層的節點數量都是最大可能的 O(log n)

Binary Search Tree

跌代循環查找、遞迴查找

# BST O(logn)

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

class BinarySearchTree:
    def __init__(self, value) -> None:
        self.root = Node(value)

    def insert(self, value):
        new_node = Node(value)

        if self.root is None:
            self.root = new_node
            return True

        tmp_root = self.root
        while True:
            if new_node.value == tmp_root.value:
                return False
            elif new_node.value < tmp_root.value:
                if tmp_root.left is None:
                    tmp_root.left = new_node
                    return True
                tmp_root = tmp_root.left
            else:
                if tmp_root.right is None:
                    tmp_root.right = new_node
                    return True
                tmp_root = tmp_root.right

    # 迴圈，適合深度較大的樹，避免因過多的遞迴調用導致記憶體溢出（Stack Overflow）

    def search(self, value):
        tmp = self.root

        while tmp is not None:
            if value < tmp.value:
                tmp = tmp.left

            elif value > tmp.value:
                tmp = tmp.right
            else:
                return True

        return False

    # 遞迴，根據當前節點的值與目標值的比較結果，遞迴地向左或右子樹搜尋，直到找到目標值或者到達 None
    # 遞迴深度過大時，會導致記憶體溢出（Stack Overflow）
    def search_r(self, current_root, value):

        if current_root is None:
            return False
        if value == current_root.value:
            return True

        if value < current_root.value:
            return self.search_r(current_root.left, value)
        if value > current_root.value:
            return self.search_r(current_root.right, value)


if __name__ == "__main__":
    bst = BinarySearchTree(10)
    bst.insert(5)
    bst.insert(15)

    print(bst.root.value)         # 10
    print(bst.root.left.value)    # 5
    print(bst.root.right.value)   # 15
    print()
    print(bst.search(5))          # True
    print(bst.search(12))         # False
    print(bst.search_r(bst.root, 15))  # True
    print(bst.search_r(bst.root, 8))   # False

# 二分搜索 (Binary Search)

# 迴圈
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid  # 返回目標元素的索引
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1  # 如果目標元素不在數組中，返回 -1


# 遞迴
def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1  # 如果範圍無效，返回 -1

    mid = (left + right) // 2
    if arr[mid] == target:
        return mid  # 找到目標元素，返回索引
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)  # 搜索右半邊
    else:
        return binary_search_recursive(arr, target, left, mid - 1)  # 搜索左半邊


# 
arr = [1, 3, 5, 7, 9, 11, 13]
target = 11

result = binary_search(arr, target)
if result != -1:
    print(f"binary_search：Element found at index: {result}")
else:
    print("binary_search：Element not found in the array.")


result2 = binary_search_recursive(arr, target, 0, len(arr) - 1)
if result2 != -1:
    print(f"binary_search_recursive：Element found at index: {result}")
else:
    print("binary_search_recursive：Element not found in the array.")

Graphs 圖

圖（Graph）: 用於表示物體之間的關係。圖由節點（Node）和邊（Edge）組成，圖可以用來模擬各種實際應用，社交網絡、網絡拓撲、路線規劃等

節點（Node）： 也被稱為頂點（Vertex），表示圖中的一個個體

邊（Edge）： 連接兩個節點的線段，表示兩個物體之間的關係

有向圖（Directed Graph）： 邊有方向的圖，從一個節點指向另一個節點

無向圖（Undirected Graph）： 邊沒有方向的圖，邊是雙向的

度（Degree）： 節點相連的邊的數量，對於有向圖分為入度（In-Degree）和出度（Out-Degree）

路徑（Path）： 由節點和邊依次組成的序列

Weighted Graph（權重圖）： 在這種圖中，每條邊都有一個關聯的權重或成本，這種權重可以代表距離、時間、成本等，用於解決需要考慮邊的權重的問題，如最短路徑、最小生成樹

Unweighted Graph（非權重圖）： 在這種圖中，所有的邊都沒有權重或成本，用於表示只關心節點之間是否有連接關係的情況

Cyclic Graph（循環圖）： 包含至少一個環（Cycle）的圖，一個環是一條起點和終點相同的路徑

Acyclic Graph（無環圖）： 不包含任何環的圖，有向無環圖（DAG）是一種特殊的無環圖，它在應用中常常出現，如依賴關係圖

Tree（樹）： 是一種連通的”有向無環圖”，任意兩個節點之間都有唯一的路徑。PS 不是所有的有向無環圖都是樹

• 【無向圖】
  

— Adjacency Matrix（鄰接矩陣） : 以0 1 表示圖是否有相連
PS 查看關聯較方便

   A  B  C  D
A  0  1  1  0
B  1  0  1  1
C  1  1  0  0
D  0  1  0  0

— Adjacency List（鄰接表）: 列出有相連的點
PS 存儲空間較少

A -> [B, C]
B -> [A, C, D]
C -> [A, B]
D -> [B]

• 【有向圖】
  

— Adjacency Matrix（鄰接矩陣） : 以0 1 表示圖是否有相連並指向

   A  B  C  D
A  0  1  1  0
B  0  0  1  1
C  0  0  0  0
D  0  0  0  0

— Adjacency List（鄰接表）: 列出有相連並指向的點

A -> [B, C]
B -> [C, D]
C -> []
D -> []

• 【權重無向圖】
  

— Adjacency Matrix（鄰接矩陣） : 以權重數字表示圖是否有相連

   A  B  C  D
A  0  1  1  3
B  1  0  0  1
C  1  0  0  2
D  3  1  2  0

— Adjacency List（鄰接表）: 列出有權重數字的點

A: [(B, 1), (C, 1), (D, 3)]
B: [(A, 1), (D, 1)]
C: [(A, 1), (D, 2)]
D: [(A, 3), (B, 1), (C, 2)]

• 【權重有向圖】
  

— Adjacency Matrix（鄰接矩陣） : 以權重數字表示圖是否有相連並指向

   A  B  C  D
A  0  1  1  3
B  0  0  0  1
C  0  0  0  0
D  0  0  2  0

— Adjacency List（鄰接表）: 列出有權重數字並指向的點

A: [(B, 1), (C, 1), (D, 3)]
B: [(D, 1)]
C: []
D: [(C, 2)]

添加、刪除

# graph

class Graph():
    def __init__(self):
        self.adj_list = {}

    def print_graph(self):
        for node in self.adj_list:
            print(node, ":", self.adj_list[node])

    # O(1)  
    def add_node(self, node):
        if node not in self.adj_list:
            self.adj_list[node] = []
            return True
        return False

    # O(1)  
    def add_edge(self, n1, n2):
        if n1 in self.adj_list and n2 in self.adj_list:
            if n2 not in self.adj_list[n1]:
                self.adj_list[n1].append(n2)
                self.adj_list[n2].append(n1)
                return True
        return False

    # O(2n)/O(n)
    def delete_edge(self, n1, n2):
        if n1 in self.adj_list and n2 in self.adj_list:
            try:
                self.adj_list[n1].remove(n2)
                self.adj_list[n2].remove(n1)
            except:
                pass
            return True
        return False

    # O(n*e) * n為節點數、e為邊數
    def delete_node(self, node):
        if node not in self.adj_list:
            return False

        for other in self.adj_list[node]:
            self.adj_list[other].remove(node)
        del self.adj_list[node]
        return True

if __name__ == "__main__":
    graph = Graph()
    graph.add_node('A')
    graph.add_node('B')
    graph.add_node('C')
    graph.print_graph()
    print()

    graph.add_edge('A','B')
    graph.add_edge('A','B')
    graph.add_edge('A','C')
    graph.print_graph()
    print()

    graph.delete_edge('A','B')
    graph.print_graph() 
    print()

    graph.delete_node('A')
    graph.print_graph()