一臀防、是什么
一種物理存儲(chǔ)單元（內(nèi)存）非連續(xù)的數(shù)據(jù)結(jié)構(gòu)遂蛀，數(shù)據(jù)元素的邏輯順序通過鏈表中的指針依次串聯(lián)
二进肯、使用場景
-
Redis的LRU緩存淘汰策略
LRU：Least Recently Used岂傲，代表最近最久未使用痰洒，使用的立馬更新成最新的麦向，剔除近段時(shí)間最久沒更新的數(shù)據(jù)口糕。它是按照一個(gè)非常著名的計(jì)算機(jī)操作系統(tǒng)理論：最近使用的頁面數(shù)據(jù)會(huì)在未來一段時(shí)期內(nèi)仍然被使用，已經(jīng)很久沒有使用的頁面很有可能在未來較長的一段時(shí)間內(nèi)仍然不會(huì)被使用磕蛇。 - 約瑟夫環(huán)算法題
- 頻繁更新景描、刪除的場景
三、工作原理
每個(gè)數(shù)據(jù)結(jié)點(diǎn)秀撇，除了存儲(chǔ)數(shù)據(jù)之外超棺，還需要記錄下一個(gè)結(jié)點(diǎn)的地址
四、鏈表類型
-
單鏈表：
每個(gè)數(shù)據(jù)結(jié)點(diǎn)除存儲(chǔ)數(shù)據(jù)呵燕，還記錄下個(gè)結(jié)點(diǎn)的地址（后繼指針） -
雙鏈表：
每個(gè)數(shù)據(jù)結(jié)點(diǎn)除了存儲(chǔ)數(shù)據(jù)棠绘，還記錄上一個(gè)和下一個(gè)結(jié)點(diǎn)的地址（前繼指針和后繼指針） -
循環(huán)鏈表：
單鏈表的尾結(jié)點(diǎn)指針指向NULL,循環(huán)鏈表的尾結(jié)點(diǎn)指向鏈表的頭結(jié)點(diǎn) -
循環(huán)雙鏈表：
循環(huán)鏈表和雙鏈表的結(jié)合
PS：
- 頭結(jié)點(diǎn)： 頭結(jié)點(diǎn)的數(shù)據(jù)為空，只記錄鏈表的基地址
-
尾結(jié)點(diǎn)： 尾結(jié)點(diǎn)的數(shù)據(jù)不為空再扭，指針指向一個(gè)空地址
NULL
五氧苍、實(shí)現(xiàn)
-
代碼實(shí)現(xiàn)
package main
import "fmt"
// 數(shù)據(jù)結(jié)點(diǎn)
type node struct {
data int
prev *node
next *node
}
// 在 xxx 結(jié)點(diǎn)之前插入結(jié)點(diǎn)
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 結(jié)點(diǎn)之后插入結(jié)點(diǎn)
func InsertAfterLinkedList(a int, afterInsert *node) *node {
insertNode := node{
data: a,
prev: afterInsert,
next: afterInsert.next,
}
// 校驗(yàn)是否是第一個(gè)結(jié)點(diǎn)，首結(jié)點(diǎn)無 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 結(jié)點(diǎn)之前插入結(jié)點(diǎn)驗(yàn)證 ***/
// zero 的前面增加結(jié)點(diǎn)-1
before := InsertBeforeLinkedList(-1, &zero)
// head 在 before 前面 before.prev
fmt.Printf("%p", &head)
// before 結(jié)構(gòu)體
fmt.Println(before)
// zero 在 before 后面 before.next
fmt.Printf("%p", &zero)
/*** 在 xxx 結(jié)點(diǎn)之后插入結(jié)點(diǎn)驗(yàn)證 ***/
zero = node{
prev: &head,
next: nil,
}
// zero 的后面加結(jié)點(diǎn)1
one := InsertAfterLinkedList(1, &zero)
// zero.pre
fmt.Printf("%p", &head)
// zero 結(jié)構(gòu)體的值
fmt.Println(zero)
// zero.next
fmt.Printf("%p", one)
return
}
六泛范、優(yōu)劣
- 優(yōu)點(diǎn)：
- 合理利用碎片內(nèi)存空間
- 一定的先決條件下让虐，插入和刪除操作時(shí)間復(fù)雜度為
O(1)
先決條件
插入：向a地址之前插入一條數(shù)據(jù)，需要知道a地址之前的結(jié)點(diǎn)地址
刪除：刪除a地址的數(shù)據(jù)罢荡，需要知道a地址之前的結(jié)點(diǎn)數(shù)據(jù)
PS：雙鏈表情況下可以不需要此先決條件
- 缺點(diǎn)：
- 隨機(jī)訪問的性能沒有數(shù)組好赡突，需要
O(n)的時(shí)間復(fù)雜度
七、替代性技術(shù)
- 數(shù)組
- 棧
- 隊(duì)列
八区赵、經(jīng)典應(yīng)用
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
}
// 獲取緩存數(shù)據(jù)
// 1惭缰、判斷數(shù)據(jù)是否存在
// 1、不存在笼才，直接返回
// 2漱受、存在，則數(shù)據(jù)刷新骡送，返回?cái)?shù)據(jù)
func (l *LRUCache) get(key int) int {
if v, ok := l.hashMap[key]; !ok {
return -1
} else {
l.refreshData(v)
return v.Vaule
}
}
// 寫入數(shù)據(jù)
//
// 1昂羡、 判斷數(shù)據(jù)是否存在
// 1絮记、存在，則數(shù)據(jù)更新紧憾、刷新
// 2到千、不存在昌渤，判斷是否緩存已滿
// 1赴穗、已滿，則移除頭數(shù)據(jù)膀息，新數(shù)據(jù)直接放在最后
// 2般眉、未滿，新數(shù)據(jù)直接放到最后
func (l *LRUCache) put(key, value int) int {
// 判斷數(shù)據(jù)是否存在
if v, ok := l.hashMap[key]; ok {
// 存在則更新潜支、刷新數(shù)據(jù)
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甸赃、數(shù)據(jù)刪除
// 2、數(shù)據(jù)放到最后
func (l *LRUCache) refreshData(dataNode *Node) {
l.removeData(dataNode)
l.addData(dataNode)
}
//移除數(shù)據(jù)
//1冗酿、判斷緩存中是否存在此數(shù)據(jù)
// 1埠对、不存在，則直接 return
// 2裁替、存在项玛，則分3種情況
// 1、緩存頭數(shù)據(jù)弱判，緩存頭直接指向 head.next
// 2襟沮、緩存尾數(shù)據(jù)，緩存尾直接指向 end.prev
// 3昌腰、非緩存頭尾數(shù)據(jù)
func (l *LRUCache) removeData(dataNode *Node) (position int) {
// 判斷緩存中數(shù)據(jù)是否存在
if _, ok := l.hashMap[dataNode.Key]; !ok {
return -1
} else {
if l.head == dataNode { // 緩存頭數(shù)據(jù)
l.head = l.head.next
l.head.prev = nil
} else if l.end == dataNode { // 緩存尾數(shù)據(jù)
l.end = l.end.prev
l.end.next = nil
} else {
dataNode.prev.next = dataNode.next
dataNode.next.prev = dataNode.prev
}
return 1
}
}
//添加數(shù)據(jù)开伏，放在最后
//1、判斷當(dāng)前數(shù)據(jù)是不是就是最后的數(shù)據(jù)
// 1遭商、就是最后數(shù)據(jù)固灵，無需操作
// 2、非最后數(shù)據(jù)劫流，判斷當(dāng)前緩存是否為空
// 1怎虫、為空，則直接放數(shù)據(jù)
// 2困介、非空大审，進(jìn)行數(shù)據(jù)指針切換
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
}
}
}
// 依序獲取整個(gè)鏈表的數(shù)據(jù)
// 測試用
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("========== 獲取數(shù)據(jù)之后 ===============")
cache.getCache()
}
約瑟夫環(huán)
package main
import "fmt"
// 人
type Person struct {
num int
prev *Person
next *Person
}
// 環(huán)
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
}
// 依序獲取整個(gè)鏈表的數(shù)據(jù)
// 測試用
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
}
// 循環(huán)
// 進(jìn)行循環(huán)，符合條件的進(jìn)行移除座哩，直至環(huán)剩下的人數(shù)恰好等于目標(biāo)人數(shù)
func (r *Roll) round() {
removePerson := r.head
i := 1
for {
// 判斷環(huán)的大小是否等于目標(biāo)大小
if len(r.hashMap) <= r.targetPerson || len(r.hashMap) == 0 {
break
}
// 判斷是否到指定游標(biāo)的人
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 {
// 字符串轉(zhuǎn) 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"))
}
鏈表反轉(zhuǎn)
// 輸入: 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
}
}
// 反轉(zhuǎn)鏈表
func (head *Node) reverseLinkedList() (newHead *Node) {
cur := head
var pre *Node
for cur != nil {
cur.next, pre, cur = pre, cur, cur.next
}
return pre
}
// 循環(huán)輸出鏈表，測試用
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{}
// 校驗(yàn) 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()
}
