数据结构与算法之美 06 | 链表(上)-如何实现LRU缓存淘汰算法

常见的缓存淘汰策略:
先进先出 FIFO
最少使用LFU(Least Frequently Used)
最近最少使用 LRU(Least Recently Used) 链表定义:
链表也是线性表的一种,
数组需要一块连续的内存空间来存储,对内存要求比较高,
链表恰恰相反,它并不需要一块连续的内存空间,它通过"指针"将一组零散的内存块
串联起来使用。 最常见的链表结构:
单链表
双向链表
循环链表 用空间换时间:
当内存空间充足的时候,如果更加追求代码的执行速度,可以选择空间复杂度相对较高、
但时间复杂度相对很低的算法或数据结构。 链表 vs 数组性能
数组 链表
插入删除 O(n) O(1)
随机访问 O(1) O(n) 如果基于链表实现LRU缓存淘汰算法?
思路: 维护一个有序单链表,越靠近链表尾部的结点是越早之间访问的数据,
当有一个新的数据被访问时,从链表头开始顺序遍历链表。 1. 如果此数据之前已经被缓存在链表中,可以遍历得到这个数据对应的结点,
并将其从原来的位置删除,然后再插入到链表的头部。 2. 如果此数据没有在缓存链表中,又可以分为两种情况:
如果此时缓存未满,则将此结点直接插入到链表的头部;
如果此时缓存已满,则链表尾结点删除,将新的数据结点插入链表的头部。 缓存访问时间复杂度: 因为不管缓存有没有满,都需要遍历一遍链表,因此时间复杂度为O(n)
可以通过"散列表(Hash table)"来记录每个数据的位置,将缓存访问的时间复杂度降低为O(1) 内容小结:
链表是跟数组"相反"的数据结构,它跟数组一样,也是非常基础、常用的数据结构。
不过链表比数组稍微复杂。 从普通的单链表衍生出 双向链表、循环链表、双向循环链表 和数组相比,链表更适合插入、删除操作频繁的场景,查询的时间复杂度较高。 基于Python语言实现的单链表
# 定义链表节点
class Node(object):
def __init__(self, data, n=None):
self.data = data
self.next = n # 定义链表及其增删改查
class LinkList(object): def __init__(self):
# 初始化空链表
self.head = None
self.tail = None
self.length = 0 def is_empty(self):
# 判断链表是否为空
return self.length == 0 def append(self, dataOrNode):
"""
在尾部添加数据
:param dataOrNode: Data or Node obj
:return: True or None
"""
# 判断是一个数据还是Node对象
if isinstance(dataOrNode, Node):
item = dataOrNode
else:
item = Node(dataOrNode) if self.length == 0:
# 判断是一个空链表, 直接赋值
self.head = item
else:
# 将旧尾部节点的next指向新增加的数据
old_tail = self.tail
old_tail.next = item self.tail = item
self.length += 1
return True def delete(self, index):
"""
删除指定位置的数据
:param index: 位置
:return: True or False
"""
if self.is_empty():
print("this chain table is empty.")
return False if index < 0 or index >= self.length:
print("error: out of index.")
return False if index == 0:
# 直接删除第一个数据
self.head = self.head.next
self.length -= 1
return True
else:
j = 0
node = self.head
prev = self.head
# 从头开始遍历,遍历到指定位置,然后删除数据
while node.next and j < index:
prev = node
node = node.next
j += 1 if j == index:
prev.next = node.next
self.length -= 1
return True
if index == self.length - 1:
self.tail = prev def insert(self, index, dataOrNode):
"""
在指定位置插入数据
:param index: 位置
:param dataOrNode: Data or Node Obj
:return: True or False
"""
if self.is_empty():
print("this chain table is empty")
return False if index < 0 or index >= self.length:
print("error: out of index")
return False if isinstance(dataOrNode, Node):
item = dataOrNode
else:
item = Node(dataOrNode) if index == 0:
# 在首部直接插入数据
item.next = self.head
self.head = item
self.length += 1
else:
j = 0
node = self.head
prev = self.head
# 从头开始遍历,遍历到指定位置,然后插入数据
while node.next and j < index:
prev = node
node = node.next
j += 1
if j == index:
item.next = node
prev.next = item
self.length += 1
return True def update(self, index, data):
"""
更新指定位置的数据
:param index: 位置
:param data: 数据
:return: True or False
"""
if self.is_empty() or index < 0 or index >= self.length:
print("error: out of index")
return False j = 0
node = self.head
# 从头开始遍历,遍历到指定位置,然后更新数据
while node.next and j < index:
node = node.next
j += 1 if j == index:
node.data = data
return True
return False def get_item(self, index):
"""
获取指定位置的数据
:param index:
:return:
"""
if self.is_empty() or index < 0 or index >= self.length:
print("error: out of index")
return j = 0
node = self.head
while node.next and j < index:
node = node.next
j += 1 if j == index:
return node.data def clear(self):
"""
删除所有数据
:return:
"""
self.head = None
self.length = 0
return True def __len__(self):
return self.length def __getitem__(self, item):
# 使用[]获取实例属性 如obj[item], python会自动调用__getitem__方法;
return self.get_item(item) def __setitem__(self, key, value):
# 使用[]设置实例属性 如obj[key] = value, python会自动调用__setitem__方法;
return self.update(key, value) if __name__ == '__main__':
link = LinkList()
for i in range(5):
link.append(i) print("初始化后,链表长度为:", len(link))
for i in range(len(link)):
print("初始化数据:", link.get_item(i)) print("删除指定位置数据:", link.delete(0)) print("删除指定数据后,链表长度为:", len(link))
for i in range(len(link)):
print("删除后的数据为:", link.get_item(i)) print("指定位置插入数据:", link.insert(1, 100)) print("插入数据后的链表长度:", len(link))
for i in range(len(link)):
print("插入后的数据:", link.get_item(i)) print("更新指定数据", link.update(1, 200)) # 更新数据
link[1] = 100 # 获取数据
print(link[1])
基于Go语言实现的单链表
package main

