网站首页 > 教程文章 正文
数据结构必修：链表核心操作与 LRU 设计，一篇图解吃透
1. 引言：为什么先学链表再学 LRU？
**链表（Linked List）**是“指针思维”的练兵场：
- o 数组：随机访问快 O(1)，但在中间插入/删除可能要整体搬移，最坏 O(n)；
- o 链表：随机访问慢（得一个个往后找），但已知位置的插入/删除是 O(1)。
这正是 LRU 缓存（Least Recently Used，最近最少使用）需要的：访问后要把数据快速移动到“最新”位置，淘汰时快速删除“最旧”。工业界标准解是：哈希表 + 双向链表。
3. 链表从直观到正式：你到底在操作什么？
- o 直观比喻：链表像一列“车厢”，每节车厢用“手”（指针）拉住下一节。
- o 节点（Node）：由 value（数据）和指针域组成。
- o 单链表：只有 next；
- o 双向链表：有 prev 和 next，能从中间 O(1) 删除/插入。
- o 哨兵（dummy）节点：在链表两端放“虚拟头/尾”节点（不存业务数据），可以统一边界、减少 if 分支，避免“删头/删尾”的特殊情况。
4. 单链表：7 个必会操作（边界 + 不变式）
不变式（Invariant）：
- 1. 插/删时链不断；
- 2. 需要改 head/tail 时一起维护；
- 3. 任何访问前先判空；
- 4. 指针赋值有顺序：先建立新连接，再断旧连接。
常用操作：
- 1. 头插：new.next = head; head = new
- 2. 尾插：维护 tail 可 O(1)；否则要遍历到末尾
- 3. 按位插入：找到 pos 的前驱 prev，做 prev -> new -> prev.next
- 4. 按值删除：找 prev，断 prev.next 指针
- 5. 查找：顺序遍历
- 6. 反转：三指针（prev/curr/next）迭代
- 7. 检测环：快慢指针（Floyd 判圈）
5. 双向链表 & 哨兵：把复杂边界变简单
- o 双向链表删除中间节点（已知节点）：
node.prev.next = node.next; node.next.prev = node.prev
不需要再去找 prev，从而保证 O(1)。 - o 哨兵节点：
在首尾放 dummyHead/dummyTail，链表永远“不空”，从而把 addToHead/removeTail 等操作统一化，是 LRU 代码健壮的关键。
6. LRU 缓存的经典设计
目标：固定容量 capacity，实现 get(key) 与 put(key, value)；访问命中后将该数据移动到“最新”，满容时淘汰“最久未使用”。
朴素方案：用数组每次移动位置，代价大；若用队列，很难从中间 O(1) 删除。
工业标准：哈希表（key → node） + 双向链表（维护“新鲜度顺序”）
- o get：命中返回值，并 moveToHead(node)；
- o put：存在则更新并 moveToHead；不存在则 addToHead，若超容则 removeTail；
- o 四个原子操作：addToHead / removeNode / moveToHead / removeTail；
- o 复杂度：get/put 均摊 O(1)，空间 O(capacity)。
7. 复杂度对照与工程落地建议
结构/操作访问第 k 个已知位置插入已知节点删除反转判环数组O(1)O(n)（可能搬移）O(n)O(n)—单链表O(n)O(1)（已知前驱）O(1)（已知前驱）O(n) / O(1) 空间O(n) / O(1) 空间双向链表O(n)O(1)O(1)（不找前驱）O(n)O(n)LRU（哈希+双链）O(1)O(1)O(1)——
工程建议：
o 随机访问密集：数组/动态数组；o 中间插删频繁：双向链表；o 缓存淘汰策略：LRU（哈希 + 双链 + 哨兵）。
8. Swift 实战
8.1 单链表工具
// 语言：Swift
import Foundation
/// 单链表节点（引用类型，便于指针操作）
final class SListNode<T> {
var val: T
var next: SListNode<T>?
init(_ val: T, _ next: SListNode<T>? = nil) {
self.val = val
self.next = next
}
}
enum SinglyLinkedList {
/// 从数组构建链表
static func build<T>(_ arr: [T]) -> SListNode<T>? {
let dummy = SListNode<T?>(nil)
var tail: SListNode<T?>? = dummy
for v in arr {
tail?.next = SListNode<T?>(v)
tail = tail?.next
}
return map(dummy.next) { $0! }
}
/// 打印 [a -> b -> c]
static func printList<T>(_ head: SListNode<T>?) {
var cur = head
var parts: [String] = []
while let node = cur {
parts.append("\(node.val)")
cur = node.next
}
print("[\(parts.joined(separator: " -> "))]")
}
/// 头插：返回新 head
static func pushFront<T>(_ head: SListNode<T>?, _ val: T) -> SListNode<T> {
let node = SListNode(val)
node.next = head
return node
}
/// 尾插：返回 head
static func pushBack<T>(_ head: SListNode<T>?, _ val: T) -> SListNode<T> {
let node = SListNode(val)
guard let head = head else { return node }
var cur: SListNode<T>? = head
while cur?.next != nil { cur = cur?.next }
cur?.next = node
return head
}
/// 在索引 pos 后插入（pos >= -1；pos == -1 表示头插）
static func insertAfter<T>(_ head: SListNode<T>?, pos: Int, val: T) -> SListNode<T> {
if pos < 0 { return pushFront(head, val) }
guard let head = head else { return SListNode(val) }
var cur: SListNode<T>? = head
var idx = 0
while idx < pos, cur?.next != nil {
cur = cur?.next
idx += 1
}
let node = SListNode(val)
node.next = cur?.next
cur?.next = node
return head
}
/// 按值删除首个等于 val 的节点
static func removeFirst<T: Equatable>(_ head: SListNode<T>?, _ val: T) -> SListNode<T>? {
var head = head
if head?.val == val { return head?.next }
var prev = head
while let next = prev?.next {
if next.val == val {
prev?.next = next.next
break
}
prev = next
}
return head
}
/// 反转链表（迭代三指针）
static func reverse<T>(_ head: SListNode<T>?) -> SListNode<T>? {
var prev: SListNode<T>? = nil
var cur = head
while let node = cur {
let nxt = node.next
node.next = prev
prev = node
cur = nxt
}
return prev
}
/// 判环（Floyd）
static func hasCycle<T>(_ head: SListNode<T>?) -> Bool {
var slow = head
var fast = head
while let f1 = fast, let f2 = f1.next {
slow = slow?.next
fast = f2.next
if slow === fast { return true }
}
return false
}
// helper：Optional<T> 链表 → T 链表
private static func map<T>(_ head: SListNode<T?>?, _ f: (T?) -> T) -> SListNode<T>? {
guard let head = head else { return nil }
let newHead = SListNode<T>(f(head.val))
var src: SListNode<T?>? = head.next
var dst: SListNode<T>? = newHead
while let node = src {
dst?.next = SListNode<T>(f(node.val))
dst = dst?.next
src = node.next
}
return newHead
}
}8.2 LRUCache
// 语言：Swift
import Foundation
/// LRU 节点（双向链表）
final class DNode {
var key: Int
var value: Int
var prev: DNode?
var next: DNode?
init(_ key: Int, _ value: Int) { self.key = key; self.value = value }
}
/// LRU：哈希表 + 双向链表（带虚拟头尾）
final class LRUCache {
private let capacity: Int
private var dict: [Int: DNode] = [:]
private let head = DNode(0, 0) // dummy head
private let tail = DNode(0, 0) // dummy tail
private var size = 0
init(_ capacity: Int) {
precondition(capacity > 0)
self.capacity = capacity
head.next = tail; tail.prev = head
}
func get(_ key: Int) -> Int {
guard let node = dict[key] else { return -1 }
moveToHead(node)
return node.value
}
func put(_ key: Int, _ value: Int) {
if let node = dict[key] {
node.value = value
moveToHead(node)
} else {
let node = DNode(key, value)
dict[key] = node
addToHead(node)
size += 1
if size > capacity, let removed = removeTail() {
dict.removeValue(forKey: removed.key)
size -= 1
}
}
}
private func addToHead(_ node: DNode) {
node.prev = head
node.next = head.next
head.next?.prev = node
head.next = node
}
private func removeNode(_ node: DNode) {
node.prev?.next = node.next
node.next?.prev = node.prev
node.prev = nil; node.next = nil
}
private func moveToHead(_ node: DNode) {
removeNode(node); addToHead(node)
}
@discardableResult
private func removeTail() -> DNode? {
guard let last = tail.prev, last !== head else { return nil }
removeNode(last)
return last
}
}9. Python 实战
9.1 单链表工具
# 语言：Python
from typing import Optional, TypeVar, Generic
T = TypeVar("T")
class SListNode(Generic[T]):
def __init__(self, val: T, next: Optional["SListNode[T]"] = None):
self.val = val
self.next = next
def build_list(arr):
"""从数组构建单链表"""
dummy = SListNode(None)
tail = dummy
for v in arr:
tail.next = SListNode(v)
tail = tail.next
return dummy.next
def print_list(head: Optional[SListNode[T]]) -> None:
"""打印 [a -> b -> c]"""
cur = head
parts = []
while cur:
parts.append(str(cur.val))
cur = cur.next
print("[" + " -> ".join(parts) + "]")
def push_front(head: Optional[SListNode[T]], val: T) -> SListNode[T]:
node = SListNode(val)
node.next = head
return node
def push_back(head: Optional[SListNode[T]], val: T) -> SListNode[T]:
node = SListNode(val)
if head is None:
return node
cur = head
while cur.next:
cur = cur.next
cur.next = node
return head
def insert_after(head: Optional[SListNode[T]], pos: int, val: T) -> SListNode[T]:
"""在索引 pos 后插入（pos >= -1；-1 代表头插）"""
if pos < 0:
return push_front(head, val)
if head is None:
return SListNode(val)
cur = head
idx = 0
while idx < pos and cur.next is not None:
cur = cur.next
idx += 1
node = SListNode(val)
node.next = cur.next
cur.next = node
return head
def remove_first(head: Optional[SListNode[T]], val: T) -> Optional[SListNode[T]]:
"""按值删除首个等于 val 的节点"""
if head is None:
return None
if head.val == val:
return head.next
prev = head
while prev.next:
if prev.next.val == val:
prev.next = prev.next.next
break
prev = prev.next
return head
def reverse(head: Optional[SListNode[T]]) -> Optional[SListNode[T]]:
"""三指针反转"""
prev = None
cur = head
while cur:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
return prev
def has_cycle(head: Optional[SListNode[T]]) -> bool:
"""Floyd 判环"""
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False9.2 LRUCache
# 语言：Python
class DNode:
"""双向链表节点"""
def __init__(self, key: int, value: int):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
"""
LRU：哈希表 + 双向链表（带 dummy 头尾）
get/put 均摊 O(1)
"""
def __init__(self, capacity: int):
assert capacity > 0
self.capacity = capacity
self.map = {}
self.head = DNode(0, 0)
self.tail = DNode(0, 0)
self.head.next = self.tail
self.tail.prev = self.head
self.size = 0
def get(self, key: int) -> int:
node = self.map.get(key)
if not node:
return -1
self._move_to_head(node)
return node.value
def put(self, key: int, value: int) -> None:
node = self.map.get(key)
if node:
node.value = value
self._move_to_head(node)
else:
new_node = DNode(key, value)
self.map[key] = new_node
self._add_to_head(new_node)
self.size += 1
if self.size > self.capacity:
tail = self._remove_tail()
if tail:
self.map.pop(tail.key, None)
self.size -= 1
# --- 原子操作 ---
def _add_to_head(self, node: DNode) -> None:
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def _remove_node(self, node: DNode) -> None:
prev, nxt = node.prev, node.next
if prev: prev.next = nxt
if nxt: nxt.prev = prev
node.prev = node.next = None
def _move_to_head(self, node: DNode) -> None:
self._remove_node(node)
self._add_to_head(node)
def _remove_tail(self) -> DNode | None:
last = self.tail.prev
if last is self.head:
return None
self._remove_node(last)
return last10. 面试高频问法 & 易错点清单
Q1：如何 O(1) 删除链表节点？
- o 单链表需已知前驱 prev；只给 node 可用“值覆盖 + 删后继”（不适用于尾节点）。双向链表天然 O(1)。
Q2：为什么 LRU 选双向链表 + 哈希表？
- o 哈希表负责 O(1) 定位节点，双向链表负责 O(1) 摘除与插入。
Q3：数组/堆能否胜任？
- o 数组维护“最近度”需要移动元素；堆难以表达“访问即变最新”的语义。
易错点：
- 1. 指针赋值顺序错误导致断链；2) 忘记更新 head/tail；3) 淘汰节点未从 map 删除；4) 并发场景缺锁。
11. 练习题详解与代码
11.1 反转链表（迭代与递归）
题意：反转单链表并返回新头。
思路：迭代三指针 prev/curr/next；或递归“先反转子链，再把 head 接到子链尾”。
正确性：循环不变式 & 递归回溯指向；
复杂度：O(n)；迭代 O(1) 额外空间，递归 O(n) 栈。
Swift
// 语言：Swift
import Foundation
final class ListNode {
var val: Int
var next: ListNode?
init(_ val: Int, _ next: ListNode? = nil) { self.val = val; self.next = next }
}
func reverseListIterative(_ head: ListNode?) -> ListNode? {
var prev: ListNode? = nil
var curr = head
while let node = curr {
let nxt = node.next
node.next = prev
prev = node
curr = nxt
}
return prev
}
func reverseListRecursive(_ head: ListNode?) -> ListNode? {
guard let head = head, let next = head.next else { return head }
let newHead = reverseListRecursive(next)
next.next = head
head.next = nil
return newHead
}
// 自测
func build(_ arr: [Int]) -> ListNode? {
let dummy = ListNode(0); var t: ListNode? = dummy
for v in arr { t?.next = ListNode(v); t = t?.next }
return dummy.next
}
func dumpList(_ h: ListNode?) -> [Int] { var r:[Int]=[]; var p=h; while let n=p { r.append(n.val); p=n.next }; return r }
print(dumpList(reverseListIterative(build([1,2,3,4,5])))) // [5,4,3,2,1]
print(dumpList(reverseListRecursive(build([1])))) // [1]Python
# 语言：Python
from typing import Optional
class ListNode:
def __init__(self, val: int, next: 'Optional[ListNode]' = None):
self.val = val
self.next = next
def reverse_list_iterative(head: Optional[ListNode]) -> Optional[ListNode]:
prev, curr = None, head
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
return prev
def reverse_list_recursive(head: Optional[ListNode]) -> Optional[ListNode]:
if head is None or head.next is None:
return head
new_head = reverse_list_recursive(head.next)
head.next.next = head
head.next = None
return new_head
# 自测
def build(arr):
d = ListNode(0); t = d
for v in arr: t.next = ListNode(v); t = t.next
return d.next
def to_list(h):
r = []
while h: r.append(h.val); h = h.next
return r
print(to_list(reverse_list_iterative(build([1,2,3,4,5])))) # [5,4,3,2,1]
print(to_list(reverse_list_recursive(build([1])))) # [1]11.2 删除倒数第 k 个节点（快慢指针 + dummy）
题意：删除倒数第 k 个节点并返回新头。
思路：dummy -> head；fast 先走 k 步，再与 slow 同步走到尾；此时 slow 在待删前驱。
正确性：两指针距离始终为 k；
复杂度：O(n) 时间，O(1) 空间。
Swift
// 语言：Swift
func removeNthFromEnd(_ head: ListNode?, _ k: Int) -> ListNode? {
let dummy = ListNode(0, head)
var fast: ListNode? = dummy
var slow: ListNode? = dummy
for _ in 0..<k {
if fast?.next == nil { return head } // k 超界：返回原链（也可抛错/按题意处理）
fast = fast?.next
}
while fast?.next != nil {
fast = fast?.next
slow = slow?.next
}
slow?.next = slow?.next?.next
return dummy.next
}
// 自测
print(dumpList(removeNthFromEnd(build([1,2,3,4,5]), 2))) // [1,2,3,5]
print(dumpList(removeNthFromEnd(build([1]), 1))) // []
print(dumpList(removeNthFromEnd(build([1,2]), 3))) // [1,2]Python
# 语言：Python
from typing import Optional
def remove_nth_from_end(head: Optional[ListNode], k: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
fast, slow = dummy, dummy
for _ in range(k):
if fast.next is None:
return head # k 超界：原样返回
fast = fast.next
while fast.next:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.next
# 自测
print(to_list(remove_nth_from_end(build([1,2,3,4,5]), 2))) # [1,2,3,5]
print(to_list(remove_nth_from_end(build([1]), 1))) # []
print(to_list(remove_nth_from_end(build([1,2]), 3))) # [1,2]11.3 合并两个有序链表（原地优先）
题意：合并两个升序单链表成一个升序链表，尽量复用原节点。
思路：dummy + tail 尾插较小节点，某一方空后接上另一方剩余。
正确性：循环不变式：dummy->...->tail 始终有序。
复杂度：O(n+m) 时间，O(1) 空间。
Swift
// 语言：Swift
func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
let dummy = ListNode(0); var tail: ListNode? = dummy
var a = l1, b = l2
while a != nil && b != nil {
if a!.val <= b!.val { tail?.next = a; a = a?.next }
else { tail?.next = b; b = b?.next }
tail = tail?.next
}
tail?.next = (a != nil) ? a : b
return dummy.next
}
// 自测
print(dumpList(mergeTwoLists(build([1,2,4]), build([1,3,4])))) // [1,1,2,3,4,4]
print(dumpList(mergeTwoLists(nil, build([0])))) // [0]Python
# 语言：Python
from typing import Optional
def merge_two_lists(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
d = ListNode(0); tail = d
a, b = l1, l2
while a and b:
if a.val <= b.val: tail.next = a; a = a.next
else: tail.next = b; b = b.next
tail = tail.next
tail.next = a if a else b
return d.next
# 自测
print(to_list(merge_two_lists(build([1,2,4]), build([1,3,4])))) # [1,1,2,3,4,4]
print(to_list(merge_two_lists(None, build([0])))) # [0]11.4 环检测与入口（Floyd 判圈 + 入环点）
题意：判断链表是否有环；若有，返回环入口节点。
思路：
- 1. 快慢指针相遇判环；
- 2. 相遇后，一指针从 head 出发，另一从相遇点出发，同时一步步走，再次相遇处即环入口。
正确性：经典等式 a = (k-1)(b+c) + c 推得“相遇后齐头并进到入口”。
复杂度：时间 O(n)，空间 O(1)。
Swift
// 语言：Swift
func detectCycle(_ head: ListNode?) -> ListNode? {
var slow = head, fast = head
while let f1 = fast, let f2 = f1.next {
slow = slow?.next
fast = f2.next
if slow === fast {
var p = head, q = slow
while p !== q { p = p?.next; q = q?.next }
return p
}
}
return nil
}
// 自测：构造有环
let a = ListNode(3); let b = ListNode(2); let c = ListNode(0); let d = ListNode(-4)
a.next = b; b.next = c; c.next = d; d.next = b
print(detectCycle(a)?.val ?? -1) // 2（b 的值）Python
# 语言：Python
from typing import Optional
def detect_cycle(head: Optional[ListNode]) -> Optional[ListNode]:
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
p, q = head, slow
while p is not q:
p = p.next
q = q.next
return p
return None
# 自测
a = ListNode(3); b = ListNode(2); c = ListNode(0); d = ListNode(-4)
a.next = b; b.next = c; c.next = d; d.next = b
print(detect_cycle(a).val if detect_cycle(a) else None) # 211.5 LRU 进阶：泛型、TTL（过期）、线程安全
(A) 泛型 LRU（Swift）
要点：dict: [Key: Node]；双向链表节点保存 key/value；四原子操作不变。
说明：示例用占位 Dummy 节点，生产建议定义专门的 Dummy 类型或改用可选。
// 语言：Swift
import Foundation
final class LRUNode<Key: Hashable, Value> {
var key: Key
var value: Value
var prev: LRUNode?
var next: LRUNode?
init(_ key: Key, _ value: Value) { self.key = key; self.value = value }
}
final class GenericLRUCache<Key: Hashable, Value> {
private let capacity: Int
private var dict: [Key: LRUNode<Key, Value>] = [:]
private let head = LRUNode<Key, Value>(unsafeBitCast(0, to: Key.self), unsafeBitCast(0, to: Value.self))
private let tail = LRUNode<Key, Value>(unsafeBitCast(0, to: Key.self), unsafeBitCast(0, to: Value.self))
private var size = 0
init(_ capacity: Int) {
precondition(capacity > 0)
self.capacity = capacity
head.next = tail; tail.prev = head
}
func get(_ key: Key) -> Value? {
guard let node = dict[key] else { return nil }
moveToHead(node)
return node.value
}
func put(_ key: Key, _ value: Value) {
if let node = dict[key] {
node.value = value
moveToHead(node)
} else {
let node = LRUNode(key, value)
dict[key] = node
addToHead(node)
size += 1
if size > capacity, let removed = removeTail() {
dict.removeValue(forKey: removed.key); size -= 1
}
}
}
private func addToHead(_ n: LRUNode<Key, Value>) {
n.prev = head; n.next = head.next
head.next?.prev = n; head.next = n
}
private func removeNode(_ n: LRUNode<Key, Value>) {
n.prev?.next = n.next; n.next?.prev = n.prev
n.prev = nil; n.next = nil
}
private func moveToHead(_ n: LRUNode<Key, Value>) { removeNode(n); addToHead(n) }
private func removeTail() -> LRUNode<Key, Value>? {
guard let last = tail.prev, last !== head else { return nil }
removeNode(last); return last
}
}(B) TTL（过期）版 LRU
要点：节点带 expireAt 时间戳；get 时若过期则删除并视为未命中；put 刷新过期时间。
Swift
// 语言：Swift
import Foundation
final class TTLNode<Key: Hashable, Value> {
var key: Key
var value: Value
var expireAt: TimeInterval
var prev: TTLNode?
var next: TTLNode?
init(_ key: Key, _ value: Value, _ expireAt: TimeInterval) {
self.key = key; self.value = value; self.expireAt = expireAt
}
}
final class TTLRUCache<Key: Hashable, Value> {
private let capacity: Int
private let ttl: TimeInterval
private var dict: [Key: TTLNode<Key, Value>] = [:]
private let head = TTLNode<Key, Value>(unsafeBitCast(0, to: Key.self), unsafeBitCast(0, to: Value.self), 0)
private let tail = TTLNode<Key, Value>(unsafeBitCast(0, to: Key.self), unsafeBitCast(0, to: Value.self), 0)
private var size = 0
init(capacity: Int, ttl: TimeInterval) {
precondition(capacity > 0 && ttl > 0)
self.capacity = capacity; self.ttl = ttl
head.next = tail; tail.prev = head
}
func get(_ key: Key) -> Value? {
guard let node = dict[key] else { return nil }
let now = Date().timeIntervalSince1970
if now >= node.expireAt {
removeNode(node); dict.removeValue(forKey: key); size -= 1
return nil
}
moveToHead(node)
return node.value
}
func put(_ key: Key, _ value: Value) {
let now = Date().timeIntervalSince1970
if let node = dict[key] {
node.value = value; node.expireAt = now + ttl; moveToHead(node)
} else {
let node = TTLNode(key, value, now + ttl)
dict[key] = node; addToHead(node); size += 1
if size > capacity, let rm = removeTail() {
dict.removeValue(forKey: rm.key); size -= 1
}
}
}
private func addToHead(_ n: TTLNode<Key, Value>) { n.prev = head; n.next = head.next; head.next?.prev = n; head.next = n }
private func removeNode(_ n: TTLNode<Key, Value>) { n.prev?.next = n.next; n.next?.prev = n.prev; n.prev = nil; n.next = nil }
private func moveToHead(_ n: TTLNode<Key, Value>) { removeNode(n); addToHead(n) }
private func removeTail() -> TTLNode<Key, Value>? { guard let last = tail.prev, last !== head else { return nil }; removeNode(last); return last }
}Python
# 语言：Python
import time
from typing import Generic, TypeVar, Optional, Dict
K = TypeVar("K")
V = TypeVar("V")
class TTLNodePy(Generic[K, V]):
def __init__(self, key: K, value: V, expire_at: float):
self.key = key
self.value = value
self.expire_at = expire_at
self.prev: 'Optional[TTLNodePy[K, V]]' = None
self.next: 'Optional[TTLNodePy[K, V]]' = None
class TTLRUCachePy(Generic[K, V]):
def __init__(self, capacity: int, ttl_seconds: float):
assert capacity > 0 and ttl_seconds > 0
self.capacity = capacity
self.ttl = ttl_seconds
self.map: Dict[K, TTLNodePy[K, V]] = {}
self.head = TTLNodePy(None, None, 0) # dummy
self.tail = TTLNodePy(None, None, 0) # dummy
self.head.next = self.tail
self.tail.prev = self.head
self.size = 0
def get(self, key: K) -> Optional[V]:
node = self.map.get(key)
if not node:
return None
now = time.time()
if now >= node.expire_at:
self._remove_node(node)
self.map.pop(key, None)
self.size -= 1
return None
self._move_to_head(node)
return node.value
def put(self, key: K, value: V) -> None:
now = time.time()
node = self.map.get(key)
if node:
node.value = value
node.expire_at = now + self.ttl
self._move_to_head(node)
else:
node = TTLNodePy(key, value, now + self.ttl)
self.map[key] = node
self._add_to_head(node)
self.size += 1
if self.size > self.capacity:
rm = self._remove_tail()
if rm:
self.map.pop(rm.key, None)
self.size -= 1
def _add_to_head(self, node: TTLNodePy[K, V]) -> None:
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def _remove_node(self, node: TTLNodePy[K, V]) -> None:
prev, nxt = node.prev, node.next
if prev: prev.next = nxt
if nxt: nxt.prev = prev
node.prev = node.next = None
def _move_to_head(self, node: TTLNodePy[K, V]) -> None:
self._remove_node(node)
self._add_to_head(node)
def _remove_tail(self) -> Optional[TTLNodePy[K, V]]:
last = self.tail.prev
if last is self.head:
return None
self._remove_node(last)
return last(C) 线程安全
要点：写操作用互斥；读操作也要保护结构一致性。Swift 可用并发队列 + barrier；Python 用 RLock。
Swift（并发队列 + barrier）
// 语言：Swift
import Foundation
final class ThreadSafeLRU<Key: Hashable, Value> {
private let inner = GenericLRUCache<Key, Value>(4) // 复用上文实现
private let queue = DispatchQueue(label: "lru.queue", attributes: .concurrent)
func get(_ key: Key) -> Value? {
queue.sync { inner.get(key) }
}
func put(_ key: Key, _ value: Value) {
queue.async(flags: .barrier) { self.inner.put(key, value) }
}
}Python（RLock）
# 语言：Python
import threading
from typing import Optional, Generic, TypeVar
K = TypeVar("K")
V = TypeVar("V")
class ThreadSafeLRU(Generic[K, V]):
def __init__(self, capacity: int):
self._lru = TTLRUCachePy[K, V](capacity, ttl_seconds=10**9) # “超长 TTL”当普通 LRU 用
self._lock = threading.RLock()
def get(self, key: K) -> Optional[V]:
with self._lock:
return self._lru.get(key)
def put(self, key: K, value: V) -> None:
with self._lock:
self._lru.put(key, value)自测建议：多线程并发 put/get 压测，检测是否崩溃、是否命中率与容量统计正确。
12. 复盘
- o 链表本质：节点 + 指针；随机访问慢、插入/删除快。
- o 双向链表 + 哨兵：删中间 O(1)，边界统一。
- o LRU 标配：哈希 + 双链，四原子操作要烂熟（addToHead/removeNode/moveToHead/removeTail）。
- o 面试套路：三指针反转、快慢指针判环、dummy 头尾、指针顺序正确性。
- o 工程化：泛型、TTL、并发安全，算法“产品化”。
猜你喜欢
- 2025-09-21 快速了解JavaScript的基础知识_javascript 基础
- 2025-09-21 陌生APP拿到你的摄像头权限后拿到你的“裸照”有多容易
- 2025-09-21 原 顶 ECMAScript6入门 学习之简介
- 2025-09-21 Rust元编程: 让你的代码在编译时开始「自我繁殖」
- 2025-09-21 别再让误操作背锅!常见防误操作程序底层逻辑，工程师必收藏
- 2025-09-21 Javascript简介和基础数据类型_javascript的数据类型主要包括
- 2025-09-21 Rust中的Condvar条件变量:让线程"听话"的魔法棒
- 2025-09-21 一举两得学编程:Rust 与 Zig 对比学习教程
- 2025-09-21 从零开始的 SwiftUI 互操作_swiftui dsl
- 2025-09-21 面试被问 const 是否不可变?这样回答才显功底
- 最近发表
- 标签列表
-
- location.href (44)
- document.ready (36)
- git checkout -b (34)
- 跃点数 (35)
- 阿里云镜像地址 (33)
- qt qmessagebox (36)
- mybatis plus page (35)
- vue @scroll (38)
- 堆栈区别 (33)
- 什么是容器 (33)
- sha1 md5 (33)
- navicat导出数据 (34)
- 阿里云acp考试 (33)
- 阿里云 nacos (34)
- redhat官网下载镜像 (36)
- srs服务器 (33)
- pico开发者 (33)
- https的端口号 (34)
- vscode更改主题 (35)
- 阿里云资源池 (34)
- os.path.join (33)
- redis aof rdb 区别 (33)
- 302跳转 (33)
- http method (35)
- js array splice (33)