Single linked list
Data Structure python

【Python】Single Linked List(單向鏈結串列) 資料結構實作

clickup

前言

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

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

圖1

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

簡介 Linked List

什麼是Linked List?

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

圖2

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

operationBig-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
圖3
圖4
圖5
  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,所以我們要靠重新尋訪的方式來處理

圖6
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
圖7

當 index == 1

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

圖8

else

圖9
圖10
圖11
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:

圖12

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

圖13
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 讓我得到一些回饋,
支持我繼續寫出更多好文章

clickup

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。