链表

作者: jiaji_3740 | 来源:发表于2019-04-17 14:26 被阅读0次

链表

image.png

缺点:查找复杂
有点:定点删除/插入元素

单链表

type ListNode struct {
    Val  int
    Next *ListNode
}
image.png

双向链表

type ListNode struct {
    Val  int
    Prev *ListNode
    Next *ListNode
}
image.png

循环链表

image.png

双向循环链表

image.png

数组与链表的区别

数据存储:数组必须要有连续的内存空间,链表不需要
数据存取特点:插入删除,随机访问时间复杂度正好相反

image.png

示例:LRU缓存淘汰策略

常见的缓存淘汰策略:
先进先出策略 FIFO(First In,First Out)、最少使用策略 LFU(Least Frequently Used)、最近最少使用策略 LRU(Least Recently Used)。

LRU

距离当前最久没有被访问过的数据应该被淘汰

package linked_list2

import (
    "errors"
    "fmt"
    "testing"
)

//链表结构
type ListNode struct {
    data int
    next *ListNode
}

//初始化链表头,下面的所有操作都是基于带头链表
func NewListNode() *ListNode {
    return &ListNode{next: nil}
}

//获取链表的长度
func (l *ListNode) Length() int {
    len := 0
    for l.next != nil {
        len++
        l = l.next
    }
    return len
}

//插入节点
func (l *ListNode) InsertNode(d int) error {
    fmt.Println("InsertNode", d)
    newNode := new(ListNode)

    newNode.data = d

    newNode.next = l.next

    l.next = newNode

    return nil

}

//删除节点
//注意:如果直接操作 l = l.next l的指向会发生变化
//注意:如果直接 temp = l.next ; temp = temp.next 不会对 l 链表有影响
func (l *ListNode) DelNode(d int) {
    if l == nil {
        errors.New("Empty List!")
        return
    }
    for l.next != nil {
        if l.next.data == d {
            l.next = l.next.next
            continue
        }
        l = l.next
    }
}

//遍历链表
func (l *ListNode) ListNode() {
    fmt.Print("range :")
    for l.next != nil {
        fmt.Printf(" %d", l.next.data)
        l = l.next
    }
    fmt.Println("")
}

//获取链表第一个元素
func (l *ListNode) GetFirstNode() *ListNode {
    return l.next
}

//递归单链反转
func ReverseList(pHead, node *ListNode) *ListNode {
    if node.next == nil {
        pHead.next = node
        return node
    }
    n := ReverseList(pHead, node.next)
    if n != nil {
        n.next = node
        node.next = nil
    }
    return node
}

//遍历单链反转方法

func (pHead *ListNode) ReverseListV2() {
    pReversedHead := pHead
    var pNode = pHead.next
    var pPrev *ListNode
    for pNode != nil {
        pNext := pNode.next
        if pNext == nil {
            pReversedHead.next = pNode
        }
        pNode.next = pPrev
        pPrev = pNode
        pNode = pNext
    }
    return
}

func TestLinkedList2(t *testing.T) {
    //新建单链表
    //
    l := NewListNode()
    l.ListNode()
    l.InsertNode(1)
    l.ListNode()
    l.InsertNode(2)
    l.ListNode()
    l.InsertNode(3)
    l.ListNode()
    fmt.Println("first:", l.GetFirstNode().data)

    fmt.Printf("before del l:%p\n", l)
    l.DelNode(2)
    fmt.Printf("after del l:%p\n", l)
    l.ListNode()
}


如何轻松写出正确的链表代码?

技巧一:理解指针或引用的含义
p->next=q
技巧二:警惕指针丢失和内存泄漏
p->next = x;  // 将 p 的 next 指针指向 x 结点;
x->next = p->next;  // 将 x 的结点的 next 指针指向 b 结点;
image.png

插入结点时,一定要注意操作的顺序
删除链表结点时,也一定要记得手动释放内存空间

技巧三:利用哨兵简化实现难度

针对链表的插入、删除操作,需要对插入第一个结点和删除最后一个结点的情况进行特殊处理

插入操作

if (head == null) {
  head = new_node;
}else{
  new_node->next = p->next;
  p->next = new_node;
}

删除操作
iif (head == null) {
  head = new_node;
}else{
  p->next = p->next->next;
}

哨兵也是解决“边界问题”的,不直接参与业务逻辑

带头链表:有哨兵结点的链表
不带头链表:有哨兵结点的链表

技巧四:重点留意边界条件处理

经常用来检查链表代码是否正确的边界条件:

  • 如果链表为空时,代码是否能正常工作?
  • 如果链表只包含一个结点时,代码是否能正常工作?
  • 如果链表只包含两个结点时,代码是否能正常工作?
  • 代码逻辑在处理头结点和尾结点的时候,是否能正常工作?
技巧五:举例画图,辅助思考
image.png
技巧六:多写多练,没有捷径

练习:

//Leetcode 206 https://leetcode.com/problems/reverse-linked-list/

type ListNode struct {
    Val  int
    Next *ListNode
}

//翻转链表
func reverseList(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    var prev *ListNode
    next := head.Next
    for next != nil {
        head.Next = prev
        prev = head
        head = next
        next = next.Next
    }
    head.Next = prev
    return head
}

引用:
https://zh.wikipedia.org/wiki/%E7%BA%A6%E7%91%9F%E5%A4%AB%E6%96%AF%E9%97%AE%E9%A2%98

极客时间: https://time.geekbang.org/column/article/41149

https://www.jianshu.com/p/b1ab4a170c3c

相关文章

  • 链表基础

    链表基础 链表长度 链表为空 链表结构 链表增加

  • 双向链表&双向循环链表

    链表分为:单链表、单向循环链表、双向链表、双向循环链表本节主要说明:双向链表、双向循环链表 定义结点 一、双向链表...

  • 算法与数据结构:链表

    链表 链表还分为单向链表和双向链表, 但是这篇文章只说单向链表 , 下次再讲双向链表 . 链表和数组的区别 ? 链...

  • 链表

    链表 单链表反转链表中环的检测两个有序链表合并删除链表倒数第n个节点求链表的元素总个数 一.单向链表 链表共有特征...

  • 五、双向链表

    双向链表 此前介绍的链表,也叫做单向链表使用双向链表可以提升链表的综合性能 修改之前的单链表的源码: 双向链表 –...

  • 链表

    内容 链表数据结构 向链表添加元素 从链表移除元素 使用 LinkedList 表 双向链表 循环链表 链表数据结...

  • 数据与算法结构

    线性表 顺序表 链表(物理上离散,逻辑上连续) 链表的类别 单链表 循环链表 双链表 链表的操作 顺序表与链表的比...

  • 数据结构——链表

    本文所讲的链表是单链表,链表采用无头链表 科普下:一般链表可以分为有头节点的链表与无头节点的链表 有头节点的链表:...

  • 链表

    文章结构 链表的定义 链表的插入和删除操作 链表的特性 常见的链表结构 自定义链表 链表的经典操作 使用链表实现L...

  • Algorithm小白入门 -- 单链表

    单链表递归反转链表k个一组反转链表回文链表 1. 递归反转链表 单链表节点的结构如下: 1.1 递归反转整个单链表...

网友评论

      本文标题:链表

      本文链接:https://www.haomeiwen.com/subject/yewkiqtx.html