Python 中的链接列表

Aditya Raj 2024年2月15日

Python Python Data Structure

什么是 Python 中的链表
在 Python 中如何创建链表
在 Python 中打印链表的所有元素
在 Python 中将元素插入到链表中
从 Python 中的链表中删除一个元素
在 Python 中计算链表中的元素数
在 Python 中更新链表中的节点
在 Python 中为什么使用链表
Python 中的完整实现链表
结论

Python 为我们提供了各种内置的数据结构。

但是，每种数据结构都有其局限性。因此，我们需要自定义数据结构。

本文将讨论一种称为链表的自定义数据结构。我们还将在 Python 中实现一个链表，并对链表进行各种操作。

什么是 Python 中的链表

顾名思义，链表是一种数据结构，其中包含使用链接连接的元素。

链表是使用称为节点的对象创建的。每个节点包含两个属性——一个用于存储数据，另一个用于连接到链表中的下一个节点。

你可以使用下图了解节点的结构。

Python 中的节点

这里，

Node 是包含属性 data 和 next 的对象。
属性 data 存储数据。
属性 next 指链表中的下一个节点。

如下图所示，我们可以连接各个节点来创建一个链表。

Python 中的链表

这里，

我们创建了一个由四个节点组成的链表。
第一个节点包含数字 10，第二个节点包含 20，第三个节点包含 30，最后一个节点包含 40。
我们还创建了一个引用第一个节点的变量 Head。我们只将 Head 变量保存在链表对象中。所有其他节点中的数据都是通过从 Head 引用的第一个节点开始遍历链表获得的。
最后一个节点的 next 属性指的是 None 对象。链表最后一个节点的 next 属性将始终引用 None 对象。
如果链表为空，则 Head 变量将引用 None 对象。

我们现在了解了链表的基本结构。让我们在 Python 中实现一个链表。

在 Python 中如何创建链表

由于节点是链表的构建块，我们将首先创建一个节点。为此，我们将定义一个具有属性 data 和 next 的 Node 类，如下所示。

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


myNode = Node(10)
print("The data in the node is:", myNode.data)
print("The next attribute in the node is:", myNode.next)

输出：

The data in the node is: 10
The next attribute in the node is: None

在上面的例子中，你可以观察到 Node 的 next 属性默认是指 None。当我们将它插入到链表中时，我们将 next 属性分配给链表中的节点，我们将在前面讨论。

我们必须创建一个具有 Head 属性的对象来创建一个链表。我们可以定义 LinkedList 类，如下所示。

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


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


myLinkedList = LinkedList()
myNode1 = Node(10)
myNode2 = Node(20)
myNode3 = Node(30)
myNode4 = Node(40)
myLinkedList.Head = myNode1
myNode1.next = myNode2
myNode2.next = myNode3
myNode3.next = myNode4

print("The elements in the linked list are:")
print(myLinkedList.Head.data, end=" ")
print(myLinkedList.Head.next.data, end=" ")
print(myLinkedList.Head.next.next.data, end=" ")
print(myLinkedList.Head.next.next.next.data)

输出：

The linked list is:
10 20 30 40

在上面的例子中，我们创建了一个链表。

之后，我们使用给定的数据手动创建节点，将它们一一添加到链表中，并打印出来。稍后，我们将学习使用 Python 的 while 循环将元素插入到链表中。

现在让我们讨论如何在不手动访问所有节点的情况下打印链表的所有元素。

在 Python 中打印链表的所有元素

我们将使用 while 循环来打印所有链表元素。

从 Head 指针开始，我们将首先使用节点的 data 属性打印当前节点中的数据。之后，我们将使用 next 指针移动到下一个节点。

我们将遵循这个过程，直到到达链表的末尾（即，节点的 next 属性被发现为 None）。如下所示，你可以在 printList() 方法中实现整个逻辑。

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


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

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next


myLinkedList = LinkedList()
myNode1 = Node(10)
myNode2 = Node(20)
myNode3 = Node(30)
myNode4 = Node(40)
myLinkedList.Head = myNode1
myNode1.next = myNode2
myNode2.next = myNode3
myNode3.next = myNode4

print("The elements in the linked list are:")
myLinkedList.printList()

输出：

The elements in the linked list are:
10 20 30 40

在 Python 中将元素插入到链表中

在链表中插入元素有四种情况。

链表在插入前可以为空。
我们必须在非空链表的开头插入一个元素。
我们必须在链表的末尾插入一个元素。
我们必须在链表的给定位置插入一个元素。

