数据结构与算法笔记-数据结构-链表

原创
2020/09/11 14:14
阅读数 382

[TOC]

数据结构与算法笔记-数据结构-链表

链表(linked list)

链表代码-gitee

链表代码-github

关键词

  • 链表是和数组相反的一种数据结构,数组是连续下标的内存结构,链表未非连续结构,通过寄存相邻节点的指针来实现.

  • 头结点: 链表的第一个节点

  • 尾结点: 链表的最后一个节点

  • 指针: 未必一定要是指针,也可以指向一个数据而已,但是一般我们都称之为指针.

  • 常见的几种链表类型

    • 单向链: 主要是最后一个节点的指针指向NULL
    • 循环链表: 主要是最后一个节点的指针指向头结点.
    • 双向链表: 主要是节点同时可以指向前一个节点和后一个节点
    • 双向循环链表: 主要是将双向链表和循环链表结合起来做成的链表,即将双向链表的尾结点的指针指向头结点.
  • 链表的时间复杂度

    • 插入和删除: O(1)
    • 随机访问: O(n)

本章无总结可写, 基本上没什么难理解的,主要是要多写多练

链表-上-之实现LRU缓存淘汰算法

链表的经典应用场景: LRU 缓存淘汰算法

缓存尝试:

缓存时一种提高性能的技术,在硬件和软件中广泛采用.比如CPU缓存,数据库缓存,浏览器缓存等等.

缓存是有大小的,当缓存被用满时,那些数据需要被清理出去.就需要一个淘汰机制.

常见的策略有三种:

  1. 先进先出策略 FIFO(First In, First Out)
  2. 最少使用策略 LFU(Least Frequently Used)
  3. 最近最少用策略 LRU(Least Recently Used)

链表结构

链表是一种较为复杂的数据结构,数组和链表都是很基础的数据结构,但是链表更为复杂且链表有3种形式的链表

  1. 双向链表
  2. 单向链
  3. 循环链表

数组和链表的区别

从底层架构分析: 数组需要一块连续的内存空间来存储,对内存要求比较高:

如果要申请一个100M大小的内存空间,当内存中没有连续的足够大的内存空间时,即便剩余内存大于100M,也会申请失败

而链表就不会存在这种情况,链表不需要一块连续的内存空间,它通过""指针"将一组零散的内存块串联起来

所以如果申请100M大小的链表,就不会出现这种情况.

img

单向链表

链表通过指针将一组零散的内存块串联在一起,通常将内存块成为链表的节点.

为了将所有的节点串联起来,每个链表的节点除了存储数据之外,还要记录链上的下一个节点的地址.

通常把这个记录下一个节点指针叫做后继指针next.

img

如图所示,单向链表中有两个节点是比较特殊的,分别是第一个节点和最后一个节点.通常称之为头结点尾节点.

头节点用来记录链表的基地址,有了这个就可以遍历得到整条链表.

尾结点特殊的地方是指针不指向下一个节点,而是指向一个空地址NULL,表示这是链上最后一个节点.

链表和数组一样,链表也支持数据的查找,插入和删除操作.

在进行数组的插入和删除时为了保持内存数据的连续性,需要作出大量的搬运,所以时间复杂度时O(n).

而在链表中插入或者删除一个数据,并不需要为了保持内存的连续性搬运节点,因为链表的存储空间本身就不是连续的.

所以链表的插入和删除数据时一个非常快的.

img

针对链表的插入和删除操作,只需要考虑相邻节点的指针改变,所以对应的时间复杂度时O(1).

img

链表要想随机访问第k个元素,就没有数组高效了.

因为链表中的数据并非连续存储,所以无法像数组根据首地址和下标,通过寻址公式就能直接计算出对应的内存

链表是要根据指针一个节点一个节点的逐个遍历,直到找到相应的节点.

链表的随机访问性能没有数组好,需要O(n)的时间复杂度.

循环链表

循环链表和单项链表唯一的区别就是双向链表的尾结点指针指向头结点.

单项链表的尾结点指向一个空指针.

img

相较于单向链表,循环链表的优点是从链尾到链首时很方便.用来处理环形结构的数据是很方便,比如约瑟夫问题

