30 自定义数据结构的实现

在上一篇中，我们探讨了 Python 中集合与字典的高级用法，了解了如何利用这些内置数据结构来实现复杂的数据管理与处理。在这一篇中，我们将进一步深入，探讨如何通过自定义数据结构来满足特定需求。

自定义数据结构的优势在于它们可以根据特定的业务逻辑和数据处理需求来量身定制，提供比内置数据结构更高的灵活性和功能。

1. 自定义链表

链表是一种基础且灵活的数据结构，它由节点组成。每个节点包含数据和指向下一个节点的指针。我们先来实现一个简单的单向链表。

1.1 节点的定义

我们先定义一个节点类 Node，它包含数据和指向下一个节点的指针。

class Node:
    def __init__(self, data):
        self.data = data  # 节点数据
        self.next = None  # 下一个节点的指针

1.2 链表的定义

接下来，我们定义链表类 LinkedList，它提供一些基本操作，例如插入、删除和遍历。

class LinkedList:
    def __init__(self):
        self.head = None  # 链表头部

    def insert(self, data):
        new_node = Node(data)  # 创建新节点
        if not self.head:
            self.head = new_node  # 如果链表为空，则新节点为头节点
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next  # 寻找链表末尾
        last_node.next = new_node  # 将新节点插入链表末尾

    def delete(self, key):
        current = self.head
        if current and current.data == key:  # 如果要删除的是头节点
            self.head = current.next  # 更新头节点
            return
        prev = None
        while current and current.data != key:  # 寻找要删除的节点
            prev = current
            current = current.next
        if current is None:  # 如果节点不存在
            return
        prev.next = current.next  # 跳过要删除的节点

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

1.3 使用链表

现在我们可以使用这个自定义的链表了。

linked_list = LinkedList()
linked_list.insert(1)
linked_list.insert(2)
linked_list.insert(3)
linked_list.display()  # 输出: 1 -> 2 -> 3 -> None

linked_list.delete(2)
linked_list.display()  # 输出: 1 -> 3 -> None

2. 自定义栈

栈是一种后进先出（LIFO）的数据结构，可以使用链表或列表来实现。我们将自己实现一个简单的栈。

2.1 栈的定义

class Stack:
    def __init__(self):
        self.items = []  # 初始化一个空列表作为栈

    def push(self, item):
        self.items.append(item)  # 将元素压入栈中

    def pop(self):
        if not self.is_empty():
            return self.items.pop()  # 弹出栈顶元素
        return None  # 如果栈为空，返回 None

    def peek(self):
        if not self.is_empty():
            return self.items[-1]  # 返回栈顶元素，但不弹出
        return None

    def is_empty(self):
        return len(self.items) == 0  # 判断栈是否为空

    def size(self):
        return len(self.items)  # 返回栈的大小

2.2 使用栈

现在让我们使用自定义的栈。

stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)

print(stack.pop())  # 输出: 3
print(stack.peek())  # 输出: 2
print(stack.size())  # 输出: 2

3. 自定义队列

队列是一种先进先出（FIFO）的数据结构。我们可以使用列表或者链表来实现。

3.1 队列的定义

class Queue:
    def __init__(self):
        self.items = []  # 初始化一个空列表作为队列

    def enqueue(self, item):
        self.items.insert(0, item)  # 在队列前端插入元素

    def dequeue(self):
        if not self.is_empty():
            return self.items.pop()  # 从队列后端弹出元素
        return None  # 如果队列为空，返回 None

    def is_empty(self):
        return len(self.items) == 0  # 判断队列是否为空

    def size(self):
        return len(self.items)  # 返回队列的大小

3.2 使用队列

接下来，我们使用自定义的队列。

queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)

print(queue.dequeue())  # 输出: 1
print(queue.size())  # 输出: 2

4. 总结

在本篇中，我们探讨了如何通过实现自定义数据结构（如链表、栈和队列）来应对特定的编程需求。这些数据结构能够帮助我们更好地组织和管理数据，使得编程任务变得更加高效。

在下一篇中，我们将讨论更为复杂的自定义数据结构，例如树和图的实现，以及它们的应用场景。希望大家继续关注！