让我们讨论如何在所有情况下将元素插入到链表中。

将元素插入空链表

要将元素插入空链表，我们将定义一个方法 insertIntoEmptyList()，该方法接受元素作为输入参数，并将包含输入元素的节点添加到链表中。

为此，我们将在 insertIntoEmptyList() 中创建一个节点，输入元素为 data。创建节点后，我们将节点分配给 Head 属性。

这样，新节点将成为链表的第一个节点。该方法可以如下实现。

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


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

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next

    def insertIntoEmptyList(self, element):
        newNode = Node(element)
        self.Head = newNode


myLinkedList = LinkedList()
myLinkedList.insertIntoEmptyList(10)
print("The elements in the linked list are:")
myLinkedList.printList()

输出：

The elements in the linked list are:
10

在链表的开头插入元素

为了在非空列表的开头插入一个元素，我们将定义一个方法 insertAtBeginning()，它将一个元素作为输入并将其添加到链表的开头。在 insertAtBeginning() 方法中，我们将首先创建一个以输入元素作为数据的节点。

之后，我们将新创建的节点的 next 属性指向链表的 Head 属性指向的节点。接下来，我们将新创建的节点分配给 Head 属性。

这样，新节点将被插入到链表的开头。

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


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

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next

    def insertIntoEmptyList(self, element):
        newNode = Node(element)
        self.Head = newNode

    def insertAtBeginning(self, element):
        newNode = Node(element)
        newNode.next = self.Head
        self.Head = newNode


myLinkedList = LinkedList()
myLinkedList.insertIntoEmptyList(10)
myLinkedList.insertAtBeginning(20)
myLinkedList.insertAtBeginning(30)
print("The elements in the linked list are:")
myLinkedList.printList()

输出：

The elements in the linked list are:
30 20 10

如下所示，我们可以结合上述方法创建一个方法，在链表的开头插入一个元素。

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


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

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next

    def insertAtBeginning(self, element):
        if self.Head is None:
            newNode = Node(element)
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = self.Head
            self.Head = newNode


myLinkedList = LinkedList()
myLinkedList.insertAtBeginning(10)
myLinkedList.insertAtBeginning(20)
myLinkedList.insertAtBeginning(30)
print("The elements in the linked list are:")
myLinkedList.printList()

输出：

The elements in the linked list are:
30 20 10

我们将 insertIntoEmptyList() 方法合并到 insertAtBeginning() 方法中，因为插入空链表本质上意味着我们在链表的开头插入一个元素。

在链表末尾插入元素

在空列表的末尾插入元素类似于在链表的开头插入元素。

要在链表的末尾插入一个元素，我们将首先检查链表是否为空。如果发现链表为空，我们可以简单地将包含新元素的节点分配给 Head 属性，就像我们在 insertAtBeginning() 方法中所做的那样。

否则，我们将使用 while 循环遍历链表直到结束。我们将从 Head 开始并使用节点的 next 属性继续移动到下一个节点，直到我们发现节点的 next 属性指向 None。

一旦我们到达一个其 next 属性指向 None 的节点，我们就在最后一个节点。现在，我们将使用输入数据创建一个新节点，并将该节点分配给链表最后一个节点的下一个属性。

这样，新元素将被插入到链表的末尾。你可以在方法 insertAtEnd() 中实现整个逻辑，如下所示。

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


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

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next

    def insertAtEnd(self, element):
        if self.Head is None:
            newNode = Node(element)
            self.Head = newNode
        else:
            current = self.Head
            while current.next is not None:
                current = current.next
            newNode = Node(element)
            current.next = newNode


myLinkedList = LinkedList()
myLinkedList.insertAtEnd(10)
myLinkedList.insertAtEnd(20)
myLinkedList.insertAtEnd(30)
print("The elements in the linked list are:")
myLinkedList.printList()

输出：

The elements in the linked list are:
10 20 30

在链表的给定位置插入元素

我们将使用一个计数器变量和一个 while 循环在链表中的给定位置插入一个元素。

我们将从 Head 指针开始，并使用 while 循环继续移动到下一个节点。在每次迭代中，我们还将递增计数器变量。

一旦我们到达给定位置之前的节点，我们就会退出 while 循环。此外，如果我们到达链表的末尾，我们将退出循环。否则，程序会出错。