import (
"fmt"
) type Object interface {
} // 定义节点
type Node struct {
data Object
next *Node
} // 定义单向链表
type List struct {
head *Node
tail *Node
size uint64
} // 初始化链表
func (list *List) Init() {
(*list).size = // 此时链表是空的
(*list).head = nil // 没有头
(*list).tail = nil // 没有尾
} // 向尾部添加数据
func (list *List) Append(node *Node) bool {
if node == nil {
return false
} // 将尾部的next设置为空
(*node).next = nil // 将新元素放入单链表中
if (*list).size == {
(*list).head = node
} else {
// 将旧尾部数据的next指向新的数据
oldTail := (*list).tail
(*oldTail).next = node
} // 调整尾部位置及链表元素数量
(*list).tail = node // node成为新的尾部
(*list).size ++ // 元素数量增加
return true
} // 插入数据
func (list *List) Insert(i uint64, node *Node) bool {
// 空的节点、索引超出范围和空链表都无法做插入操作
if node == nil || i > (*list).size || (*list).size == {
return false
} if i == {
// 直接排在第一
(*node).next = (*list).head
(*list).head = node
} else {
// 找前一个元素
preItem := (*list).head
for j := ; uint64(j) < i; j++ {
// 数前面i个元素
preItem = (*preItem).next
}
// 原有元素放到新元素后面,新元素放到前一个元素后面
(*node).next = (*preItem).next
(*preItem).next = node
} (*list).size ++
return true
} // 删除元素
func (list *List) Remove(i uint64, node *Node) bool {
if i >= (*list).size {
return false
}
if i == {
node = (*list).head
(*list).head = (*node).next
if (*list).size == {
(*list).tail = nil
}
} else {
preItem := (*list).head
for j := ; uint64(j) < i; j++ {
preItem = (*preItem).next
}
node = (*preItem).next
(*preItem).next = (*node).next if i == ((*list).size - ) {
(*list).tail = preItem
}
}
(*list).size --
return true
} // 获取元素
func (list *List) Get(i uint64) *Node {
if i >= (*list).size {
return nil
} item := (*list).head
for j := ; uint64(j) < i; j++ {
item = (*item).next
}
return item
} func main() { // 初始化长度为100的空链表
var list = List{}
list.Init()
for i := ; i <= ; i++ {
var node = Node{data: i}
list.Append(&node)
} var node = list.Get()
fmt.Printf("Current node position: %d, data: %d\n", node, node.data)
var deleteNode = &Node{}
result := list.Remove(, deleteNode)
fmt.Printf("Delete result: %+v \n", result) var node2 = list.Get()
fmt.Printf("Current node position: %p, data: %d\n", node2, node2.data) newNode := Node{data: }
result2 := list.Insert(, &newNode)
fmt.Printf("Insert result: %+v \n", result2) var node3 = list.Get()
fmt.Printf("Current node position: %p, data: %d\n", node3, node3.data) fmt.Printf("Head: %d, Tail: %d", list.head.data, list.tail.data)
}
上一篇:缓存淘汰算法之FIFO


下一篇:linux安装python