Python程序添加元素到链表

什么是链表

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

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

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

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

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

HEAD将包含指向第一个节点的链接。最后一个节点将指向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    # 将新节点指向以前的第一个节点
   self.head = newNode         # 将头部指向新添加的节点

在结尾添加元素

将新节点添加到最后一个节点之后，新节点指向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的链接列表。必须在位置3（表示在节点B之后添加）插入新节点E

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）   #创建新节点
   newNode.next = self.head    #将新节点连接到前一个第一个节点
   self.head = newNode         #将头指针指向新添加的节点

  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）：＃用于遍历要插入新节点的位置
      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（"请输入要添加到链表中的元素数量："）
n=int（input（））
for i in range（n）：
    print（"从以下中选择：1.开头2.结束3.中间"）
    a=int（input（））

    if（a == 1）：
        print（"输入数据："）
        data=int（input（））
        newList.insert_at_the_beginning（data）
    elif（a == 2）：
        print（"输入数据："）
        data=int（input（））
        newList.insert_at_the_end（data）
    else：
        print（"输入位置："）
        pos=int（input（））
        print（"输入数据："）
        data=int（input（））
        newList.insert_in_middle（data，pos）

newList.Print_the_LL（）

输出

请输入要添加到链表中的元素数量：
3
从以下中选择：1.开头2.结束3.中间
1
输入数据：
112
从以下中选择：1.开头2.结束3.中间
2
输入数据：
145
从以下中选择：1.开头2.结束3.中间
3
输入位置：
2
输入数据：
223
The linked list elements are: 112 223 145