一、数组与列表：Python的基础线性结构

1.1 概念详解

数组 是一种线性数据结构，使用连续的内存空间存储相同类型的元素。在Python中，虽然没有传统意义上的静态数组，但列表(list)可以看作是动态数组的实现。

Python列表的核心特性：

  1. 动态大小：列表可以自动调整大小，无需手动管理内存

  2. 异构存储：可以存储不同类型的元素

  3. 连续内存：元素在内存中是连续存储的，支持快速随机访问

  4. 引用存储：列表存储的是对象的引用，而非对象本身

1.2 Python列表的底层实现

"""
Python列表的底层实现原理：
1. 列表对象包含三个主要部分：
   - 指向数组的指针
   - 列表长度（当前元素数量）
   - 列表容量（已分配的内存空间）
2. 当列表空间不足时，Python会分配一个更大的数组，并将原有元素复制过去
3. 扩容策略通常是按比例增长（如增加当前大小的1/8）
"""

# 演示列表扩容过程
import sys

def list_growth_demo():
    """展示列表扩容时内存的变化"""
    lst = []
    prev_capacity = 0
    
    print("列表扩容过程演示:")
    print("-" * 50)
    print(f"{'元素数量':<10} {'内存大小(字节)':<15} {'容量估计':<10}")
    print("-" * 50)
    
    for i in range(30):
        lst.append(i)
        current_size = sys.getsizeof(lst)
        
        # 估算容量（内存大小减去固定开销）
        if i == 0:
            capacity = 0
        else:
            # Python列表的固定开销大约是56字节
            capacity = (current_size - 56) // 8  # 每个引用8字节
        
        if capacity != prev_capacity:
            print(f"{i+1:<10} {current_size:<15} {capacity:<10} ← 扩容")
            prev_capacity = capacity
        else:
            print(f"{i+1:<10} {current_size:<15} {capacity:<10}")

list_growth_demo()

print("\n" + "="*60)
print("列表操作时间复杂度总结:")
print("="*60)
print("| 操作               | 时间复杂度 | 说明                   |")
print("|-------------------|------------|------------------------|")
print("| 索引访问 lst[i]    | O(1)       | 直接计算内存地址       |")
print("| 尾部追加 append()  | O(1)       | 平均时间复杂度         |")
print("| 头部插入 insert(0)| O(n)       | 需要移动所有元素       |")
print("| 中间插入 insert(i)| O(n)       | 需要移动i之后的元素    |")
print("| 删除尾部 pop()     | O(1)       |                        |")
print("| 删除头部 pop(0)    | O(n)       | 需要移动所有元素       |")
print("| 查找元素 in        | O(n)       | 线性查找               |")
print("| 切片 lst[i:j]      | O(k)       | k=j-i个元素            |")

1.3 例题1：询问学号

问题概述：有 n名同学陆陆续续进入教室。我们知道每名同学的学号（在 1 到 109 之间），按进教室的顺序给出。上课了，老师想知道第 i 个进入教室的同学的学号是什么。

import sys

def solve():
    """
    优化版解决方案
    核心优化点：
    1. 一次性读取所有输入
    2. 一次性输出所有结果
    3. 避免频繁的print调用
    """
    # 一次性读取所有数据
    data = sys.stdin.buffer.read().split()
    
    # 解析数据
    n = int(data[0])
    m = int(data[1])
    
    # 学号列表
    students = data[2:2+n]
    
    # 处理查询并构建输出
    out_lines = []
    # 使用索引直接访问，O(1)时间复杂度
    for i in data[2+n:2+n+m]:
        # i是bytes类型，转换为int索引
        idx = int(i) - 1
        # 直接使用bytes避免编码转换
        out_lines.append(students[idx])
    
    # 一次性输出
    sys.stdout.buffer.write(b'\n'.join(out_lines))

if __name__ == "__main__":
    solve()

二、栈（Stack）的深度解析与应用

2.1 栈的概念与原理

栈 是一种后进先出（LIFO - Last In First Out）的线性数据结构。想象一下一叠盘子，你只能从最上面取放盘子。

栈的核心操作：

  1. push - 入栈：将元素添加到栈顶

  2. pop - 出栈：移除并返回栈顶元素

  3. peek/top - 查看栈顶元素但不移除

  4. is_empty - 检查栈是否为空

  5. size - 获取栈中元素数量

栈的应用场景：

  • 函数调用栈

  • 表达式求值

  • 括号匹配

  • 浏览器前进后退

  • 撤销/重做功能