之后，如果我们还在 Head，我们必须将元素添加到链表的第一个位置；我们将给定位置的节点分配给包含新节点元素的 next 指针。接下来，我们将新元素的节点分配给链表的 Head。

如果我们不必在第一个位置插入元素，我们会将给定位置的节点分配给包含新元素的节点的 next 指针。接下来，我们将新节点分配给位于 position-1 的节点的 next 属性。

这样，新元素将插入给定位置。如下所示，你可以在 insertAtPosition() 方法中实现整个逻辑。

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


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

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode


myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.insertAtPosition(20, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.insertAtPosition(30, 3)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()

输出：

The elements in the linked list are:
10 
The elements in the linked list are:
10 20 
The elements in the linked list are:
10 20 30 
The elements in the linked list are:
10 40 20 30

从 Python 中的链表中删除一个元素

当我们试图从链表中删除一个元素时，可能有三种情况。

我们要删除链表的第一个元素。
我们要删除链表的最后一个元素。
我们必须删除链表中任意位置的元素。

让我们一一讨论所有这些情况。

删除链表的第一个元素

要删除链表的第一个元素，我们将首先检查链表是否为空。

为此，我们将检查链表的 Head 是否指向 None。如果是，我们将通知用户链表为空，我们没有要删除的元素。

否则，我们会将第一个节点分配给一个临时变量。之后，我们将链表的第二个节点分配给 Head 属性。

然后，我们将使用 del 语句删除存储在临时变量中的第一个节点。如下所示，你可以在 deleteFromBeginning() 方法中实现整个逻辑。

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


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

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode

    def deleteFromBeginning(self):
        if self.Head is None:
            print("The linked list empty. Cannot delete an element.")
            return
        else:
            node = self.Head
            self.Head = self.Head.next
            del node


myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteFromBeginning()
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteFromBeginning()
print("The elements in the linked list are:")
myLinkedList.printList()

输出：

The elements in the linked list are:
10 40 20 30 
The elements in the linked list are:
40 20 30 
The elements in the linked list are:
20 30

删除链表的最后一个元素

要删除链表的最后一个元素，我们将首先检查链表是否为空。

为此，我们将检查链表的 Head 是否指向 None。如果是，我们将通知用户链表为空，我们没有要删除的元素。

如果列表中存在元素，我们将遵循以下过程。

将第一个节点分配给变量 current。
将变量 previous 初始化为 None。
使用 while 循环遍历链表，将 current 变量处的节点分配给 previous 变量，将 current 变量前进到下一个节点，直到 current 变量到达最后一个节点.在这种情况下，分配给 current 的节点的 next 属性变为 None。
一旦当前变量到达最后一个节点，我们将把 None 分配给 previous 变量的 next 属性，并删除分配给 current 变量的节点。

我们可以通过执行上述步骤删除链表的最后一个元素。如下所示，你可以在 deleteFromLast() 方法中实现整个逻辑。

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


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

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode

    def deleteFromLast(self):
        if self.Head is None:
            print("The linked list empty. Cannot delete an element.")
            return
        else:
            current = self.Head
            previous = None
            while current.next is not None:
                previous = current
                current = current.next
            previous.next = None
            del current


myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteFromLast()
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteFromLast()
print("The elements in the linked list are:")
myLinkedList.printList()

输出：

The elements in the linked list are:
10 40 20 30 
The elements in the linked list are:
10 40 20 
The elements in the linked list are:
10 40

删除链表中任意给定位置的元素

要删除链表中任何给定位置的元素，我们将首先检查链表是否为空。

为此，我们将检查链表的 Head 是否指向 None。如果是，我们将通知用户链表为空，我们没有要删除的元素。

如果链表中存在元素，并且我们必须删除任何其他位置的元素，我们将按照以下步骤操作。

将第一个节点分配给变量 current。
将变量 previous 初始化为 None。
将变量 count 初始化为 1。
使用 while 循环遍历链表，在每次迭代中递增 count，将 current 变量处的节点分配给 previous，并将 current 变量前进到下一个节点直到 count 变量具有要删除的元素的位置，或者我们到达链表的末尾。此时，变量 current 将指向必须删除的节点。
一旦计数等于要删除元素的位置，可能有两种情况。
如果我们仍然在 Head，在第一个位置，我们会将当前变量的 next 属性引用的节点分配给 Head 属性。之后，我们将删除 current 变量。
如果我们不在第一个位置，我们将把 current 变量的下一个节点分配给分配给 previous 变量的节点的下一个属性。我们将删除分配给 current 变量的节点。这样，给定位置的元素将被删除。

我们可以在下面讨论的 deleteAtPosition() 方法中实现上述逻辑。

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


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

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode

    def deleteAtPosition(self, position):
        if self.Head is None:
            print("The linked list empty. Cannot delete an element.")
            return
        else:
            current = self.Head
            previous = None
            count = 1
            while current.next is not None and count < position:
                previous = current
                current = current.next
                count += 1
            if current == self.Head:
                self.Head = current.next
                del current
            else:
                previous.next = current.next
                del current


myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteAtPosition(1)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteAtPosition(2)
print("The elements in the linked list are:")
myLinkedList.printList()

输出：

The elements in the linked list are:
10 40 20 30 
The elements in the linked list are:
40 20 30 
The elements in the linked list are:
40 30

在 Python 中计算链表中的元素数

要计算链表中元素的数量，我们只需将变量 count 初始化为 0。

之后，我们将从 Head 开始并使用 while 循环移动到下一个节点，直到到达链表的末尾。在 while 循环的每次迭代中，我们将 count 增加 1。

执行完 while 循环后，我们将在变量 count 中获得链表中元素的数量。你可以按照下面的 countElements() 方法来实现此逻辑。

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


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

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode

    def countElements(self):
        count = 0
        current = self.Head
        while current is not None:
            count += 1
            current = current.next
        print("Number of elements in the linked list are:", count)


myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.countElements()

输出：

The elements in the linked list are:
10 40 20 30 
Number of elements in the linked list are: 4

在 Python 中更新链表中的节点

更新链表中某个节点的值可能有两种情况。

我们需要替换一个值。
我们需要为链表中任意给定位置的元素分配一个新值。

替换链表中的值

要替换链表中的值，我们将从第一个节点开始，并使用 while 循环遍历链表。

我们将检查 current 节点是否包含每个节点要替换的值。如果是，我们将用新值替换当前节点中的值。

通过这种方式，我们可以更新链表中任何元素的第一次出现，如 replaceElement() 方法所示。

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


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

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode

    def replaceElement(self, old_element, new_element):
        current = self.Head
        while current is not None:
            if current.data == old_element:
                current.data = new_element
                break
            current = current.next


myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.replaceElement(30, 100)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.replaceElement(20, 150)
print("The elements in the linked list are:")
myLinkedList.printList()

输出：

The elements in the linked list are:
10 40 20 30 
The elements in the linked list are:
10 40 20 100 
The elements in the linked list are:
10 40 150 100

更新链表中给定位置的元素

要更新链表中给定位置的元素，我们将首先检查链表是否为空。如果是，可能有两种情况。

如果链表为空并且我们必须更新第一个位置以外的元素，我们将通知用户无法完成。

如果链表为空并且我们必须更新第一个位置的元素，我们将使用给定元素创建一个新节点并将该节点分配给链表的 Head。否则，我们将变量 counter 初始化为 1。

之后，我们将使用 while 循环遍历链表。在 while 循环的每次迭代中，我们将移动到链表中的下一个节点，将变量 counter 加 1，并检查我们是否已经到达需要更新的元素位置。

如果到达需要更新的位置，我们会更新链表当前节点中的值并通知用户。

如果我们无法到达需要更新的位置并且 while 循环终止，我们将通知用户没有足够的元素并且我们无法更新值。这个逻辑可以在 updateAtPosition() 方法中实现，如下所示。

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


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

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode

    def updateAtPosition(self, new_element, position):
        if self.Head is None and position != 1:
            print("No element to update in the linked list.")
            return
        elif self.Head is None and position == 1:
            newNode = Node(new_element)
            self.Head = newNode
            return
        count = 1
        current = self.Head
        while current.next is not None and count < position:
            count += 1
            current = current.next
        if count == position:
            current.data = new_element
        elif current.next is None:
            print("Not enough elements in the linked list.")


myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.updateAtPosition(100, 3)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.updateAtPosition(150, 12)
print("The elements in the linked list are:")
myLinkedList.printList()

输出：

The elements in the linked list are:
10 40 20 30 
The elements in the linked list are:
10 40 100 30 
Not enough elements in the linked list.
The elements in the linked list are:
10 40 100 30

在 Python 中为什么使用链表

如果你不需要随机访问元素，链表可能是更好的选择。当我们有数百万个元素要存储并且不需要随机访问时，你应该在 Python 中使用链表而不是普通列表。
与列表中存在的元素数量相比，列表的实际大小非常大。列表的实际大小大约是其中存在的元素数量的 1.5 倍。它确保我们有足够的内存将元素插入到列表中。但是，链表不需要额外的空格。
当我们将一个元素插入到链表中时，只需要存储。列表还需要连续的内存位置。相反，链表的节点可以出现在物理内存中的任何位置。它们使用参考连接。
你可以使用链表有效地实现堆栈和队列数据结构。另一方面，使用列表实现队列的时间复杂度很高。

Python 中的完整实现链表

以下是使用本文讨论的所有方法在 Python 中实现链表的完整运行代码。

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


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

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtBeginning(self, element):
        if self.Head is None:
            newNode = Node(element)
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = self.Head
            self.Head = newNode

    def insertAtEnd(self, element):
        if self.Head is None:
            newNode = Node(element)
            self.Head = newNode
        else:
            current = self.Head
            while current.next is not None:
                current = current.next
            newNode = Node(element)
            current.next = newNode

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode

    def deleteFromBeginning(self):
        if self.Head is None:
            print("The linked list empty. Cannot delete an element.")
            return
        else:
            node = self.Head
            self.Head = self.Head.next
            del node

    def deleteFromLast(self):
        if self.Head is None:
            print("The linked list empty. Cannot delete an element.")
            return
        else:
            current = self.Head
            previous = None
            while current.next is not None:
                previous = current
                current = current.next
            previous.next = None
            del current

    def deleteAtPosition(self, position):
        if self.Head is None:
            print("The linked list empty. Cannot delete an element.")
            return
        else:
            current = self.Head
            previous = None
            count = 1
            while current.next is not None and count < position:
                previous = current
                current = current.next
                count += 1
            if current == self.Head:
                self.Head = current.next
                del current
            else:
                previous.next = current.next
                del current

    def countElements(self):
        count = 0
        current = self.Head
        while current is not None:
            count += 1
            current = current.next
        print("Number of elements in the linked list are:", count)

    def replaceElement(self, old_element, new_element):
        current = self.Head
        while current is not None:
            if current.data == old_element:
                current.data = new_element
                break
            current = current.next

    def updateAtPosition(self, new_element, position):
        if self.Head is None and position != 1:
            print("No element to update in the linked list.")
            return
        elif self.Head is None and position == 1:
            newNode = Node(new_element)
            self.Head = newNode
            return
        count = 1
        current = self.Head
        while current.next is not None and count < position:
            count += 1
            current = current.next
        if count == position:
            current.data = new_element
        elif current.next is None:
            print("Not enough elements in the linked list.")

结论

在本文中，我们讨论了链表数据结构及其在 Python 中的实现。我们还实现了链表中各种操作的方法。

在本文中，我们已经使用方法实现了所有操作。你还可以使用以链表的 Head 作为输入并在执行所需操作后返回头部的函数来实现每个操作。

但是，这将在执行期间需要更多资源。因此，我建议你使用本文中使用的方法。

作者： Aditya Raj

Aditya Raj is a highly skilled technical professional with a background in IT and business, holding an Integrated B.Tech (IT) and MBA (IT) from the Indian Institute of Information Technology Allahabad. With a solid foundation in data analytics, programming languages (C, Java, Python), and software environments, Aditya has excelled in various roles. He has significant experience as a Technical Content Writer for Python on multiple platforms and has interned in data analytics at Apollo Clinics. His projects demonstrate a keen interest in cutting-edge technology and problem-solving, showcasing his proficiency in areas like data mining and software development. Aditya's achievements include securing a top position in a project demonstration competition and gaining certifications in Python, SQL, and digital marketing fundamentals.

GitHub

什么是 Python 中的链表

在 Python 中如何创建链表

在 Python 中打印链表的所有元素

在 Python 中将元素插入到链表中

将元素插入空链表

在链表的开头插入元素

在链表末尾插入元素

在链表的给定位置插入元素

从 Python 中的链表中删除一个元素

删除链表的第一个元素

删除链表的最后一个元素

删除链表中任意给定位置的元素

在 Python 中计算链表中的元素数

在 Python 中更新链表中的节点

替换链表中的值

更新链表中给定位置的元素

在 Python 中为什么使用链表

Python 中的完整实现链表

结论

相关文章 - Python Data Structure