python 鏈表

鏈表是一系列數(shù)據(jù)元素，通過鏈接連接在一起。每個數(shù)據(jù)元素都以指針的形式包含到另一個數(shù)據(jù)元素的連接。python在其標(biāo)準(zhǔn)庫中沒有鏈接列表。我們使用前一章討論過的節(jié)點(diǎn)概念來實(shí)現(xiàn)鏈表的概念。我們已經(jīng)看到了我們?nèi)绾蝿?chuàng)建節(jié)點(diǎn)類以及如何遍歷節(jié)點(diǎn)的元素。在本章中，我們將研究被稱為單鏈表的鏈表的類型。在這種類型的數(shù)據(jù)結(jié)構(gòu)中，任何兩個數(shù)據(jù)元素之間只有一個鏈接。我們創(chuàng)建這樣一個列表并創(chuàng)建其他方法來插入，更新和從列表中移除元素。

創(chuàng)建鏈接列表

鏈表通過使用我們在上一章中研究的節(jié)點(diǎn)類創(chuàng)建。我們創(chuàng)建一個node對象并創(chuàng)建另一個類來使用這個ode對象。我們通過節(jié)點(diǎn)對象傳遞適當(dāng)?shù)闹祦碇赶蛳乱粋€數(shù)據(jù)元素。下面的程序使用三個數(shù)據(jù)元素創(chuàng)建鏈接列表。在下一節(jié)中，我們將看到如何遍歷鏈表。

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

遍歷鏈接列表

從第一個數(shù)據(jù)元素開始，單向鏈表只能在forwrad方向上遍歷。我們只需通過將下一個節(jié)點(diǎn)的指針指向當(dāng)前數(shù)據(jù)元素來打印下一個數(shù)據(jù)元素的值。

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()

當(dāng)上面的代碼被執(zhí)行時，它會產(chǎn)生以下結(jié)果：

mon
tue
wed

插入鏈接列表中

在鏈表中插入元素涉及將指針從現(xiàn)有節(jié)點(diǎn)重新分配給新插入的節(jié)點(diǎn)。取決于新數(shù)據(jù)元素是在鏈表的開始位置還是在中間位置或末尾插入，我們有以下方案。

在鏈接列表的開頭插入

這涉及到將新數(shù)據(jù)節(jié)點(diǎn)的下一個指針指向鏈表的當(dāng)前頭部。因此，鏈表的當(dāng)前頭成為第二個數(shù)據(jù)元素，新節(jié)點(diǎn)成為鏈表的頭部。

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()

當(dāng)上面的代碼被執(zhí)行時，它會產(chǎn)生以下結(jié)果：

sun
mon
tue
wed

在鏈接列表的末尾插入

這包括將鏈表的當(dāng)前最后一個節(jié)點(diǎn)的下一個指針指向新的數(shù)據(jù)節(jié)點(diǎn)。因此鏈表的當(dāng)前最后一個節(jié)點(diǎn)成為倒數(shù)第二個數(shù)據(jù)節(jié)點(diǎn)，新節(jié)點(diǎn)成為鏈表的最后一個節(jié)點(diǎn)。

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()

當(dāng)上面的代碼被執(zhí)行時，它會產(chǎn)生以下結(jié)果：

mon
tue
wed
thu

插入兩個數(shù)據(jù)節(jié)點(diǎn)之間

這涉及到將指定節(jié)點(diǎn)的指針指向新節(jié)點(diǎn)。這可以通過傳入新節(jié)點(diǎn)和現(xiàn)有節(jié)點(diǎn)，然后插入新節(jié)點(diǎn)。所以我們定義一個額外的類，將新節(jié)點(diǎn)的下一個指針改變?yōu)橹虚g節(jié)點(diǎn)的下一個指針。然后將新節(jié)點(diǎn)分配給中間節(jié)點(diǎn)的下一個指針。

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()

當(dāng)上面的代碼被執(zhí)行時，它會產(chǎn)生以下結(jié)果：

mon
tue
fri
thu

從喜好列表中刪除項(xiàng)目

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

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()

當(dāng)上面的代碼被執(zhí)行時，它會產(chǎn)生以下結(jié)果：

thu
wed
mon