golang 实现单向链表（lru）、双向链表、双向循环链表

单向链表实现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("当前节点: %+v\n", linkedObj)
	fmt.Printf("当前节点: %+v\n", 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("当前节点: %+v\n", 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("当前节点: %+v\n", linkedObj)
	//fmt.Printf("当前节点: %+v\n", 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("当前节点: %+v\n", 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("当前节点: %+v\n", 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("当前节点: %+v\n", linkedObj)
	//fmt.Printf("当前节点: %+v\n", 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("当前节点: %+v\n", 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("当前节点: %+v\n", endNode.prev.data)
		if endNode.prev == endNodePos {
			break
		}
		endNode = endNode.prev
	}
}