Python 将元素添加到链表

什么是链表

当数据不存储在连续的内存位置时，搜索所有内存位置以获取所需数据需要很长时间。为了防止这种情况，我们使用链表。

在Python中，链表是一种按顺序存储项的数据结构。它由节点组成，每个节点包含项和列表中下一个节点的引用。第一个节点称为头节点，而最后一个节点被称为尾节点。

链表用于高效的插入和删除操作，因为新的项可以从列表中的任何位置添加或删除，而无需移动其他所有元素。此外，它们占用的内存空间比数组少，因为只需要存储引用而不是每个元素的副本。

链表由节点组成。每个节点包含：

数据
指向下一个节点的链接（通常是一个指针）

头节点将包含指向第一个节点的链接。最后一个节点将指向NULL。将元素添加到链表中有3种情况：可以在开头、结尾或中间（除了开头和结尾之外的任何位置）添加元素。

在开头添加元素

新节点添加在链表头之前。新添加的节点将成为链表的头。

考虑一个带有3个节点A、B和C的链表。要在开头添加新节点D。

Python 将元素添加到链表

步骤

步骤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将被添加到末尾。

Python 将元素添加到链表

步骤

步骤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之后插入)。

Python 将元素添加到链表

步骤

步骤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