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类实现链表，以及如何在链表中添加元素。我们重点介绍了在列表开头和结尾添加元素。