如果非要用单项链表的话也是可以实现的,但是代码量会多很多

双向链表

单项链表只有一个方向,节点之后只有一个后继指针 next指向后面的节点.

而双向链表,有两个方向,每个节点既有next指向后面的后继指针,也有一个prev指向前一个指针的的前驱节点.

img

双向链表需要额外的两个空间来存储后继节点和前驱节点的地址.

所以如果存储同样多的数据,双向链表要比单项链表占用更多的空间.

虽然双向链表比较浪费空间,但是支持双向遍历,操作会灵活很多.

从结构来看,双向链表支持O(1)时间复杂度的情况下找到前驱节点,所以双向链表在某些情况下

插入如和删除操作都比单项链表简单且高效.

链表操作性能

删除操作:

通常有两种情况

  1. 删除节点中的某个给定的值的节点
  2. 删除给定指针的值

第一种情况:

无论是单向链表还是双向链表都需要从头开始遍历.

虽然删除操作的时间复杂度时O(1),但是前面的遍历操作的时间复杂度时O(n).根据加法法则那么删除操作的时间复杂度时O(n).

第二种情况:

一上来就能拿到要删除的节点,但是要删除某个节点q,需要知道他的前驱节点

单向链表不能获取前驱节点,这就要再次从头遍历前驱节点,直到p->next=q,说明p是q的前驱结点,所以删除动作的时间复杂度时O(n).

双向链表已保存了前驱节点的指针,不需要再次遍历一遍,所以针对第二种情况双向链表的删除动作的时间复杂度是O(1)

插入操作

对于插入动作来说,双向链表也比单项链表有优势,双向链表O(1),单项链表O(n).

查询操作

对于查询动作,双向链表的按值查询的效率也比单项效率高很多.因为可以记录上次查找的位置p,

每次查询时,根据要查询的只与p的大小关系,可以决定向前还是向后查找,平均只需要查找一半的数据.

所以在工作中,虽然双向链表比单项链表更费内存,但是大家都在用双向链表.

据称,Java的LinkedHashMap的实现原理就是双向链表.

总结

这就是用空间换时间的设计思想

对于执行慢的程序,可以通过消费更多的内存(空间换时间)来优化

对于消耗过多内存的程序,可以通过消耗更多时间的(时间换空间)来降低内存的消费

但是,实话说,我个人认为性能比空间重要.时间换空间的项目估计是新项目或者是那种等死的项目

双向循环链表

将双向链表和循环链表整合起来就是,双向循环链表

img

链表和数组对比

数组和链表是两种不同的内存组织结构,因为内存存储的区别,他们的插入,删除,随机访问操作的世界复杂度正好相反

img

数组简单易用,使用的是连续的内存空间,可以借助CPU的缓存机制预读数组中的数据,访问的效率更高.

链表在内存中并不是连续的存储的,所以对CPU缓存很不友好,没法预读缓存.

数组的缺点

  1. 大小固定,一旦声明就要占用整块的连续内存.
  2. 如果申请过大,系统可能没有足够多的连续内存,导致内存不足(out of memeory).
  3. 如果申请过小,搞不好会出现不够用的情况.这时候只能再申请一个更大的,把原数组的数据复制过去做成动态扩容数组,有点耗时.
  4. 而链表不存在这个情况,没有大小限制,支持动态扩容,这是链表和数组最大的区别.

切记: 在实际应用中,不能总是强调时间复杂度分析就决定用哪个数据结构.

如果代码对内存要求很严苛,那就用数组.

因为链表的每个节点都要消费额外的内存来记录下一个节点的指针,所以内存消耗会翻倍.

对链表进行频繁的插入和删除会导致频繁的内存被申请和释放,容易造成内存碎片.如果是Java可能会导致频繁的GC(Garbage Collection,垃圾回收)

基于链表实现 LRU 缓存淘汰算法

维护一个有序单向链表,越是靠近尾部的节点就是越早之前访问的,当有一个新的数据被访问时,就从链表头部开始遍历.

  1. 如果此数据之前已经被缓存在链表中了,遍历得到这个数据对应的节点,并将其从原来的位置删除,然后再插入到链表头部.
  2. 如果链表中没有改数据
    1. 如果此时链表未满,则将该数据直接插入到链表头部
    2. 如果链表已满,则将链表尾部的删除掉,将新的数据插入到链表头部

