【数据结构与算法】链表

一、是什么

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


二、使用场景

  • RedisLRU缓存淘汰策略
    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()
}

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 199,393评论 5 467
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 83,790评论 2 376
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 146,391评论 0 330
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 53,703评论 1 270
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 62,613评论 5 359
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,003评论 1 275
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,507评论 3 390
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,158评论 0 254
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,300评论 1 294
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,256评论 2 317
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,274评论 1 328
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 32,984评论 3 316
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,569评论 3 303
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,662评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,899评论 1 255
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,268评论 2 345
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 41,840评论 2 339

推荐阅读更多精彩内容