Python程式：向連結串列首尾新增元素

---

在Python中，連結串列是一種線性資料結構，由一系列節點組成，每個節點包含一個值和指向鏈中下一個節點的引用。

在本文中，我們將討論如何在Python中向連結串列的首尾新增元素。

Python中的連結串列

連結串列是一種引用資料結構，它儲存一組元素。它與陣列類似，但陣列中的資料儲存在連續的記憶體位置，而連結串列中的資料不受此限制。這意味著資料不是一個接一個地儲存，而是以隨機的方式儲存在記憶體中。

這就產生了一個問題，即我們如何訪問連結串列中的元素？答案很簡單，在連結串列中，一個元素指向另一個元素，直到列表的末尾。

連結串列的開頭和結尾被認為是特殊位置。連結串列的開頭稱為表頭，它指向第一個元素；最後一個元素是特殊的，因為它指向NULL。

Head -> data_1 -> data_2 -> … -> data_n -> NULL

現在我們知道了如何訪問連結串列的開頭和結尾，讓我們看看如何遍歷元素並訪問連結串列中的資料。

遍歷連結串列非常簡單，我們只需從表頭開始訪問下一個節點；我們不斷重複這個過程，直到找到下一個節點為NULL的節點。至於訪問節點中的資料，我們使用箭頭運算子“->”。

Head->data

現在我們已經具備了開始解決問題所需的所有理解。

在開頭新增元素

要在連結串列的開頭新增資料，我們必須考慮連結串列的表頭。每當我們在連結串列的開頭新增一個節點時，連結串列都會被修改，新新增的節點將成為列表的第一個節點/表頭。

演算法

步驟1 – 建立新節點

步驟2 – 將資料新增到新建立的節點中

步驟3 – 更新新節點的連結，使其指向當前表頭節點

步驟4 – 現在將表頭指標設定為新建立的節點

注意 – 這些步驟的順序至關重要，因為如果您首先將新建立的節點設定為表頭節點，那麼我們將無法更新新節點的連結，而該連結應該理想地指向之前的表頭節點。

示例

class Node:
   def __init__(self, data):
      self.dataPart = data
      self.nextNode = None
class LinkedList:
   def __init__(self):
      self.headNode = None
   def showList(self):
      n = self.headNode
      while n is not None:
         print(n.dataPart, end='-')
         n = n.nextNode
      print('')
   def addBeginList(self, data):
      tempNode = Node(data)
      tempNode.nextNode = self.headNode
      self.headNode = tempNode
newLinkedList = LinkedList()
print("Printing the list before adding element : ")
newLinkedList.showList()
newLinkedList.addBeginList(10)
newLinkedList.addBeginList(25)
print("Printing the elements after adding at the beginning of the list")
newLinkedList.showList()

輸出

Printing the list before adding any element :
\
Printing the elements after adding at the beginning of the list
25-10-\

在末尾新增元素

在末尾新增元素在邏輯上與在列表開頭新增元素不同。這次我們需要訪問列表的最後一個節點而不是第一個節點（即表頭）。

現在的問題是檢查我們嘗試向其中新增元素的列表是空列表還是已經包含一些元素。

如果列表為空，則新節點將成為列表的第一個節點；否則，它將成為最後一個節點。為此，我們需要檢查表頭節點是否為None。如果表頭為None，則列表為空；否則，列表不為空。

演算法

步驟1 – 建立一個新節點。

步驟2 – 將資料新增到節點的資料部分。

步驟3 – 確保新建立節點的下一個節點指向None或空指標。

步驟4 – 如果列表為空，則將新建立的節點作為表頭節點。

步驟5 - 否則遍歷到列表的末尾，最後一個節點。

步驟6 – 將最後一個節點的下一個節點設定為新建立的節點。

示例

class Node:
   def __init__(self, data):
      self.dataPart = data
      self.nextNode = None
class LinkedList:
   def __init__(self):
      self.headNode = None
   def showList(self):
      n = self.headNode
      while n is not None:
         print(n.dataPart, end='-')
         n = n.nextNode
      print("")
   def addEndList(self, data):
      tempNode = Node(data)
      if self.headNode is None:
         self.headNode = tempNode
      else:
         n = self.headNode
         while n.nextNode is not None:
            n = n.nextNode
            n.nextNode = tempNode
newLinkedList = LinkedList()
print("Printing the list before insertion : ")
newLinkedList.showList()
newLinkedList.addEndList(25)
newLinkedList.addEndList(10)
print("Printing the list after adding elements at the end of the list : ")
newLinkedList.showList()

輸出

Printing the list before insertion :
\
Printing the list after adding elements at the end of the list :
25-10-\

結論

在本文中，我們討論瞭如何使用Python類實現連結串列，以及如何在連結串列中新增元素。我們重點介紹了在列表開頭和結尾新增元素。