2.2 Python中栈的实现对比

"""
Python中实现栈的几种方式对比：
1. 使用列表：最简单，但头部操作效率低
2. 使用collections.deque：两端操作都高效
3. 使用queue.LifoQueue：线程安全版本
"""

# 方法1：使用Python列表实现栈
class ListStack:
    """使用列表实现的栈"""
    def __init__(self):
        self._items = []
    
    def push(self, item):
        """入栈 - O(1)"""
        self._items.append(item)
    
    def pop(self):
        """出栈 - O(1)"""
        if not self.is_empty():
            return self._items.pop()
        raise IndexError("栈为空")
    
    def peek(self):
        """查看栈顶 - O(1)"""
        if not self.is_empty():
            return self._items[-1]
        raise IndexError("栈为空")
    
    def is_empty(self):
        return len(self._items) == 0
    
    def size(self):
        return len(self._items)
    
    def __str__(self):
        return f"Stack({self._items})"

# 方法2：使用deque实现栈（推荐）
from collections import deque

class DequeStack:
    """使用deque实现的栈"""
    def __init__(self):
        self._items = deque()
    
    def push(self, item):
        """入栈 - O(1)"""
        self._items.append(item)
    
    def pop(self):
        """出栈 - O(1)"""
        if not self.is_empty():
            return self._items.pop()
        raise IndexError("栈为空")
    
    def peek(self):
        """查看栈顶 - O(1)"""
        if not self.is_empty():
            return self._items[-1]
        raise IndexError("栈为空")
    
    def is_empty(self):
        return len(self._items) == 0
    
    def size(self):
        return len(self._items)
    
    def __str__(self):
        return f"Stack({list(self._items)})"

# 方法3：使用链表实现栈
class Node:
    """链表节点"""
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedListStack:
    """使用链表实现的栈"""
    def __init__(self):
        self.top = None
        self._size = 0
    
    def push(self, item):
        """入栈 - O(1)"""
        new_node = Node(item)
        new_node.next = self.top
        self.top = new_node
        self._size += 1
    
    def pop(self):
        """出栈 - O(1)"""
        if self.is_empty():
            raise IndexError("栈为空")
        
        popped = self.top.data
        self.top = self.top.next
        self._size -= 1
        return popped
    
    def peek(self):
        """查看栈顶 - O(1)"""
        if self.is_empty():
            raise IndexError("栈为空")
        return self.top.data
    
    def is_empty(self):
        return self.top is None
    
    def size(self):
        return self._size
    
    def __str__(self):
        result = []
        current = self.top
        while current:
            result.append(str(current.data))
            current = current.next
        return " -> ".join(result) + " -> None"

# 性能对比测试
import time

def benchmark_stacks():
    """对比不同栈实现的性能"""
    print("栈实现性能对比测试")
    print("="*60)
    
    implementations = {
        "ListStack": ListStack,
        "DequeStack": DequeStack,
        "LinkedListStack": LinkedListStack
    }
    
    operations = 100000
    
    for name, StackClass in implementations.items():
        print(f"\n测试 {name}:")
        stack = StackClass()
        
        # 测试push性能
        start = time.time()
        for i in range(operations):
            stack.push(i)
        push_time = time.time() - start
        
        # 测试pop性能
        start = time.time()
        for i in range(operations):
            stack.pop()
        pop_time = time.time() - start
        
        print(f"  Push {operations}次: {push_time:.4f}秒")
        print(f"  Pop  {operations}次: {pop_time:.4f}秒")

benchmark_stacks()

print("\n" + "="*60)
print("结论：在Python中，使用deque实现栈是最佳选择")
print("="*60)

2.3 栈的经典应用例题

例题2：括号匹配验证器

问题概述：编写一个程序，检查字符串中的括号是否匹配。需要支持多种括号类型：圆括号()、方括号[]。

s = input().strip()  # 读取输入的字符串并去除首尾空格
n = len(s)  # 获取字符串长度
matched = [False] * n  # 创建一个布尔数组，标记每个位置的括号是否匹配成功
stack = []  # 存放 (位置, 字符) 的栈，用于跟踪未匹配的左括号

