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