October 11, 2018 · 数据结构与算法 本文字数: 1.3k 阅读时长:4 min 全站字数:344.2k

敏而好学之WHAT——链表的精髓

  1. 1 链表的征状
  2. 2 链表的增删改查操作
  3. 3 链表实战
    1. 3.1 实践中如何选择数组和链表
    2. 3.2 链表实现和应用中的编码技巧
      1. 3.2.1 理解链表节点中的指针或者引用
      2. 3.2.2 警惕指针丢失和内存泄漏
      3. 3.2.3 哨兵节点简化代码
      4. 3.2.4 特别要照顾边界条件
      5. 3.2.5 画画图,多写多练
      6. 3.2.6 链表代码实现学习

本文是数据结构与算法之美专栏的学习笔记。

1 链表的征状

链表也是线性表的一种,与数组最大的不同就是链表在内存区域不是连续的。组成链表的每个节点由数据和指针组成。指针至少有一个,可以有多个。如单链表只要一个指针,指向后一个节点。双向列表有两个指针,分别指向前一个节点和后一个节点。链表通过指针将多个位置的内存存储的链表节点链接起来形成链表。

链表中的节点按照在链表中的逻辑位置可以分为:中间节点,头结点,尾节点,哨兵节点。

链表可以分为单向链表,双向链表和循环列表。单链表有头结点,中间节点和尾节点。循环链表是特殊的单链表,尾节点的指针指向头结点。双向链表的每个节点有两个指针,分别指向前一个和后一个节点。双向循环列表是双向链表加循环链表。

2 链表的增删改查操作

链表的随机访问的复杂度是O(n),因为链表的内存是不连续的,必须通过节点中的指针进行遍历。

链表的插入和删除只需要修改其前后节点的指针即可,复杂度为O(1)。

链表的删除操作有两种情况:

  1. 删除节点值相等的节点。
  2. 删除特定指针指向的节点。

第一种情况需要遍历一遍链表,复杂度是O(n)。第二种情况,如果是单链表,则需要找将要删除节点的前驱节点,这里的复杂度是O(n),而双链表是O(1)。

插入操作与删除操作类似。

对于有序列表的查找操作,双向链表也比单链表高效,原因就是需要向前或者向后移动。双向链表通过使用内存换时间。

空间换时间或者时间换空间,适用于内存充足和CPU资源充足的场景。缓存就是以空间换时间,因为磁盘访问比内存访问慢。

3 链表实战

3.1 实践中如何选择数组和链表

在实践中,数组简单易用,使用的是连续的内存空间,可以更好地利用CPU的局部性原理,预读数据,提高访问效率。而链表则相反。

数组的缺点是大小固定,或者扩容是需要拷贝数据,性能差。链表则是动态变化。

数组省内存,而链表不是,因为指针占用内存。链表的节点创建和删除在Java中会导致频繁的堆内存申请和释放,导致频繁的GC。

3.2 链表实现和应用中的编码技巧

3.2.1 理解链表节点中的指针或者引用

指针或者引用,就是某一个变量值的地址,通过这个地址的值可以找到这个变量。

3.2.2 警惕指针丢失和内存泄漏

1
2
p->next = q;
q->next = p->next;

正确的代码是

1
2
q->next = p->next;
p->next = q;

对于需要手动管理内存,如果指针丢失或者删除节点后没有释放,都会导致内存泄漏。对于有垃圾回收的语言,主动置值为null可以加快垃圾回收。

3.2.3 哨兵节点简化代码

在p节点处插入一个新的节点:

1
2
new_node->next = p->next;
p->next = new_node;

如果是一个空列表,则需要特殊化处理:

1
2
3
if (head == null) {
head = new_node;
}

删除操作也是类似,会有特殊的代码逻辑处理。

哨兵节点就是一个空节点,不包含数据,它一直存在。使用哨兵节点,上面的代码就可以使用统一的逻辑进行处理。

哨兵在插入排序,归并排序,动态规划等算法中都有应用,主要目的就是为了简化代码的实现或者提高性能。

3.2.4 特别要照顾边界条件

链表相关的边界条件:

  1. 空链表
  2. 只有一个节点
  3. 只有两个节点
  4. 头节点和尾节点的处理

3.2.5 画画图,多写多练

诀窍:花上一整天,一个周末去写,一遍又一遍。

链表相关练习册:

  1. 单链表反转
  2. 链表中环的检测
  3. 两个有序的链表合并
  4. 删除链表倒数第 n 个结点
  5. 求链表的中间结点
  6. 回文字符串问题。如果字符串是使用单链表存储,如何判断一个回文字符串,如何更好地解决,时间和空间复杂度是多少?
    链表反转
  7. 约瑟夫问题
  8. LRU缓存实现。

3.2.6 链表代码实现学习

  1. Linux内核中的链表实现。
  2. Java中的LinkedHashMap就是使用双向链表实现的, LinkedList实现。