# 第一遍扫描：匹配括号
for i, ch in enumerate(s):
    # 如果是左括号，压入栈中
    if ch == '(' or ch == '[':
        stack.append((i, ch))
    # 如果是右括号
    elif ch == ')' or ch == ']':
        if stack:  # 如果栈不为空（存在未匹配的左括号）
            last_pos, last_ch = stack[-1]  # 获取栈顶元素（最近的未匹配左括号）
            # 检查括号类型是否匹配：小括号配小括号，中括号配中括号
            if (ch == ')' and last_ch == '(') or (ch == ']' and last_ch == '['):
                matched[last_pos] = True  # 标记左括号已匹配
                matched[i] = True  # 标记当前右括号已匹配
                stack.pop()  # 弹出栈顶（已匹配的左括号）
        # 如果栈为空或不匹配，右括号保持未匹配状态（matched[i]保持False）

# 第二遍扫描：构建结果字符串
result = []
for i, ch in enumerate(s):
    if not matched[i]:  # 如果该括号未匹配
        # 未匹配的括号可能是 '('、')'、'[' 或 ']'
        # 根据题目要求，在它旁边添加一个字符使其匹配
        if ch == '(' or ch == ')':
            # 对于小括号，无论原来是左括号还是右括号，都变成"()"
            result.append('(')
            result.append(')')
        else:  # '[' or ']'
            # 对于中括号，无论原来是左括号还是右括号，都变成"[]"
            result.append('[')
            result.append(']')
    else:  # 如果该括号已匹配，直接保留原字符
        result.append(ch)

# 输出结果
print(''.join(result))
例题3：后缀表达式计算器（逆波兰表达式）

问题概述：实现一个后缀表达式（逆波兰表达式）计算器。后缀表达式是一种不需要括号就能明确运算顺序的表达式表示法。

后缀表达式特点：

  • 操作符在操作数之后

  • 不需要括号来指定优先级

  • 计算顺序明确，易于计算机处理

示例：

  • 中缀表达式：(3 + 4) * 5

  • 后缀表达式：3 4 + 5 *

