python 鏈表

鏈表是一系列數據元素，通過鏈接連接在一起。每個數據元素都以指針的形式包含到另一個數據元素的連接。python在其標準庫中沒有鏈接列表。我們使用前一章討論過的節點概念來實現鏈表的概念。我們已經看到了我們如何創建節點類以及如何遍歷節點的元素。在本章中，我們將研究被稱為單鏈表的鏈表的類型。在這種類型的數據結構中，任何兩個數據元素之間只有一個鏈接。我們創建這樣一個列表并創建其他方法來插入，更新和從列表中移除元素。

創建鏈接列表

鏈表通過使用我們在上一章中研究的節點類創建。我們創建一個node對象并創建另一個類來使用這個ode對象。我們通過節點對象傳遞適當的值來指向下一個數據元素。下面的程序使用三個數據元素創建鏈接列表。在下一節中，我們將看到如何遍歷鏈表。

class node:
    def __init__(self, dataval=none):
        self.dataval = dataval
        self.nextval = none

class slinkedlist:
    def __init__(self):
        self.headval = none

list1 = slinkedlist()
list1.headval = node("mon")
e2 = node("tue")
e3 = node("wed")
# link first node to second node
list1.headval.nextval = e2

# link second node to third node
e2.nextval = e3

遍歷鏈接列表

從第一個數據元素開始，單向鏈表只能在forwrad方向上遍歷。我們只需通過將下一個節點的指針指向當前數據元素來打印下一個數據元素的值。

class node:
    def __init__(self, dataval=none):
        self.dataval = dataval
        self.nextval = none

class slinkedlist:
    def __init__(self):
        self.headval = none

    def listprint(self):
        printval = self.headval
        while printval is not none:
            print (printval.dataval)
            printval = printval.nextval

list = slinkedlist()
list.headval = node("mon")
e2 = node("tue")
e3 = node("wed")

# link first node to second node
list.headval.nextval = e2

# link second node to third node
e2.nextval = e3

list.listprint()

當上面的代碼被執行時，它會產生以下結果：

mon
tue
wed

插入鏈接列表中

在鏈表中插入元素涉及將指針從現有節點重新分配給新插入的節點。取決于新數據元素是在鏈表的開始位置還是在中間位置或末尾插入，我們有以下方案。

在鏈接列表的開頭插入

這涉及到將新數據節點的下一個指針指向鏈表的當前頭部。因此，鏈表的當前頭成為第二個數據元素，新節點成為鏈表的頭部。

class node:
    def __init__(self, dataval=none):
        self.dataval = dataval
        self.nextval = none

class slinkedlist:
    def __init__(self):
        self.headval = none

# print the linked list
    def listprint(self):
        printval = self.headval
        while printval is not none:
            print (printval.dataval)
            printval = printval.nextval
    def atbegining(self,newdata):
        newnode = node(newdata)

# update the new nodes next val to existing node
        newnode.nextval = self.headval
        self.headval = newnode

list = slinkedlist()
list.headval = node("mon")
e2 = node("tue")
e3 = node("wed")

list.headval.nextval = e2
e2.nextval = e3

list.atbegining("sun")

list.listprint()

當上面的代碼被執行時，它會產生以下結果：

sun
mon
tue
wed

在鏈接列表的末尾插入

這包括將鏈表的當前最后一個節點的下一個指針指向新的數據節點。因此鏈表的當前最后一個節點成為倒數第二個數據節點，新節點成為鏈表的最后一個節點。

class node:
    def __init__(self, dataval=none):
        self.dataval = dataval
        self.nextval = none

class slinkedlist:
    def __init__(self):
        self.headval = none

# function to add newnode
    def atend(self, newdata):
        newnode = node(newdata)
        if self.headval is none:
            self.headval = newnode
            return
        laste = self.headval
        while(laste.nextval):
            laste = laste.nextval
        laste.nextval=newnode

# print the linked list
    def listprint(self):
        printval = self.headval
        while printval is not none:
            print (printval.dataval)
            printval = printval.nextval


list = slinkedlist()
list.headval = node("mon")
e2 = node("tue")
e3 = node("wed")

list.headval.nextval = e2
e2.nextval = e3

list.atend("thu")

list.listprint()

當上面的代碼被執行時，它會產生以下結果：

mon
tue
wed
thu

插入兩個數據節點之間

這涉及到將指定節點的指針指向新節點。這可以通過傳入新節點和現有節點，然后插入新節點。所以我們定義一個額外的類，將新節點的下一個指針改變為中間節點的下一個指針。然后將新節點分配給中間節點的下一個指針。

class node:
    def __init__(self, dataval=none):
        self.dataval = dataval
        self.nextval = none

class slinkedlist:
    def __init__(self):
        self.headval = none

# function to add node
    def inbetween(self,middle_node,newdata):
        if middle_node is none:
            print("the mentioned node is absent")
            return

        newnode = node(newdata)
        newnode.nextval = middle_node.nextval
        middle_node.nextval = newnode

# print the linked list
    def listprint(self):
        printval = self.headval
        while printval is not none:
            print (printval.dataval)
            printval = printval.nextval


list = slinkedlist()
list.headval = node("mon")
e2 = node("tue")
e3 = node("thu")

list.headval.nextval = e2
e2.nextval = e3

list.inbetween(list.headval.nextval,"fri")

list.listprint()

當上面的代碼被執行時，它會產生以下結果：

mon
tue
fri
thu

從喜好列表中刪除項目

我們可以使用該節點的密鑰刪除現有節點。在下面的程序中，我們找到要刪除的節點的前一個節點。然后將該節點的下一個指針指向要刪除的節點的下一個節點。

class node:
    def __init__(self, data=none):
        self.data = data
        self.next = none

class slinkedlist:
    def __init__(self):
        self.head = none

    def atbegining(self, data_in):
        newnode = node(data_in)
        newnode.next = self.head
        self.head = newnode

# function to remove node
    def removenode(self, removekey):

        headval = self.head

        if (headval is not none):
            if (headval.data == removekey):
                self.head = headval.next
                headval = none
                return

        while (headval is not none):
            if headval.data == removekey:
                break
            prev = headval
            headval = headval.next

        if (headval == none):
            return

        prev.next = headval.next

        headval = none

    def llistprint(self):
        printval = self.head
        while (printval):
            print(printval.data),
            printval = printval.next


llist = slinkedlist()
llist.atbegining("mon")
llist.atbegining("tue")
llist.atbegining("wed")
llist.atbegining("thu")
llist.removenode("tue")
llist.llistprint()

當上面的代碼被執行時，它會產生以下結果：

thu
wed
mon