单向链表实现lru
package main
import "fmt"
func main() {
// 实现一个lru 淘汰算法
// linked 结构体
// node 节点 : data prev next
// 更新lru
// 如果没有满
// 将新的数据加入到头结点
// 队满 : 删除尾结点
// 将新数据加入头结点
linkedObj := getLinked[int](5)
linkedObj.insert(6)
linkedObj.insert(5)
linkedObj.insert(4)
linkedObj.insert(3)
linkedObj.insert(2)
linkedObj.insert(1)
linkedObj.insert(0)
//fmt.Printf("当前节点: %+vn", linkedObj)
fmt.Printf("当前节点: %+vn", linkedObj.head.next.data)
linkedObj.foreach()
}
type linked[T int | string | map[string]string] struct {
head *node[T]
length int
limit int
}
type node[T int | string | map[string]string] struct {
data T
next *node[T]
}
func getLinked[T int | string | map[string]string](limit int) *linked[T] {
headNode := &node[T]{}
return &linked[T]{
head: headNode,
length: 0,
limit: limit,
}
}
func createNode[T int | string | map[string]string](data T) *node[T] {
return &node[T]{
data: data,
next: nil,
}
}
func (l *linked[T]) insert(data T) bool {
newNode := createNode(data)
headNode := l.head.next
newNode.next = l.head.next
l.head.next = newNode
if l.length == l.limit {
prevNode := headNode
for headNode.next != nil {
prevNode = headNode
headNode = headNode.next
}
prevNode.next = nil
} else {
l.length++
}
return true
}
func (l *linked[T]) foreach() {
headNode := l.head.next
for headNode.next != nil {
headNode = headNode.next
fmt.Printf("当前节点: %+vn", headNode.data)
}
}
双向链表
package main
import "fmt"
func main() {
// 实现一个双向循环链表
linkedObj := getLinked[int](5)
linkedObj.headInsert(6)
linkedObj.headInsert(5)
linkedObj.headInsert(4)
linkedObj.headInsert(3)
linkedObj.headInsert(2)
linkedObj.headInsert(1)
linkedObj.headInsert(0)
//fmt.Printf("当前节点: %+vn", linkedObj)
//fmt.Printf("当前节点: %+vn", linkedObj.head.next.data)
linkedObj.headForeach()
//linkedObj.tailForeach()
}
type linked[T int | string | map[string]string] struct {
head *node[T]
length int
limit int
}
type node[T int | string | map[string]string] struct {
data T
next *node[T]
prev *node[T]
}
func getLinked[T int | string | map[string]string](limit int) *linked[T] {
return &linked[T]{
head: nil,
length: 0,
limit: limit,
}
}
func createNode[T int | string | map[string]string](data T) *node[T] {
return &node[T]{
data: data,
next: nil,
prev: nil,
}
}
// 从头部插入
func (l *linked[T]) headInsert(data T) bool {
newNode := createNode(data)
if l.head == nil {
l.head = newNode
l.head.next = newNode
l.head.prev = newNode
l.length++
return true
}
// 原头结点
currentNode := l.head
headNode := currentNode
l.head = newNode
newNode.next = currentNode
currentNode.prev = newNode
// 找到尾结点
for {
if currentNode.next == headNode {
break
}
currentNode = currentNode.next
}
if l.length >= l.limit {
currentNode.prev.next = l.head
l.head.prev = currentNode.prev
} else {
l.head.prev = currentNode
l.length++
}
return true
}
func (l *linked[T]) delete(node *node[T]) {
}
// 从头部遍历
func (l *linked[T]) headForeach() {
headNode := l.head
fmt.Printf("从头结点遍历:n")
for {
fmt.Printf("当前节点: %+vn", headNode.data)
if headNode.next == l.head {
break
}
headNode = headNode.next
}
}
// 从尾部遍历
func (l *linked[T]) tailForeach() {
endNode := l.head.prev
fmt.Printf("从尾结点遍历:n")
for {
fmt.Printf("当前节点: %+vn", endNode.data)
if endNode.prev == l.head.prev {
break
}
endNode = endNode.prev
}
}
双向循环链表
package main
import "fmt"
func main() {
// 实现一个lru 淘汰算法
// 双向循环链表
// linked 结构体
// node 节点 : data prev next
// 更新lru
// 如果没有满
// 将新的数据加入到头结点
// 队满 : 删除尾结点
// 将新数据加入头结点
linkedObj := getLinked[int](5)
linkedObj.headInsert(6)
linkedObj.headInsert(5)
linkedObj.headInsert(4)
linkedObj.headInsert(3)
linkedObj.headInsert(2)
linkedObj.headInsert(1)
linkedObj.headInsert(0)
//fmt.Printf("当前节点: %+vn", linkedObj)
//fmt.Printf("当前节点: %+vn", linkedObj.head.next.data)
linkedObj.headForeach()
linkedObj.tailForeach()
}
type linked[T int | string | map[string]string] struct {
head *node[T]
length int
limit int
}
type node[T int | string | map[string]string] struct {
data T
next *node[T]
prev *node[T]
}
func getLinked[T int | string | map[string]string](limit int) *linked[T] {
return &linked[T]{
head: nil,
length: 0,
limit: limit,
}
}
func createNode[T int | string | map[string]string](data T) *node[T] {
return &node[T]{
data: data,
next: nil,
prev: nil,
}
}
// 从头部插入
func (l *linked[T]) headInsert(data T) bool {
newNode := createNode(data)
if l.head == nil {
l.head = newNode
l.length++
newNode.next = newNode
newNode.prev = newNode
return true
}
currentNode := l.head
// 头结点位置
headNodePos := l.head
l.head = newNode
newNode.next = currentNode
currentNode.prev = newNode
// 找尾结点
for {
if currentNode.next == headNodePos {
break
}
currentNode = currentNode.next
}
if l.length >= l.limit {
currentNode.prev.next = newNode
newNode.prev = currentNode.prev
} else {
currentNode.next = newNode
newNode.prev = currentNode
l.length++
}
return true
}
func (l *linked[T]) delete(node *node[T]) {
}
// 从头部遍历
func (l *linked[T]) headForeach() {
headNode := l.head
headNodPos := headNode
fmt.Printf("从头结点遍历:n")
for {
fmt.Printf("当前节点: %+vn", headNode.data)
if headNode.next == headNodPos {
break
}
headNode = headNode.next
}
}
// 从尾部遍历
func (l *linked[T]) tailForeach() {
endNode := l.head
endNodePos := endNode
fmt.Printf("从尾结点遍历:n")
for {
fmt.Printf("当前节点: %+vn", endNode.prev.data)
if endNode.prev == endNodePos {
break
}
endNode = endNode.prev
}
}
原文地址:https://blog.csdn.net/u012914309/article/details/134677775
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_5785.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。