• GitHub
• Facebook
• Instagram

前言

前篇介紹 【Python】Stack(堆疊) 資料結構實作 後，接著要來談談「鏈結串列」(Linked List)

只要在大學修過資料結構之後都知道鏈結串列就是到Tree之前一定要懂的DS，主要是因為Tree也是 Node 的概念儲存 data 和 指到下一個 Node 的 pointer

藉由每個Node的pointer指向下一個Node可以將多個Node串連起來，形成 「位址Address不連續但一樣可以找到下一個資料的結構」

簡介 Linked List

什麼是Linked List?

Linked list(鏈結串列) 是一個有相似資料型態序列的nodes，每個node儲存一個data物件 與 指向下一個node位址的pointer

Linked List: 特點

• 節點資料的type、記憶體大小不用相同
• 不支援如Stack的隨機存取（Random Access），只能做循序存取 (Sequential access)
• 需額外 1. head 2. tail 3.current 空間
  • head: 指向第一個node
  • tail: 指向最後一個node
  • current: 在循序搜尋時current會指向當前的node

Linked List: Big-O

	operation	Big-O
search	搜尋	O(N)
insert	插入第一項	O(1)
append	插入最後一項	O(N)
remove	移除第一項	O(1)
removeLast	移除最後一項	O(N)

用Python實作Linked List

首先我們先建立 class Node

• data 存資料
• next 指向下一個node

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

接著建立 class Node

• head 指向第一個資料
• tail 指向最後一個資料

因為一開時串列沒有資料，所以初始head和tail設為None

class SingleLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

以下就來開始實作功能拉

append: 從tail新增資料

從tail加入資料，也就是類似於list的append

在呼叫append(self, data) 傳入data之後會先建立一個Node的instance

註：利用建構子 (constructor) 建立的物件被稱為實體 (instance)

接著判斷head是否為None

• self.head == None
  • 代表這個Linked list為空，因此head 跟tail同時指向 new_node
• self.head != None
  • 代表這個Linked list沒有為空，所以將tail.next指向new_node，tail就變成指向new_node

  def append(self, data):
        #建立 class Node 的instance(實體)
        new_node = Node(data)
        
        # 如果head == None 代表為第一個Node
        if self.head == None:
            self.head = new_node
            self.tail = new_node

        else:
            self.tail.next = new_node
            self.tail = self.tail.next

delete: 從tail刪除資料

可能比較直覺的會認為說刪除tail資料不是從tail直接刪掉就好了嗎？答案是NONONO，最大的原因在於這是「單向」鏈結串列，因此我們沒pointer指回前一個node，所以我們要靠重新尋訪的方式來處理

def delete(self):
        if self.head == None:
            return print("This list is empty")
        else:
            if len(self) == 1:
                self.head = None
            else:
                #請參圖6
                current_node = self.head
                while current_node.next != None:
                    self.tail = current_node
                    current_node = current_node.next
                self.tail.next = None

insert: 從特定node插入資料

在insert(self, index, data)我們需要傳入index 和data

• index: 第幾個node
• data: 要新增的data

當 index == 1

插入第一個node會影響到head的指標所以分開處理

else

def insert(self, index , data):
        '''
        To insert the data to the specific index
        '''
        if self.head == None:
            print("You can only insert the data to a not empty list")
        if not 1 <= index <= len(self):
            print("{} is not in range".format(index))

        elif index == 1:
            #圖8
            new_node = Node(data)
            new_node.next = self.head
            self.head = new_node
        else:
            #圖9
            cur_idx = 1
            new_node = Node(data)
            current_node = self.head
            while cur_idx+1 != index:
                current_node = current_node.next
                cur_idx += 1

            new_node.next = current_node.next #圖10
            current_node.next = new_node #圖11

delete_node_by_index: 刪除特定的node

if index == 1 and len(self) > 1:

index == 1 and len(self) == 1

def delete_node_by_index(self, index):
        '''
        To delete the specific node
        '''
        if self.head == None:
            print("You can only delete the data from a not empty list")
        #圖12
        if index == 1 and len(self) > 1:
            self.head = self.head.next

        #圖13
        elif index == 1 and len(self) == 1:
            self.head = None
            self.tail = None

        elif 1 < index < len(self):
            cur_idx = 1
            current_node = self.head
            while cur_idx != index:
                previous_node = current_node
                current_node = current_node.next
                cur_idx += 1
            previous_node.next = current_node.next

        elif index == len(self):
            cur_idx = 1
            current_node = self.head
            while cur_idx != index:
                previous_node = current_node
                current_node = current_node.next
                cur_idx += 1
            previous_node.next = None
            self.tail = previous_node

        else:
            print("index out of range")

reverse: 反轉鏈結串列

反轉前

反轉後

def reverse(self):

        # reverse the order of the list
        previous_node = None
        current_node = self.head
        self.tail = current_node
        next_node = current_node.next

        while next_node is not None:
            current_node.next = previous_node
            previous_node = current_node
            current_node = next_node
            next_node = next_node.next

        current_node.next = previous_node
        self.head = current_node
        return

Linked List 完整程式碼

'''
Welcome to use my SingleLinkedList
The following line is the ouput of the SingleLinkedList
[1]1 --> [2]2 --> [3]3 --> [4]5
[index]: means the index of the node
And the following number/string of [index] is the data of the Node
'''
import os
class Node:
    def __init__(self ,data=None, next=None):
        self.data = data
        self.next = next

class SingleLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, data):
        new_node = Node(data)

        if self.head == None:
            self.head = new_node
            self.tail = new_node

        else:
            self.tail.next = new_node
            self.tail = self.tail.next

    #重寫
    def delete(self):
        if self.head == None:
            return print("This list is empty")
        else:
            if len(self) == 1:
                self.head = None
            else:
                current_node = self.head
                while current_node.next != None:
                    self.tail = current_node
                    current_node = current_node.next
                self.tail.next = None


    def insert(self, index , data):
        '''
        To insert the data to the specific index
        '''
        if self.head == None:
            print("You can only insert the data to a not empty list")
        if not 1 <= index <= len(self):
            print("{} is not in range".format(index))

        elif index == 1:
            new_node = Node(data)
            new_node.next = self.head
            self.head = new_node
        else:
            cur_idx = 1
            new_node = Node(data)
            current_node = self.head
            while cur_idx+1 != index:
                current_node = current_node.next
                cur_idx += 1
            new_node.next = current_node.next
            current_node.next = new_node

    def delete_node_by_index(self, index):
        '''
        To delete the specific node
        '''
        if self.head == None:
            print("You can only delete the data from a not empty list")

        if index == 1 and len(self) > 1:
            self.head = self.head.next

        elif index == 1 and len(self) == 1:
            self.head = None
            self.tail = None

        elif 1 < index < len(self):
            cur_idx = 1
            current_node = self.head
            while cur_idx != index:
                previous_node = current_node
                current_node = current_node.next
                cur_idx += 1
            previous_node.next = current_node.next

        elif index == len(self):
            cur_idx = 1
            current_node = self.head
            while cur_idx != index:
                previous_node = current_node
                current_node = current_node.next
                cur_idx += 1
            previous_node.next = None
            self.tail = previous_node

        else:
            print("index out of range")

    def reverse(self):

        # reverse the order of the list
        previous_node = None
        current_node = self.head
        self.tail = current_node
        next_node = current_node.next

        while next_node is not None:
            current_node.next = previous_node
            previous_node = current_node
            current_node = next_node
            next_node = next_node.next

        current_node.next = previous_node
        self.head = current_node
        return


    def __len__(self):
        length = 0
        current_node = self.head
        while current_node != None:
            length += 1
            current_node = current_node.next
        return length

    def __str__(self):
        current_node = self.head
        chain = []
        index = 1
        while current_node != None:
            chain.append("["+str(index)+"]"+str(current_node.data))
            index += 1
            current_node = current_node.next
        return " --> ".join(chain)



def main():

    l = SingleLinkedList()
    while True:
        os.system('cls' if os.name == 'nt' else 'clear')
        print(__doc__)
        print(l)
        print("這個鏈結串列的長度為："+ str(len(l)))
        print("-"*20)
        opt = input("1. 加入資料\n2. 刪除資料\n3. 插入資料\n4. 刪除特定資料\n5. 反轉串列\n0. 結束程式\n 請輸入要使用的功能：")

        if opt == "1":
            data = input("請輸入要加入的資料：")
            l.append(data)
            print(l)

        elif opt == "2":
            l.delete()
            print(l)

        elif opt == "3":
            index = input("請輸入要插入的資料的index：")
            data = input("請輸入要插入的資料：")
            l.insert(int(index), data)
            print(l)

        elif opt == "4":
            index = int(input("請輸入要刪除的資料的index："))
            l.delete_node_by_index(int(index))
            print(l)

        elif opt == "5":
            l.reverse()
            print(l)

        elif opt == "0":
            print("The Final result is: {}".format(l))
            return False
        else:
            print("請輸入合法指令")


if __name__ == '__main__':
    main()

Showcase

如果對文章內容有任何問題，歡迎在底下留言讓我知道。 
如果你喜歡我的文章，可以分享我的文章，讓更多的人看見我的文章。 
追蹤我的Instagram，看我分享 #愛喝咖啡 #咖啡程式 #咖啡程式吱喳 #咖啡程式白日夢
如果這篇文章對你有幫助，
可以幫我在下方按 5 個Like 讓我得到一些回饋，
支持我繼續寫出更多好文章

  
 
 
 
 
 
 
 View this post on Instagram
 
 
 
 
 
 
 
 
 
 
 🐧分享我最愛用的幾個app 1. ClickUp —>專案管理大推 2. Sourcetree —> Git GUI 3. GitHub —> 一定要會用的 4. Atom —> 目前愛用的code editor 5. Iterm2 —> 終於不是死板的Terminal #愛喝咖啡 #咖啡程式 #咖啡程式吱喳 #code #programmer #programming #atom #clickup #sourcetree #github #iterm2 #workspace #application #computer #computerscience #engineer #engineering #coding #codinglife💻
 
A post shared by  🇹🇼咖啡程式人Joy (@lovedrinkcafe) on Nov 6, 2020 at 5:28pm PST
 

• 【SSH】製作SSH key教學
• 【快速架站】什麼是Hexo? 5分鐘快速架站教學
• 【Python】Quick Sort 快速排序｜演算法介紹、新手快速入門
• 【Python】Insertion Sort 插入排序｜演算法介紹、新手快速入門
• 【Python】Selection Sort 選擇排序｜演算法介紹、新手快速入門
• 【Python】Bubble Sort 泡沫排序｜演算法介紹、新手快速入門
• 【Python】Binary Search 二分搜尋｜演算法介紹、新手快速入門
• 【Python】linear search 線性搜尋｜演算法介紹、新手快速入門
• 【Python】什麼是演算法？｜演算法介紹、新手快速入門
• 【教學】使用Sourcetree將專案push到Github｜GitHub Token 產製與用法

• GitHub
• Facebook
• Instagram