这就实现了一个LRU缓存淘汰算法

时间复杂度:

不管缓存有没有满,都要遍历一遍链表,所以这种基于链表实现的思路,缓存访问的世界复杂度时O(n).

如果使用**散列表(hash table)**记录每个数据的位置,可以将缓存访问时间降为O(1).

小结

链表是和数组相反的一种数据结构,链表和数组都是非常基础和常用的数据结构.

链表比数组更为复杂,从普通的单向链表衍生出来好几种链表结构,比如:

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

与数组相比,链表更加适合插入和删除操作比较频繁的常见,查询的时间复杂度比较高

不过,具体场景下,需要对链表和数组的各种性能进行对比,具体还要设计到业务类型,才能选定用什么数据结构.

链表-下-之写出正确的链表代码

6个写链表代码的技巧

1.理解指针或引用的意义

要写好链表代码,首先要理解好指针.

有的语言有指针,比如C和go.有的语言没指针而叫做引用,比如Java,PHP,Python. 但意思都一样,都是存储所指对象的内存地址.

所谓指针,即将某个变量赋值给指针,实际上就是将这个变量的地址赋值给指针,

反过来说,指针中存储了这个变量的内存地址,指向了这个变量,通过指针就能找到这个变量.

在编写链表代码时,通常会这么有这样的代码: p->next=q,这代码是指,p节点中的next指针存储了q节点的内存地址.

更复杂的代码,p->next=p->next->next,这代码表示p节点的next指针存储了p节点的下下一个节点的内存地址.

2.警惕指针丢失和内存泄漏

在写链表代码时,指针来回指,很容易不知道指到哪里去了,一定要注意不能弄丢指针.

弄丢指针的案例

img

如图,希望在节点a和相邻节点b之间插入节点x,假设当前节点p指向节点a.

如果代码写作下面这样,就会弄丢指针:

p->next = x;  // 将p的next指针指向x结点;
x->next = p->next;  // 将x的结点的next指针指向b结点;

第1行p->next指针在完成第一步操作后已经不再指向b了,而是指向节点x.

第2行代码相当于将x赋值给了x->next,自己指向知己.因此整个链表也就断成了两节,从节点b往后所有的节点都无法访问到了.

在部分语言中,比如C语言,内存管理是由人来负责的,如果没有手动释放内存就会产生内存泄漏.

所以在插入节点时一定要注意操作的顺序:

  1. 要先把节点x测next指针指向b
  2. 再把节点a的next指针指向x,这样才不会丢失指针,导致内存泄漏

所以上面的插入代码,只需要将第一行和第二行代码的顺序颠倒一下就可以了.

同时,在删除链表时,也必须先手动释放内存,否则也会出现内存泄漏的问题.(以上说的都是C语言. java,PHP什么的不考虑)

3.利用哨兵简化实现难度

单项链表插入案例

单项链表的节点p后面插入一个新的节点

new_node->next = p->next;
p->next = new_node;

若要向一个空的单项链表中插入第一个结点,上面的代码就跑不通了,需要进行下面代码的这样的特殊处理,其中head表示链表的头结点.

所以,对于单项链表的插入操作,第一个节点和其他节点的插入逻辑是完全不同的.

if (head == null) {
  head = new_node;
}

单项链表删除,如果要删除节点p的后继节点,只要一行代码

p->next = p->next->next;

但是如果要删除单项链表中的最后一个节点,上面的删除代码就用不了了,和插入类似,也要对这种特殊情况进行处理

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

上面都是对单项链表的操作,可以看出: 单项链表的插入,删除操作,需要对插入第一个节点和删除最后一个节点的情况进行特殊处理.

这样会导致代码很啰嗦

哨兵解决单项链表的边界问题

表示一个空链表: head=null表示链表中没有节点了,其中head为头节点指针,指向表中的第一个节点.

如果引入哨兵,任何时候不管链表是不是空的,head指针都会一直指向这个哨兵节点,这种哨兵节点也叫做带头节点

