Python 链表|极客教程

Python 链表

在计算机科学中，链表是一种常见的数据结构，用于存储一系列元素。链表包含一系列节点，每个节点包含一个值和指向下一个节点的指针。链表与数组相比具有一些优势，例如插入和删除操作更加高效，但是访问元素的速度相对较慢。在本文中，我们将讨论如何在Python中实现链表，并演示一些常见操作。

实现链表节点

首先，我们需要定义链表节点的结构。一个简单的链表节点可以包含一个值和一个指向下一个节点的指针。在Python中，我们可以使用类来表示链表节点。

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

在上面的代码中，我们定义了一个 Node 类，它具有一个构造函数 __init__，用来初始化节点的值和下一个节点的指针。

实现链表

接下来，我们可以定义链表类，其中包含一些常见的链表操作，例如插入、删除和遍历节点。

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

    def is_empty(self):
        return self.head is None

    def insert_at_beginning(self, value):
        new_node = Node(value)
        new_node.next = self.head
        self.head = new_node

    def insert_at_end(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            return
        current_node = self.head
        while current_node.next is not None:
            current_node = current_node.next
        current_node.next = new_node

    def delete(self, value):
        if self.head is None:
            return
        if self.head.value == value:
            self.head = self.head.next
            return
        current_node = self.head
        while current_node.next is not None:
            if current_node.next.value == value:
                current_node.next = current_node.next.next
                return
            current_node = current_node.next

    def display(self):
        current_node = self.head
        while current_node is not None:
            print(current_node.value, end=' ')
            current_node = current_node.next
        print()

在上面的代码中，我们定义了一个 LinkedList 类，它包含一些常见的链表操作。具体来说：

__init__：初始化链表的头节点。
is_empty：检查链表是否为空。
insert_at_beginning：在链表的头部插入一个新节点。
insert_at_end：在链表的尾部插入一个新节点。
delete：删除链表中指定值的节点。
display：遍历并打印链表中的所有节点的值。

使用链表

现在我们已经定义了链表类，让我们看看如何使用它。首先，我们创建一个空链表，并插入一些元素，然后遍历链表并删除一个元素。

# 创建一个链表
ll = LinkedList()

# 插入元素
ll.insert_at_beginning(3)
ll.insert_at_beginning(2)
ll.insert_at_end(4)
ll.insert_at_end(5)

# 遍历链表
ll.display()  # Output: 2 3 4 5

# 删除元素
ll.delete(3)

# 再次遍历链表
ll.display()  # Output: 2 4 5

在这个示例中，我们首先创建了一个空链表 ll，然后向链表中插入一些元素，并通过 display 方法打印出链表的内容。接着，我们使用 delete 方法删除了一个元素，并再次遍历链表以验证删除操作。