如何使用Python实现链表数据结构

# 1. 简介

链表（Linked List）是一种常见的数据结构，它使用一组节点来表示线性顺序。每个节点包含数据以及指向下一个节点的引用。链表与数组相比，具有更灵活的内存分配和插入/删除操作。

## 1.1 什么是链表数据结构

链表是由节点组成的数据结构，每个节点包含数据以及指向下一个节点的指针或引用。链表可以分为单向链表、双向链表和循环链表等不同类型。

## 1.2 为什么选择Python来实现链表

Python是一种简洁而强大的编程语言，具有丰富的内置数据类型和功能库。Python的易读性和灵活性使其成为实现数据结构（如链表）的理想选择。在Python中，可以轻松定义类来表示节点，并使用指针或引用来连接节点，实现链表的各种操作。

# 2. 单链表的实现

在本节中，我们将学习如何使用Python来实现单链表数据结构。单链表是一种基本的数据结构，它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。我们将分步骤实现单链表的基本操作，包括定义节点类、插入操作、删除操作等。

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

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

    def insert(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

    def delete(self, data):
        current = self.head
        previous = None
        found = False
        while current and not found:
            if current.data == data:
                found = True
            else:
                previous = current
                current = current.next
        if current is None:
            raise ValueError("Data not found in the list")
        if previous is None:
            self.head = current.next
        else:
            previous.next = current.next

    def display(self):
        elements = []
        current = self.head
        while current:
            elements.append(current.data)
            current = current.next
        return elements

# 示例
linked_list = LinkedList()
linked_list.insert(3)
linked_list.insert(4)
linked_list.insert(5)
print(linked_list.display())  # 输出: [3, 4, 5]

linked_list.delete(4)
print(linked_list.display())  # 输出: [3, 5]

上面的代码展示了如何定义Node类和LinkedList类，以及如何进行插入和删除操作。在示例部分，我们创建了一个单链表对象，并进行了插入和删除操作，并输出了操作后的链表元素。

这样实现的单链表具有简洁、清晰的结构，适合初学者理解和实践。接下来，我们将继续学习双向链表的实现。

# 3. 双向链表的实现

双向链表是一种链表数据结构，每个节点除了指向后继节点外，还指向前驱节点。在实现双向链表时，不仅可以从头部开始遍历，还可以从尾部开始遍历，这对于某些场景非常有用。

#### 3.1 定义节点类

在Python中，可以通过定义一个节