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

---

什麼是連結串列

當資料不儲存在連續的記憶體位置時，搜尋所有記憶體位置以獲取所需資料會花費大量時間。為了避免這種情況，我們使用連結串列。

Python中的連結串列是一種以有序序列儲存專案的資料結構。它由節點組成，每個節點包含專案和指向列表中下一個節點的引用。第一個節點稱為頭節點，最後一個節點稱為尾節點。

連結串列用於高效的插入和刪除操作，因為可以在列表中的任何位置新增或刪除新專案，而無需移動周圍的其他所有元素。此外，它們比陣列佔用更少的記憶體空間，因為只需要儲存引用，而不是每個元素的副本。

連結串列由節點組成。每個節點包含：

• 資料

• 指向下一個節點的連結（通常是指標）

HEAD包含指向第一個節點的連結。最後一個節點指向NULL。向連結串列中新增元素有三種情況：您可以在開頭、結尾或中間（除開頭和結尾外的任何位置）新增元素。

在開頭新增元素

新節點新增到連結串列的頭部之前。新新增的節點將成為連結串列的頭節點。

考慮一個包含3個節點A、B和C的連結串列。新節點D要新增到開頭。

演算法

步驟1 - 首先，建立要新增到連結串列開頭的新的節點並分配資料。

步驟2 - 現在，使新節點指向頭部。

步驟3 - 使頭部指向新建立節點的地址。

函式實現

def insert_at_the_beginning(self, newVal):
   newNode = Node(newVal)      #creating the new node
   newNode.next = self.head    #pointing the new node to the previous first node
   self.head = newNode         #Making the head point to the newly added node

在結尾新增元素

新節點新增到最後一個節點之後，並且新節點指向NULL。考慮一個包含3個節點A、B和C的連結串列。新節點D要新增到結尾。

演算法

步驟1 - 建立要新增到連結串列開頭的新的節點並分配資料，並使其指向NULL。

步驟2 - 遍歷到連結串列的結尾（遇到NULL時連結串列結束）

步驟3 - 使最後一個節點指向新建立的節點

函式實現

def insert_at_the_end(self,newVal):
   newNode=Node(newVal)
   temp=self.head
   while(temp.next):
   temp=temp.next
   temp.next=newNode

在中間新增元素

將給出新節點要插入的位置以及資料。我們需要在新位置插入新節點。

考慮一個包含4個節點A、B、C和D的連結串列。新節點E要插入到位置3（這意味著它新增到節點B之後）。

演算法

步驟1 - 建立要新增到連結串列中間的新的節點並分配資料。

步驟2 - 遍歷列表直到新節點位置之前的那個節點。

步驟3 - 假設您想在位置“x”插入一個新節點

• 遍歷到x-1。

• 使新節點指向(x-1.next)

• 使x-1指向新節點。

函式實現

def insert_in_middle(self,newVal,pos):
   newNode=Node(newVal)
   temp=self.head
   for i in range(2,pos): 
      if temp.next!=None:
         temp=temp.next
   newNode.next=temp.next
   temp.next=newNode

Python程式碼

class Node:
   def __init__(self, val):
      self.val = val
      self.next = None


class LinkedList:
   def __init__(self):
      self.head = None

   def insert_at_the_beginning(self, newVal):
   newNode = Node(newVal)      #creating the new node
   newNode.next = self.head    #pointing the new node to the previous first node
   self.head = newNode         #Making the head point to the newly added node

   def insert_at_the_end(self,newVal):
      newNode=Node(newVal)
      temp=self.head
      while(temp.next):
         temp=temp.next
      temp.next=newNode

   def insert_in_middle(self,newVal,pos):
      newNode=Node(newVal)
      temp=self.head
      for i in range(2,pos): #for traversing to the position where you want to insert the new node
      if temp.next!=None:
         temp=temp.next

      newNode.next=temp.next
      temp.next=newNode

   def Print_the_LL(self):
      temp = self.head
      if(temp != None):
          print("The linked list elements are:", end=" ")
          while (temp != None):
            print(temp.val, end=" ")
            temp = temp.next
        else:
          print("The list is empty.")

newList = LinkedList()
print("\nEnter the number of elements you want to add into the linked list :")
n=int(input())
for i in range(n):
    print("Chose from the following: 1.BEGINNING   2.END   3.MIDDLE")
    a=int(input())

    if(a==1):
        print("Enter the data :  ")
        data=int(input())
        newList.insert_at_the_beginning(data)
    elif(a==2):
        print("Enter the data :  ")
        data=int(input())
        newList.insert_at_the_end(data)
    else:
        print("Enter the position: ")
        pos=int(input())
        print("Enter the data :  ")
        data=int(input())
        newList.insert_in_middle(data,pos)

newList.Print_the_LL()

輸出

Enter the number of elements you want to add into the linked list :
3
Chose from the following: 1.BEGINNING   2.END   3.MIDDLE
1
Enter the data :
112
Chose from the following: 1.BEGINNING   2.END   3.MIDDLE
2
Enter the data :
145
Chose from the following: 1.BEGINNING   2.END   3.MIDDLE
3
Enter the position:
2
Enter the data :
223
The linked list elements are: 112 223 145