列表：单链表和双链表

5.1 列表的定义和种类

列表 是一种动态数据结构，由元素（节点）组成，每个节点包含数据和指向其他节点的链接。与数组不同，列表可以在程序执行过程中改变其大小。

重要! 在这里，我们不是在说Python中的list类，而是在谈论算法理论中的数据结构。

列表的种类：

• 单链表 (Singly Linked List): 每个节点包含数据和指向下一个节点的链接。
• 双链表 (Doubly Linked List): 每个节点包含数据，指向下一个节点和前一个节点的链接。

5.2 单链表的工作原理

单链表结构：

• 节点 (Node): 由两部分组成：数据和指向下一个节点的链接。
• 头部 (Head): 指向列表的第一个节点的指针。

工作原理：

• 添加节点: 通过创建新节点并更新最后一个节点的链接来实现。
• 删除节点: 需要更新前一个节点的链接以指向被删除节点的下一个节点。

实现示例：

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

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

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

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

# 使用示例:
sll = SinglyLinkedList()
sll.append(1)
sll.append(2)
sll.append(3)
sll.display()  # 输出: 1 -> 2 -> 3 -> None

5.3 双链表的工作原理

双链表结构：

• 节点 (Node): 由三部分组成：数据，指向下一个节点和前一个节点的链接。
• 头部 (Head): 指向列表的第一个节点的指针。
• 尾部 (Tail): 指向列表最后一个节点的指针（不是必须，但通常使用）。

工作原理：

• 添加节点: 通过创建新节点并更新最后一个节点和新节点的链接来实现。
• 删除节点: 需要更新被删除节点的前后节点的链接。

实现示例：

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

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

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        new_node.prev = last

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

# 使用示例:
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.display()  # 输出: 1 <-> 2 <-> 3 <-> None

5.4 基本操作

基本操作：插入，删除，查找

插入:

• 单链表: 在列表末尾插入新节点 需要遍历到最后一个节点 并更新最后一个节点的链接。
• 双链表: 在列表末尾插入新节点与单链表类似，还需要更新新节点的prev链接以指向前一个节点。

删除:

• 单链表: 删除节点 需要遍历列表到需要删除的节点，并更新前一个节点的链接以指向被删除节点的下一个节点。
• 双链表: 删除节点需要更新被删除节点的邻近节点的next和prev链接。

查找: 从头到尾遍历列表，比较每个节点的数据与查询值。时间复杂度是O(n)。

5.5 列表的使用示例

让我们实现一个基于单链表的栈作为例子。

栈可以通过单链表来轻松实现，使用push添加和pop删除元素的方法。它应该有两个方法：

• push — 添加新元素到列表末尾
• pop — 从列表末尾删除最后一个元素

实现示例：

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

class Stack:
    def __init__(self):
        self.top = None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.top
        self.top = new_node

    def pop(self):
        if not self.top:
            return None
        data = self.top.data
        self.top = self.top.next
        return data

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

# 使用示例:
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.display()  # 输出: 3 -> 2 -> 1 -> None
print(stack.pop())  # 输出: 3
stack.display()  # 输出: 2 -> 1 -> None