1.顺序表
概念
逻辑结构为线性连续，内存空间连续存放元素，依靠下标随机访问，查询速度快，中间插入、删除需要移动元素，效率偏低。
class SequenceList: def __init__(self): self.data = [] # 尾部添加元素 def append(self, val): self.data.append(val) # 指定下标插入 def insert(self, idx, val): self.data.insert(idx, val) # 根据下标删除 def remove(self, idx): if 0 <= idx < len(self.data): return self.data.pop(idx) raise IndexError("下标越界") # 获取下标元素 def get(self, idx): return self.data[idx] # 获取长度 def size(self): return len(self.data) # 打印所有元素 def show(self): print(self.data)
2.单链表
概念
线性链式存储结构，内存不连续，由一个个节点组成，节点存数据 + 下一个节点地址。没有下标无法随机访问，遍历查找慢；增删节点只需修改指针，效率极高。
# 链表节点类class Node: def __init__(self, val): self.val = val self.next = None# 单链表class SingleLinkList: def __init__(self): self.head = None # 尾部添加 def add_last(self, val): new_node = Node(val) if not self.head: self.head = new_node return cur = self.head while cur.next: cur = cur.next cur.next = new_node # 头部添加 def add_first(self, val): new_node = Node(val) new_node.next = self.head self.head = new_node # 删除头部元素 def pop_first(self): if not self.head: return None val = self.head.val self.head = self.head.next return val # 遍历输出 def traverse(self): res = [] cur = self.head while cur: res.append(cur.val) cur = cur.next print(res)
3.栈
概念
操作受限的线性表，遵循后进先出 LIFO 原则，只能在一端（栈顶）进行存入和取出，常用于递归、表达式求值、括号匹配。
class Stack: def __init__(self): self.stack = [] # 入栈 def push(self, val): self.stack.append(val) # 出栈 def pop(self): if not self.is_empty(): return self.stack.pop() # 查看栈顶元素 def peek(self): if not self.is_empty(): return self.stack[-1] # 判断是否为空 def is_empty(self): return len(self.stack) == 0
4.队列
概念
操作受限的线性表，遵循先进先出 FIFO 原则，一端入队、一端出队，任务排队、消息队列、广度优先搜索都用队列实现。
class Queue: def __init__(self): self.queue = [] # 入队 def enqueue(self, val): self.queue.append(val) # 出队 def dequeue(self): if not self.is_empty(): return self.queue.pop(0) # 判断空队列 def is_empty(self): return len(self.queue) == 0
线性结构总总结
共同特点：元素之间一对一线性前后关系
顺序表：查快改慢，内存连续
链表：改快查慢，内存分散
栈：后进先出
队列：先进先出
