【数据结构与算法】链表

一、是什么

一种物理存储单元（内存）非连续的数据结构，数据元素的逻辑顺序通过链表中的指针依次串联

---

二、使用场景

• Redis的LRU缓存淘汰策略
  LRU：Least Recently Used，代表最近最久未使用，使用的立马更新成最新的，剔除近段时间最久没更新的数据。它是按照一个非常著名的计算机操作系统理论：最近使用的页面数据会在未来一段时期内仍然被使用，已经很久没有使用的页面很有可能在未来较长的一段时间内仍然不会被使用。
• 约瑟夫环算法题
• 频繁更新、删除的场景

---

三、工作原理

每个数据结点，除了存储数据之外，还需要记录下一个结点的地址

---

四、链表类型

• 单链表：
  每个数据结点除存储数据，还记录下个结点的地址（后继指针）
• 双链表：
  每个数据结点除了存储数据，还记录上一个和下一个结点的地址（前继指针和后继指针）
• 循环链表：
  单链表的尾结点指针指向NULL,循环链表的尾结点指向链表的头结点
• 循环双链表：
  循环链表和双链表的结合

PS：

1. 头结点： 头结点的数据为空，只记录链表的基地址
2. 尾结点： 尾结点的数据不为空，指针指向一个空地址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
}

---

六、优劣

• 优点：

1. 合理利用碎片内存空间
2. 一定的先决条件下，插入和删除操作时间复杂度为 O(1)

先决条件
插入：向a地址之前插入一条数据，需要知道a地址之前的结点地址
删除：删除a地址的数据，需要知道a地址之前的结点数据

PS：双链表情况下可以不需要此先决条件

• 缺点：

1. 随机访问的性能没有数组好，需要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()
}