一、是什么
一种物理存储单元（内存）非连续的数据结构，数据元素的逻辑顺序通过链表中的指针依次串联
二、使用场景
-
Redis的LRU缓存淘汰策略
LRU：Least Recently Used，代表最近最久未使用，使用的立马更新成最新的，剔除近段时间最久没更新的数据。它是按照一个非常著名的计算机操作系统理论：最近使用的页面数据会在未来一段时期内仍然被使用，已经很久没有使用的页面很有可能在未来较长的一段时间内仍然不会被使用。 - 约瑟夫环算法题
- 频繁更新、删除的场景
三、工作原理
每个数据结点，除了存储数据之外，还需要记录下一个结点的地址
四、链表类型
-
单链表：
每个数据结点除存储数据，还记录下个结点的地址（后继指针） -
双链表：
每个数据结点除了存储数据，还记录上一个和下一个结点的地址（前继指针和后继指针） -
循环链表：
单链表的尾结点指针指向NULL,循环链表的尾结点指向链表的头结点 -
循环双链表：
循环链表和双链表的结合
PS：
- 头结点： 头结点的数据为空，只记录链表的基地址
-
尾结点： 尾结点的数据不为空，指针指向一个空地址
NULL
五、实现
-
代码实现
package main
import "fmt"
// 数据结点
type node struct {
data int
prev *node
next *node
}
// 在 xxx 结点之前插入结点
func InsertBeforeLinkedList(a int, beforeInsert *node) *node {
insertNode := node{
data: a,
prev: beforeInsert.prev,
next: beforeInsert,
}
beforeInsert.prev.next = &insertNode
beforeInsert.prev = &insertNode
return &insertNode
}
// 在 xxx 结点之后插入结点
func InsertAfterLinkedList(a int, afterInsert *node) *node {
insertNode := node{
data: a,
prev: afterInsert,
next: afterInsert.next,
}
// 校验是否是第一个结点，首结点无 next
if afterInsert.next != nil {
afterInsert.next.prev = &insertNode
}
afterInsert.next = &insertNode
return &insertNode
}
func main() {
head := node{}
zero := node{
prev: &head,
next: nil,
}
/*** 在 xxx 结点之前插入结点验证 ***/
// zero 的前面增加结点-1
before := InsertBeforeLinkedList(-1, &zero)
// head 在 before 前面 before.prev
fmt.Printf("%p", &head)
// before 结构体
fmt.Println(before)
// zero 在 before 后面 before.next
fmt.Printf("%p", &zero)
/*** 在 xxx 结点之后插入结点验证 ***/
zero = node{
prev: &head,
next: nil,
}
// zero 的后面加结点1
one := InsertAfterLinkedList(1, &zero)
// zero.pre
fmt.Printf("%p", &head)
// zero 结构体的值
fmt.Println(zero)
// zero.next
fmt.Printf("%p", one)
return
}
六、优劣
- 优点：
- 合理利用碎片内存空间
- 一定的先决条件下，插入和删除操作时间复杂度为
O(1)
先决条件
插入：向a地址之前插入一条数据，需要知道a地址之前的结点地址
删除：删除a地址的数据，需要知道a地址之前的结点数据
PS：双链表情况下可以不需要此先决条件
- 缺点：
- 随机访问的性能没有数组好，需要
O(n)的时间复杂度
七、替代性技术
- 数组
- 栈
- 队列
八、经典应用
LRU算法
package main
import "fmt"
type Node struct {
Key int
Vaule int
prev *Node
next *Node
}
type LRUCache struct {
limit int
hashMap map[int]*Node
head *Node
end *Node
}
// 初始化缓存
func Constructor(size int) *LRUCache {
newCache := LRUCache{
limit: size,
hashMap: make(map[int]*Node, size),
}
return &newCache
}
// 获取缓存数据
// 1、判断数据是否存在
// 1、不存在，直接返回
// 2、存在，则数据刷新，返回数据
func (l *LRUCache) get(key int) int {
if v, ok := l.hashMap[key]; !ok {
return -1
} else {
l.refreshData(v)
return v.Vaule
}
}
// 写入数据
//
// 1、 判断数据是否存在
// 1、存在，则数据更新、刷新
// 2、不存在，判断是否缓存已满
// 1、已满，则移除头数据，新数据直接放在最后
// 2、未满，新数据直接放到最后
func (l *LRUCache) put(key, value int) int {
// 判断数据是否存在
if v, ok := l.hashMap[key]; ok {
// 存在则更新、刷新数据
v.Vaule = value
l.refreshData(v)
return 1
} else {
// 判断缓存是否已满
if len(l.hashMap) >= l.limit {
l.removeData(l.head)
delete(l.hashMap, key)
}
newData := &Node{
Key: key,
Vaule: value,
}
l.addData(newData)
l.hashMap[key] = newData
return 1
}
}
// 刷新
// 1、数据删除
// 2、数据放到最后
func (l *LRUCache) refreshData(dataNode *Node) {
l.removeData(dataNode)
l.addData(dataNode)
}
//移除数据
//1、判断缓存中是否存在此数据
// 1、不存在，则直接 return
// 2、存在，则分3种情况
// 1、缓存头数据，缓存头直接指向 head.next
// 2、缓存尾数据，缓存尾直接指向 end.prev
// 3、非缓存头尾数据
func (l *LRUCache) removeData(dataNode *Node) (position int) {
// 判断缓存中数据是否存在
if _, ok := l.hashMap[dataNode.Key]; !ok {
return -1
} else {
if l.head == dataNode { // 缓存头数据
l.head = l.head.next
l.head.prev = nil
} else if l.end == dataNode { // 缓存尾数据
l.end = l.end.prev
l.end.next = nil
} else {
dataNode.prev.next = dataNode.next
dataNode.next.prev = dataNode.prev
}
return 1
}
}
//添加数据，放在最后
//1、判断当前数据是不是就是最后的数据
// 1、就是最后数据，无需操作
// 2、非最后数据，判断当前缓存是否为空
// 1、为空，则直接放数据
// 2、非空，进行数据指针切换
func (l *LRUCache) addData(dataNode *Node) {
if l.end != dataNode {
if l.end == nil {
l.head = dataNode
l.end = dataNode
l.end.next = nil
} else {
dataNode.prev = l.end
l.end.next = dataNode
l.end = dataNode
l.end.next = nil
}
}
}
// 依序获取整个链表的数据
// 测试用
func (l *LRUCache) getCache() {
pos := l.head
for {
fmt.Printf("%p", pos)
fmt.Println(pos)
if pos.next == nil {
break
}
pos = pos.next
}
}
func main() {
cache := Constructor(3)
cache.put(11, 1)
cache.put(22, 2)
cache.put(33, 3)
cache.put(44, 4)
cache.put(55, 5)
cache.getCache()
cache.get(33)
fmt.Println("========== 获取数据之后 ===============")
cache.getCache()
}
约瑟夫环
package main
import "fmt"
// 人
type Person struct {
num int
prev *Person
next *Person
}
// 环
type Roll struct {
size int
moveInt int
targetPerson int
head *Person
end *Person
hashMap map[int]*Person
}
// 初始化缓存
func Constructor(size, moveInt, targetPerson int) *Roll {
r := &Roll{
size: size,
moveInt: moveInt,
hashMap: make(map[int]*Person),
targetPerson: targetPerson,
}
for i, tmpPerson := 1, r.head; i <= size; i++ {
// 头链表
if i == 1 {
r.head = &Person{
num: i,
}
r.hashMap[i] = r.head
tmpPerson = r.head
continue
}
// 尾链表
if i == size {
r.end = &Person{
num: size,
next: r.head,
prev: tmpPerson,
}
tmpPerson.next = r.end
r.head.prev = r.end
r.hashMap[size] = r.end
break
}
tmp := &Person{
num: i,
prev: tmpPerson,
}
r.hashMap[i] = tmp
tmpPerson.next = tmp
tmpPerson = tmp
}
return r
}
// 依序获取整个链表的数据
// 测试用
func (r *Roll) getRoll(size int) {
pos := r.head
for i := 1; i <= size; i++ {
fmt.Println(i)
fmt.Printf("%p", pos)
fmt.Println(pos)
if pos.next != nil {
pos = pos.next
}
}
}
// 移除人
func (r *Roll) remove(removePerson *Person) (nextPerson *Person) {
fmt.Println(removePerson.num)
nextPerson = removePerson.next
removePerson.prev.next = removePerson.next
removePerson.next.prev = removePerson.prev
delete(r.hashMap, removePerson.num)
return
}
// 循环
// 进行循环，符合条件的进行移除，直至环剩下的人数恰好等于目标人数
func (r *Roll) round() {
removePerson := r.head
i := 1
for {
// 判断环的大小是否等于目标大小
if len(r.hashMap) <= r.targetPerson || len(r.hashMap) == 0 {
break
}
// 判断是否到指定游标的人
if i == r.moveInt {
removePerson = r.remove(removePerson)
i = 1
} else {
i++
removePerson = removePerson.next
}
}
}
func main() {
roll := Constructor(1, 5, 2)
roll.round()
}
回文字符串
package main
import (
"fmt"
)
func findStrMiddle(str string) bool {
// 字符串转 byte 切片
runeStr := []byte(str)
firstStr := []byte{}
// 字符串长度
length := len(runeStr)
for i, j, k := 0, 0, 0; i < len(runeStr); i++ {
if j < len(str) { // first 字符串前半部分
firstStr = append(firstStr, runeStr[i])
j += 2
} else { // 逆序从字符串尾部，依次与字符串前半部分一一比较
if firstStr[k] != runeStr[length-1] {
return false
} else {
length -= 1
k++
}
}
}
return true
}
func main() {
fmt.Println(findStrMiddle("level"))
}
链表反转
// 输入: a->b->c->d->e->NULL
// 输出: e->d->c->b->a->NULL
package main
import "fmt"
type Node struct {
data string
next *Node
}
// 初始化字符串链表
func (head *Node) Constructor(str string) {
byteStr := []byte(str)
cur := head
for i := 0; i < len(byteStr); i++ {
cur.next = &Node{data: string(byteStr[i])}
cur = cur.next
}
}
// 反转链表
func (head *Node) reverseLinkedList() (newHead *Node) {
cur := head
var pre *Node
for cur != nil {
cur.next, pre, cur = pre, cur, cur.next
}
return pre
}
// 循环输出链表，测试用
func getLinkedList(node *Node) {
for cur := node; cur != nil; cur = cur.next {
fmt.Printf("%p", cur)
fmt.Println(cur)
}
}
func main() {
head := &Node{}
head.Constructor("abcdefg")
getLinkedList(head.next)
newHead := head.next.reverseLinkedList()
fmt.Println("-----------------------")
getLinkedList(newHead)
}
有序链表合并
package main
import "fmt"
type ListNode struct {
Val int
Next *ListNode
}
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
head := &ListNode{}
// 校验 l1/l2 是否为空
if l1 == nil && l2 != nil {
return l2
}
if l2 == nil && l1 != nil {
return l1
}
if l2 == nil && l1 == nil {
return nil
}
if l1.Val > l2.Val {
addNode(l1, l2, head)
} else {
addNode(l2, l1, head)
}
return head.Next
}
// l1.val > l2.val
func addNode(max *ListNode, min *ListNode, node *ListNode) {
node.Next = min
// 终止条件
if min.Next == nil {
node.Next.Next = max
return
}
if max.Val > min.Next.Val {
addNode(max, min.Next, node.Next)
} else {
addNode(min.Next, max, node.Next)
}
}
// 初始化链表
func (head *ListNode) constructor(nums []int) {
cur := head
for _, v := range nums {
cur.Next = &ListNode{
Val: v,
}
cur = cur.Next
}
}
// 输出链表
func (head *ListNode) printLinkedList() {
for cur := head; cur != nil; cur = cur.Next {
fmt.Println(cur.Val)
}
}
func main() {
head1 := &ListNode{}
head1.constructor([]int{})
head1.Next.printLinkedList()
fmt.Println("-------------------------")
head2 := &ListNode{}
head2.constructor([]int{})
head2.Next.printLinkedList()
fmt.Println("-------------------------")
merge := mergeTwoLists(head1.Next, head2.Next)
merge.printLinkedList()
}
