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

遍歷連結串列

單鏈表只能從第一個資料元素開始向前遍歷。我們只需將下一個節點的指標分配給當前資料元素，即可列印下一個資料元素的值。

示例

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

在連結串列中插入

在連結串列中插入元素涉及重新分配現有節點到新插入節點的指標。根據新資料元素是在連結串列的開頭、中間還是結尾插入，我們有以下幾種情況。

在開頭插入

這涉及將新資料節點的 next 指標指向連結串列的當前頭部。因此，連結串列的當前頭部成為第二個資料元素，而新節點成為連結串列的頭部。

示例

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

在結尾插入

這涉及將連結串列當前最後一個節點的 next 指標指向新資料節點。因此，連結串列的當前最後一個節點成為倒數第二個資料節點，而新節點成為連結串列的最後一個節點。

示例

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

在兩個資料節點之間插入

這涉及更改特定節點的指標以指向新節點。可以透過同時傳入新節點和現有節點（新節點將在其之後插入）來實現。因此，我們定義一個附加類，該類將更改新節點的 next 指標到中間節點的 next 指標。然後將新節點賦值給中間節點的 next 指標。

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

刪除項

我們可以使用該節點的鍵刪除現有節點。在下面的程式中，我們找到要刪除的節點的前一個節點。然後，將此節點的 next 指標指向要刪除節點的下一個節點。

示例

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
列印頁面
上一頁
下一頁
廣告