没有哨兵节点的链表就叫做不带头链表

如图,哨兵节点是不存储任何数据的,因为哨兵节点所以插入第一个结点和插入其他结点,删除最后一个结点和删除其他结点,都可以统一为相同的代码实现逻辑了.

img

利用哨兵简化编程难度的技巧,在很多代码实现中都有用到,比如插入排序、归并排序、动态规划等

代码案例:

// 在数组a中,查找key,返回key所在的位置
// 其中,n表示数组a的长度
int find(char* a, int n, char key) {
  // 边界条件处理,如果a为空,或者n<=0,说明数组中没有数据,就不用while循环比较了
  if(a == null || n <= 0) {
    return -1;
  }
  
  int i = 0;
  // 这里有两个比较操作:i<n和a[i]==key.
  while (i < n) {
    if (a[i] == key) {
      return i;
    }
    ++i;
  }
  
  return -1;
}

代码案例:

// 在数组a中,查找key,返回key所在的位置
// 其中,n表示数组a的长度
// 我举2个例子,你可以拿例子走一下代码
// a = {4, 2, 3, 5, 9, 6}  n=6 key = 7
// a = {4, 2, 3, 5, 9, 6}  n=6 key = 6
int find(char* a, int n, char key) {
  if(a == null || n <= 0) {
    return -1;
  }
  
  // 这里因为要将a[n-1]的值替换成key,所以要特殊处理这个值
  if (a[n-1] == key) {
    return n-1;
  }
  
  // 把a[n-1]的值临时保存在变量tmp中,以便之后恢复。tmp=6。
  // 之所以这样做的目的是:希望find()代码不要改变a数组中的内容
  char tmp = a[n-1];
  // 把key的值放到a[n-1]中,此时a = {4, 2, 3, 5, 9, 7}
  a[n-1] = key;
  
  int i = 0;
  // while 循环比起代码一,少了i<n这个比较操作
  while (a[i] != key) {
    ++i;
  }
  
  // 恢复a[n-1]原来的值,此时a= {4, 2, 3, 5, 9, 6}
  a[n-1] = tmp;
  
  if (i == n-1) {
    // 如果i == n-1说明,在0...n-2之间都没有key,所以返回-1
    return -1;
  } else {
    // 否则,返回i,就是等于key值的元素的下标
    return i;
  }
}

对比上面的两端代码,当字符串a很长的时比如几十万:

  1. 代码2的代码执行的最快,因为两端代码中执行次数最多的就是while循环的一部分
  2. 代码2中,通过一个哨兵a[n-1]=key,成功省掉了一个比较语句i<n,这一小条语句,如果在类型执行上万次的时候累计就会非常的明显

但是大部分情况下,我们不会追求极致的性能.

4.重点留意边界条件处理

想写好链表,必须检查边界条件是否考虑全面,代码在既定边界条件下能否正确运行.

经常用来检查代码是否正确的条件有:

  • 如果链表为空,代码能否正常工作
  • 如果链表只包含一个结点,代码能否正常工作
  • 如果链表只包含两个结点,代码能否正常工作
  • 代码逻辑在处理头结点和尾结点的时候,能否正常工作
5. 举例画图辅助思考

将具体的例子画在纸上,思维会更加的清晰.

比如: 向单向链表中插入一个数据的这样一个操作, 一般就把各种情况都举一个例子,画出插入前和插入后链表的变化:

img

6.多写多练

5个常见的链表操作:

  1. 单链表反转
  2. 链表中环的检测
  3. 两个有序链表的合并
  4. 删除链表倒数的第n个节点
  5. 求链表的中间节点

小结

主要讲了正确写出链表代码的6个技巧,分别是:

  1. 理解指针或引用的含义

  2. 警惕指针丢失和内存泄漏

  3. 利用哨兵简化实现难度

  4. 重点留意边界条件处理

  5. 举例画图、辅助思考,

  6. 多写多练

写链表代码是最考验逻辑思维能力的,因为链表代码到处是指针操作,边界条件的处理.

链表代码写的好坏,可以看出一个人写代码是否细心(MD,完美的细心确实很重要,也确实难做到.),考虑问题是否全面,思维是否缜密.

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部