def e_p(exp):
    """计算后缀表达式（逆波兰表达式）的值"""
    stack = []  # 用于存放操作数的栈
    i = 0  # 字符串索引
    length = len(exp)  # 表达式长度
    
    while i < length:
        # 遇到 '@' 表示表达式结束
        if exp[i] == '@':
            break
            
        # 遇到 '.' 是分隔符，跳过
        if exp[i] == '.':
            i += 1
            continue
            
        # 处理数字（可能是多位数）
        if exp[i].isdigit():
            num_str = ''  # 构建数字字符串
            # 连续读取数字字符，直到遇到非数字
            while i < length and exp[i].isdigit():
                num_str += exp[i]
                i += 1
            # 将数字字符串转换为整数并压入栈中
            stack.append(int(num_str))
            continue  # 已经更新了i，继续下一次循环
            
        # 处理运算符
        if exp[i] in '+-*/':
            # 弹出栈顶两个操作数（注意顺序：先弹出的是右操作数）
            right = stack.pop()  # 右操作数
            left = stack.pop()   # 左操作数
            
            # 根据运算符进行计算
            if exp[i] == '+':
                result = left + right
            elif exp[i] == '-':
                result = left - right
            elif exp[i] == '*':
                result = left * right
            elif exp[i] == '/':
                # 特殊处理除法：C++风格的整数除法（向零取整）
                # 当两个数同号时，正常整除
                if left * right >= 0:
                    result = left // right
                else:
                    # 异号时，确保结果向零取整
                    if left < 0:
                        result = -((-left) // right)
                    else:
                        result = -(left // (-right))
            
            # 计算结果压入栈中
            stack.append(result)
            i += 1
            continue
            
        # 如果不是以上情况，移动到下一个字符
        i += 1
        
    # 栈中剩下的唯一元素就是表达式的结果
    return stack[0]

# 主程序
exp = input()  # 读取后缀表达式
result = e_p(exp)  # 计算表达式值
print(result)  # 输出结果

三、队列（Queue）的深度解析与应用

3.1 队列的概念与原理

队列 是一种先进先出（FIFO - First In First Out）的线性数据结构。想象一下排队购票，先来的人先服务。

队列的核心操作：

  1. enqueue - 入队：将元素添加到队尾

  2. dequeue - 出队：移除并返回队首元素

  3. front/peek - 查看队首元素但不移除

  4. is_empty - 检查队列是否为空

  5. size - 获取队列中元素数量

队列的类型：

  1. 普通队列：基本FIFO队列

  2. 双端队列（deque）：两端都可以入队和出队

  3. 优先队列：元素按优先级出队

  4. 循环队列：使用固定大小的数组实现

队列的应用场景：

  • 消息队列

  • 任务调度

  • 广度优先搜索

  • 打印机任务队列

  • 网络数据包缓冲

3.2 Python中队列的实现

"""
Python中队列实现的几种方式：
1. 使用列表：简单但不高效（pop(0)是O(n)操作）
2. 使用collections.deque：推荐，两端操作都是O(1)
"""

from collections import deque
import queue

# 1. 使用列表实现队列（不推荐用于生产环境）
class ListQueue:
    """使用列表实现的队列（教学用途）"""
    def __init__(self):
        self._items = []
    
    def enqueue(self, item):
        """入队 - O(1)"""
        self._items.append(item)
    
    def dequeue(self):
        """出队 - O(n)！效率低"""
        if not self.is_empty():
            return self._items.pop(0)
        raise IndexError("队列为空")
    
    def front(self):
        """查看队首 - O(1)"""
        if not self.is_empty():
            return self._items[0]
        raise IndexError("队列为空")
    
    def is_empty(self):
        return len(self._items) == 0
    
    def size(self):
        return len(self._items)
    
    def __str__(self):
        return f"Queue({self._items})"

# 2. 使用deque实现队列（推荐）
class DequeQueue:
    """使用deque实现的高效队列"""
    def __init__(self):
        self._items = deque()
    
    def enqueue(self, item):
        """入队 - O(1)"""
        self._items.append(item)
    
    def dequeue(self):
        """出队 - O(1)"""
        if not self.is_empty():
            return self._items.popleft()
        raise IndexError("队列为空")
    
    def front(self):
        """查看队首 - O(1)"""
        if not self.is_empty():
            return self._items[0]
        raise IndexError("队列为空")
    
    def is_empty(self):
        return len(self._items) == 0
    
    def size(self):
        return len(self._items)
    
    def __str__(self):
        return f"Queue({list(self._items)})"
    
    def clear(self):
        """清空队列"""
        self._items.clear()
    
    def rotate(self, n=1):
        """旋转队列"""
        self._items.rotate(n)

print("\n" + "="*60)
print("队列实现选择指南:")
print("="*60)
print("1. 普通队列需求 → collections.deque")
print("2. 线程安全需求 → queue.Queue")
print("3. 异步编程需求 → asyncio.Queue")
print("4. 优先级调度需求 → heapq 或 queue.PriorityQueue")
print("5. 固定内存需求 → 自定义循环队列")
print("6. 教学/演示用途 → 列表实现（理解原理）")

3.3 队列的经典应用例题

例题4：约瑟夫问题

n 个人围成一圈，从第一个人开始报数,数到 m 的人出列，再由下一个人重新从 1 开始报数，数到 m 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。

# 约瑟夫环问题
# 输入总人数n和报数间隔m
n, m = map(int, input().split())

# 创建初始人员列表 [1, 2, 3, ..., n]
people = list(range(1, n + 1))

i = 1  # 当前报数计数器
index = 0  # 当前人员索引
result = []  # 存储出列顺序的结果列表

# 当还有人员未出列时继续循环
while len(result) < n:
    # 如果当前报数等于m
    if i == m:
        # 将当前人员加入结果列表
        result.append(people[index])
        # 从人员列表中移除该人员
        people.pop(index)
        # 重置报数计数器
        i = 1
        
        # 如果人员列表为空，结束循环
        if not people:
            break
            
        # 如果索引超出列表范围，回到开头（处理边界情况）
        if index >= len(people):
            index = 0
    else:
        # 报数加1
        i += 1
        # 移动到下一个人，使用取模运算实现循环
        index = (index + 1) % len(people)

# 输出结果，用空格分隔
print(' '.join(map(str, result)))

# 算法说明：
# 1. 这是一个约瑟夫环问题的模拟解法
# 2. 每次报数到m的人出列，然后从下一个人继续报数
# 3. 使用取模运算实现环形遍历
# 4. 时间复杂度：O(n*m)，空间复杂度：O(n)

四、链表的深度解析与应用

4.1 链表的核心概念与原理

链表 是一种非连续存储的线性数据结构，通过节点和指针（引用）实现。每个节点包含数据和指向下一个节点的指针。

链表的优缺点：
优点：
1. 动态大小，不需要预先分配内存
2. 插入和删除操作高效（O(1)时间复杂度，如果知道位置）
3. 不需要连续内存空间
4. 内存利用率高（按需分配）

缺点：
1. 随机访问低效（O(n)时间复杂度）
2. 需要额外的内存存储指针
3. 缓存不友好（节点分散在内存中）
4. 反向遍历困难（单向链表）

4.1.1 链表的类型与特点

"""
链表的主要类型：
1. 单向链表：每个节点只包含指向下一个节点的引用
2. 双向链表：每个节点包含指向前一个和后一个节点的引用
"""

# 节点基类
class BaseNode:
    """链表节点基类"""
    def __init__(self, data):
        self.data = data
        self._id = id(self)  # 用于调试
    
    def __repr__(self):
        return f"Node(data={self.data}, id={self._id % 1000:03d})"

# 单向链表节点
class SinglyNode(BaseNode):
    def __init__(self, data):
        super().__init__(data)
        self.next = None
    
    def __str__(self):
        next_id = id(self.next) % 1000 if self.next else "None"
        return f"SNode(data={self.data}, next={next_id:03d})"

# 双向链表节点
class DoublyNode(BaseNode):
    def __init__(self, data):
        super().__init__(data)
        self.prev = None
        self.next = None
    
    def __str__(self):
        prev_id = id(self.prev) % 1000 if self.prev else "None"
        next_id = id(self.next) % 1000 if self.next else "None"
        return f"DNode(data={self.data}, prev={prev_id:03d}, next={next_id:03d})"

4.2 链表的完整实现

4.2.1 单向链表完整实现

class SinglyLinkedList:
    """
    单向链表完整实现
    包含完整的增删改查操作和实用方法
    """
    
    class Node:
        """单向链表节点"""
        __slots__ = ('data', 'next')  # 减少内存占用
        
        def __init__(self, data):
            self.data = data
            self.next = None
        
        def __repr__(self):
            return f"Node({self.data})"
    
    def __init__(self, iterable=None):
        """
        初始化链表
        
        Args:
            iterable: 可迭代对象，用于初始化链表
        """
        self.head = None
        self.tail = None
        self.length = 0
        self._current = None  # 用于迭代
        
        if iterable:
            for item in iterable:
                self.append(item)
    
    def is_empty(self):
        """检查链表是否为空"""
        return self.head is None
    
    def insert(self, data, position):
        """
        在指定位置插入元素
        
        Args:
            data: 要插入的数据
            position: 插入位置（0-based索引）
            
        时间复杂度: O(n)
        """
        if position < 0 or position > self.length:
            raise IndexError(f"位置 {position} 超出范围 [0, {self.length}]")
        
        if position == 0:
            return self.prepend(data)
        
        if position == self.length:
            return self.append(data)
        
        new_node = self.Node(data)
        current = self.head
        
        # 移动到插入位置的前一个节点
        for _ in range(position - 1):
            current = current.next
        
        new_node.next = current.next
        current.next = new_node
        self.length += 1
        
        return new_node
    
    def delete(self, position):
        """
        删除指定位置的元素
        
        Args:
            position: 要删除的位置（0-based索引）
            
        Returns:
            被删除节点的数据
            
        时间复杂度: O(n)
        """
        if self.is_empty():
            raise IndexError("链表为空")
        
        if position < 0 or position >= self.length:
            raise IndexError(f"位置 {position} 超出范围 [0, {self.length-1}]")
        
        # 删除头部节点
        if position == 0:
            data = self.head.data
            self.head = self.head.next
            if self.head is None:  # 如果链表为空
                self.tail = None
            self.length -= 1
            return data
        
        # 查找要删除节点的前一个节点
        current = self.head
        for _ in range(position - 1):
            current = current.next
        
        # 删除节点
        data = current.next.data
        current.next = current.next.next
        
        # 如果删除的是尾部节点，更新尾指针
        if current.next is None:
            self.tail = current
        
        self.length -= 1
        return data
    
    
    def get(self, position):
        """
        获取指定位置的元素
        
        时间复杂度: O(n)
        """
        if position < 0 or position >= self.length:
            raise IndexError(f"位置 {position} 超出范围 [0, {self.length-1}]")
        
        current = self.head
        for _ in range(position):
            current = current.next
        
        return current.data
    
    def index(self, data):
        """
        查找元素的第一个位置
        
        Returns:
            元素的索引，如果未找到则返回-1
            
        时间复杂度: O(n)
        """
        current = self.head
        index = 0
        
        while current:
            if current.data == data:
                return index
            current = current.next
            index += 1
        
        return -1
    
    def contains(self, data):
        """检查是否包含元素"""
        return self.index(data) != -1
    
    def to_list(self):
        """将链表转换为Python列表"""
        result = []
        current = self.head
        while current:
            result.append(current.data)
            current = current.next
        return result
    
    def clear(self):
        """清空链表"""
        self.head = None
        self.tail = None
        self.length = 0
    
    def __delitem__(self, position):
        self.delete(position)
    
    def __contains__(self, data):
        return self.contains(data)

    def __iter__(self):
        self._current = self.head
        return self
    
    def __next__(self):
        if self._current is None:
            raise StopIteration
        data = self._current.data
        self._current = self._current.next
        return data
    
    def __repr__(self):
        if self.is_empty():
            return "SinglyLinkedList([])"
        
        elements = []
        current = self.head
        
        return f"SinglyLinkedList([{', '.join(elements)}])"

    

# 单向链表使用示例
def demo_singly_linked_list():
    """演示单向链表的使用"""
    print("单向链表演示")
    print("="*80)
    
    # 1. 创建和初始化
    print("1. 创建和初始化链表:")
    lst = SinglyLinkedList([1, 2, 3, 4, 5])
    print(f"   初始链表: {lst}")
    print(f"   长度: {len(lst)}")
    
    # 2. 基本操作
    print("\n2. 基本操作:")
    
    # 添加元素
    lst.insert(3.5, 4)  # 在位置4插入3.5
    print(f"   添加元素后: {lst}")
    
    # 访问元素
    print(f"   第二个元素: {lst[1]}")
    print(f"   最后一个元素: {lst[len(lst)-1]}")
    print(f"   中间元素: {lst.get_middle()}")
    
    # 3. 删除操作
    print("\n3. 删除操作:")
    deleted = lst.delete(4)  # 删除位置4的元素
    print(f"   删除位置4的元素 ({deleted}) 后: {lst}")
    
    lst.remove(0)  # 删除值为0的元素
    print(f"   删除值为0的元素后: {lst}")
    
    # 4. 查找和包含检查
    print("\n4. 查找和包含检查:")
    print(f"   元素3的位置: {lst.index(3)}")
    print(f"   是否包含10: {10 in lst}")
    print(f"   是否包含5: {5 in lst}")
    

demo_singly_linked_list()

4.2.2 双向链表完整实现

class DoublyLinkedList:
    """
    双向链表完整实现
    支持正向和反向遍历
    """
    
    class Node:
        """双向链表节点"""
        __slots__ = ('data', 'prev', 'next')
        
        def __init__(self, data):
            self.data = data
            self.prev = None
            self.next = None
        
        def __repr__(self):
            return f"DNode({self.data})"
    
    def __init__(self, iterable=None):
        """初始化双向链表"""
        self.head = None
        self.tail = None
        self.length = 0
        
        if iterable:
            for item in iterable:
                self.append(item)
    
    def is_empty(self):
        """检查链表是否为空"""
        return self.head is None
    
    def insert(self, data, position):
        """在指定位置插入元素"""
        if position < 0 or position > self.length:
            raise IndexError(f"位置 {position} 超出范围")
        
        if position == 0:
            return self.prepend(data)
        
        if position == self.length:
            return self.append(data)
        
        # 找到插入位置的节点
        if position < self.length // 2:
            # 从前向后找
            current = self.head
            for _ in range(position):
                current = current.next
        else:
            # 从后向前找
            current = self.tail
            for _ in range(self.length - position - 1):
                current = current.prev
        
        # 插入新节点
        new_node = self.Node(data)
        new_node.prev = current.prev
        new_node.next = current
        current.prev.next = new_node
        current.prev = new_node
        
        self.length += 1
        return new_node
    
    def delete(self, position):
        """删除指定位置的元素"""
        if self.is_empty():
            raise IndexError("链表为空")
        
        if position < 0 or position >= self.length:
            raise IndexError(f"位置 {position} 超出范围")
        
        # 找到要删除的节点
        if position < self.length // 2:
            current = self.head
            for _ in range(position):
                current = current.next
        else:
            current = self.tail
            for _ in range(self.length - position - 1):
                current = current.prev
        
        # 删除节点
        data = current.data
        
        if current.prev:
            current.prev.next = current.next
        else:  # 删除的是头节点
            self.head = current.next
        
        if current.next:
            current.next.prev = current.prev
        else:  # 删除的是尾节点
            self.tail = current.prev
        
        # 清理引用
        current.prev = None
        current.next = None
        
        self.length -= 1
        return data

    def get(self, position):
        """获取指定位置的元素"""
        if position < 0 or position >= self.length:
            raise IndexError(f"位置 {position} 超出范围")
        
        # 根据位置选择遍历方向
        if position < self.length // 2:
            current = self.head
            for _ in range(position):
                current = current.next
        else:
            current = self.tail
            for _ in range(self.length - position - 1):
                current = current.prev
        
        return current.data
    
    def forward_traversal(self):
        """正向遍历生成器"""
        current = self.head
        while current:
            yield current.data
            current = current.next
    
    def backward_traversal(self):
        """反向遍历生成器"""
        current = self.tail
        while current:
            yield current.data
            current = current.prev
    
    def to_list(self, reverse=False):
        """转换为Python列表"""
        if reverse:
            return list(self.backward_traversal())
        return list(self.forward_traversal())
    
    def clear(self):
        """清空链表"""
        # 断开所有节点的引用，帮助垃圾回收
        current = self.head
        while current:
            next_node = current.next
            current.prev = None
            current.next = None
            current = next_node
        
        self.head = None
        self.tail = None
        self.length = 0
    
    def __len__(self):
        return self.length
    
    def __getitem__(self, position):
        return self.get(position)
    
    def __iter__(self):
        return self.forward_traversal()
    
    def __repr__(self):
        if self.is_empty():
            return "DoublyLinkedList([])"
        
        elements = []
        current = self.head
        while current:
            elements.append(repr(current.data))
            current = current.next
        
        return f"DoublyLinkedList([{', '.join(elements)}])"

# 双向链表使用示例
def demo_doubly_linked_list():
    """演示双向链表的使用"""
    print("\n" + "="*80)
    print("双向链表演示")
    print("="*80)
    
    # 1. 创建和初始化
    dll = DoublyLinkedList([1, 2, 3, 4, 5])
    print(f"初始双向链表: {dll}")
    print(f"长度: {len(dll)}")
    
    # 2. 正向和反向遍历
    print("\n正向遍历:")
    for item in dll:
        print(f"  {item}", end="")
    print()
    
    print("反向遍历:")
    for item in dll.backward_traversal():
        print(f"  {item}", end="")
    print()
    
    # 3. 插入和删除
    dll.insert(2.5, 2)
    print(f"\n在位置2插入2.5后: {dll}")
    
    dll.delete(3)
    print(f"删除位置3的元素后: {dll}")
    
    # 4. 转换为列表
    print(f"\n正向列表: {dll.to_list()}")
    print(f"反向列表: {dll.to_list(reverse=True)}")
    
demo_doubly_linked_list()

4.3 链表的经典应用例题

例题5：队列安排

一个学校里老师要将班上 N 个同学排成一列，同学被编号为 1∼N，他采取如下的方法：

  1. 先将 1 号同学安排进队列，这时队列中只有他一个人；

  2. 2∼N 号同学依次入列，编号为 i 的同学入列方式为：老师指定编号为 i 的同学站在编号为 1∼(i−1) 中某位同学（即之前已经入列的同学）的左边或右边；

  3. 从队列中去掉 M 个同学，其他同学位置顺序不变。

在所有同学按照上述方法队列排列完毕后，老师想知道从左到右所有同学的编号。

class Node:
    """双向链表节点"""
    def __init__(self, value):
        self.value = value
        self.prev = None  # 前驱指针
        self.next = None  # 后继指针

class DoublyLinkedList:
    """双向链表"""
    def __init__(self):
        self.head = None   # 链表头节点
        self.tail = None   # 链表尾节点
        self.node_map = {}  # 值到节点的映射，用于快速查找
        
    def insert_after(self, target_value, new_value):
        """在目标节点后插入新节点"""
        # 通过映射快速找到目标节点
        target_node = self.node_map[target_value]
        # 创建新节点
        new_node = Node(new_value)
        
        # 设置新节点的前驱和后继
        new_node.prev = target_node
        new_node.next = target_node.next
        
        # 如果目标节点不是尾节点
        if target_node.next:
            target_node.next.prev = new_node
        else:
            # 如果目标节点是尾节点，更新尾节点为新节点
            self.tail = new_node
            
        # 更新目标节点的后继
        target_node.next = new_node
        # 更新映射
        self.node_map[new_value] = new_node
        
    def insert_before(self, target_value, new_value):
        """在目标节点前插入新节点"""
        target_node = self.node_map[target_value]
        new_node = Node(new_value)
        
        # 设置新节点的前驱和后继
        new_node.next = target_node
        new_node.prev = target_node.prev
        
        # 如果目标节点不是头节点
        if target_node.prev:
            target_node.prev.next = new_node
        else:
            # 如果目标节点是头节点，更新头节点为新节点
            self.head = new_node
            
        # 更新目标节点的前驱
        target_node.prev = new_node
        # 更新映射
        self.node_map[new_value] = new_node
        
    def remove(self, value):
        """删除节点"""
        # 如果值不在映射中，直接返回
        if value not in self.node_map:
            return
            
        node = self.node_map[value]
        
        # 处理前驱节点
        if node.prev:
            node.prev.next = node.next
        else:
            # 如果删除的是头节点，更新头节点
            self.head = node.next
            
        # 处理后继节点
        if node.next:
            node.next.prev = node.prev
        else:
            # 如果删除的是尾节点，更新尾节点
            self.tail = node.prev
            
        # 从映射中删除
        del self.node_map[value]
        
    def to_list(self):
        """转换为列表"""
        result = []
        current = self.head
        # 遍历链表
        while current:
            result.append(current.value)
            current = current.next
        return result

# 主程序开始
# 读取学生总数
n = int(input())
# 创建双向链表
dll = DoublyLinkedList()

# 插入第一个学生
first_node = Node(1)
dll.head = first_node
dll.tail = first_node
dll.node_map[1] = first_node

# 读取并执行插入操作
operations = []
# 从第2个学生开始到第n个学生
for i in range(2, n + 1):
    # k: 基准学生编号，p: 插入位置(0表示左边，1表示右边)
    k, p = map(int, input().split())
    operations.append((i, k, p))

# 执行所有插入操作
for i, k, p in operations:
    if p == 0:  # 插入到左边
        dll.insert_before(k, i)
    else:  # 插入到右边
        dll.insert_after(k, i)

# 读取删除操作
m = int(input())
to_delete = set()  # 使用集合提高查找效率
for _ in range(m):
    to_delete.add(int(input()))

# 执行删除
for x in to_delete:
    dll.remove(x)

# 输出结果
result = dll.to_list()
print(' '.join(map(str, result)))

# 算法说明：
# 1. 使用双向链表模拟排队过程
# 2. 通过node_map实现O(1)时间复杂度的节点查找
# 3. 插入操作：
#    - insert_after: 在目标节点后插入，时间复杂度O(1)
#    - insert_before: 在目标节点前插入，时间复杂度O(1)
# 4. 删除操作：时间复杂度O(1)
# 5. 整体时间复杂度：O(n+m)，其中n是学生总数，m是删除操作数
# 6. 空间复杂度：O(n)

# 应用场景：
# 1. 学生排队问题
# 2. 需要频繁在指定位置插入和删除的场景
# 3. 需要保持元素顺序的数据结构

总结

通过以上详细讲解和实现，我们深入探讨了Python中线性数据结构（数组/列表、栈、队列、链表）的各个方面：

核心要点总结：

  1. 数组/列表：Python的基石，动态数组实现，随机访问高效

  2. 栈：后进先出，适合函数调用、括号匹配、撤销操作

  3. 队列：先进先出，适合任务调度、消息队列、广度优先搜索

  4. 链表：动态存储，插入删除高效，适合LRU缓存、多项式运算

选择指南：

  • 需要随机访问 → 使用列表

  • 需要后进先出 → 使用栈（deque实现）

  • 需要先进先出 → 使用队列（deque实现）

  • 需要频繁插入删除 → 考虑链表

  • 需要线程安全 → 使用queue模块

  • 需要优先级调度 → 使用优先队列

# python # 数据结构
Logo
乐奇 Rokid 开放社区

更多推荐

cover

智慧矿山人员定位AR巡检品牌推荐

avatar 乐奇 Rokid 开放社区
cover

水务集团AR巡检系统选哪家公司好

avatar 乐奇 Rokid 开放社区

极刻觅镜 | AI眼镜周报｜智能眼镜声学性能测试规范10月2日起实施

本周智能眼镜领域出现多项进展：国内《智能眼镜声学性能测试规范》自10月2日起实施，高通发布Snapdragon Sound Elite Gen 2平台，Meta与Naver合作推进免手持步行导航，依视路陆逊梯卡与Meta扩充产品线，影目INMO就海外版发热问题发布声明，荷兰零售商停售Meta眼镜并引发监管关注。

avatar 乐奇 Rokid 开放社区