栈与队列

数据结构教程 · 第 3 章 · 8 次浏览

链表由一个个节点组成，每个节点存数据和下一个节点的指针，像珠子串起来。它不要求内存连续。

特点

插入删除快 O(1)（已知位置，改指针即可）
按下标访问慢 O(n)（要一个个找过去）
每个节点多一个指针，内存开销大

类型

单向链表（next）、双向链表（prev+next，Python deque 就是）、循环链表（尾指头）。

代码示例

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

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

    def append(self, data):          # 尾部插入 O(n)
        if not self.head:
            self.head = Node(data)
            return
        cur = self.head
        while cur.next:
            cur = cur.next
        cur.next = Node(data)

    def insert_after(self, node, data):   # 已知位置插入 O(1)
        new = Node(data)
        new.next = node.next
        node.next = new

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

ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.display()          # 1 -> 2 -> 3 -> None

📚 Python 语法速查

常用条目速查，完整版见对应教程章节。可复制代码到在线运行中测试。

写法 / 语法	作用
`print("hello")`	输出到控制台
`name = "张三"`	变量赋值（无需声明类型）
`if x > 0: ...`	条件判断（注意冒号和缩进）
`for i in range(10): ...`	循环（缩进是语法的一部分）
`while x < 10: ...`	条件循环
`def fn(a, b): return a + b`	定义函数
`class Person: ...`	定义类
`list = [1, 2, 3]`	列表（可改）
`tuple = (1, 2)`	元组（不可改）
`dict = {"key": "value"}`	字典（键值对）
`set = {1, 2, 3}`	集合（去重）
`len(obj)`	取长度
`str(x) / int(x) / float(x)`	类型转换
`s.split(",")`	字符串按分隔符拆分
`" ".join(list)`	列表拼接成字符串
`import os`	导入模块
`from math import sqrt`	从模块导入指定函数
`try: ... except Exception as e: ...`	异常捕获
`with open("a.txt", "r") as f: ...`	文件读取（自动关闭）
`f"你好 {name}"`	f-string 格式化
`lambda x: x * 2`	匿名函数
`list(map(fn, arr))`	函数式处理列表
`range(start, stop, step)`	生成数字序列
`if __name__ == "__main__":`	主入口判断
`pip install 包名`	安装第三方包（命令行）