【C语言从入门到精通】链表：由浅入深！

左手的ㄟ右手 2023-01-07 08:47 145阅读 0赞

今天又到了算法的主题了，上次我们聊到了数组：面试中的疑难点，这次我们来聊另外一种线性结构，**链表**。

## 本质 ##

虽然链表与数组一样都是线性结构，但它们之间还是有本质的区别的。

数组在内存中是一块连续的存储区域，而链表可以支持随机存储，非连续的存储空间。

![aceb1407fc5942ae0e1bedccd5665607.png][]

链表的种类可以分为：**单链表、双向链表、循环链表、双向循环链表。**

它们的本质都是一样的，不同的是具体的表现与应用。

> 简单来说，对于单链表是每一个节点都有一个 next 后续指针，它都指向当前节点的下一个链表节点；对于链表的尾节点，由于是链表的最后一个节点，所以它的 next 为 null 。

双向链表与单链表所不同的是，它除了有 next 指针之外，还有 prev 前驱指针，它指向于当前节点的上一个节点；特殊的，链表的头节点的 prev 为 null 。

循环链表与单链表的区别是，它的最后一个节点的 next 将不再为 null ，而是指向头节点或者链表的其它位置节点。

而对于双向循环链表也是同样的原理。

## 插入 ##

我们都听过这么一句话，**链表适合插入与删除。**这主要是由于链表自身的数据结构决定的。

对于单链表来说，向已知的一个节点后插入一个新的节点，它所要做的事情就是将当前节点的 **next **指针指向新的节点，然后再将新节点的 **next **指向指向当前节点的之前的后续节点。

而这个过程不需要任何数据的迁移，只需改变节点的 **next **指针指向，所以它的时间复杂度为** O(1)** 。

![a71a0750a04a28252d17130aeb4cb57c.png][]

看图很简单，但真正去实现的话，不一定都会，尤其是首次接触到链表的读者。容易犯的是下面这个错误：

> node.next = newNode
> 
> newNode.next = node.next

犯这个错误的本质绝大多数还是对链表的指针理解不到位。其实对于指针的理解，我们只需记住一点，指针指向的是节点在内存中的地址。

**改变指针就是改变指向的地址。**

正确的做法是下面这种：

> newNode.next = node.next
> 
> node.next = newNode

当然，为了杜绝这个问题，还有一个简单的方法就是多练，写多了自然就会了。

所谓书读百遍其义自见，应该就是这个道理。

还有上面的时间复杂的是基于一个前提的：已经找到了插入节点的位置。而查找当前插入点，需要通过遍历整个链表的，所以链表中查找一个节点的时间复杂度为 O(n) 。

> 可能有的读者一直都有一个疑问，为什么有了单链表还有出来一个双向链表，你看这插入双向链表也是与单链表一样，时间复杂度都为 O(1) ，而双向链表由于它每个节点都额外需要 prev前驱节点，导致它更加浪费内存。

针对这类问题，我们将上面的插入位置做一下调整。

现在已知了当前节点的位置，下面需要将新节点插入到当前节点的前面。

如果是单链表，由于只有 next 指针，所以只能重新遍历链表，找到当前节点的上一个节点，然后再重复上面的转移指针的步骤，此时时间复杂度为 O(n) 。

而对于双向链表，由于它还有 prev 执行，所以它可以直接改变 prev 的指向，来将新节点插入到当前节点的前面，所以它的时间复杂度为 O(1) 。

![9b69d2bfa324dd29f0a3630356147c51.png][]

正是由于这特性，在实际运用中，双向链表比单链表更加普遍，例如我们所熟悉的 LinkedList：

private static class Node<E> {
    
        E item;
    
        Node<E> next;
    
        Node<E> prev;
    
        Node(Node<E> prev, E element, Node<E> next) {
    
            this.item = element;
    
            this.next = next;
    
            this.prev = prev;
    
        }
    
    }

————————————

## 删除 ##

链表的删除与插入原理类似，都是改变节点的指针指向。

对于单链表，如果删除当前节点的后续节点，只需将当前节点的 next 指针指向当前节点的后续节点的后续节点。文字有点绕，还是直接看代码

> node.next= node.next.next

而对于双向链表来说，除了改变 next 节点，还要改变 next 指向的 prev 节点。

> node.next= node.next.next
> 
> node.next.prev= node

它们的时间复杂度都为 O(1)

另外的删除节点为当前节点的前驱节点。这个与插入原理类似，这里就不做详细分析。单链表的时间复杂度为 O(n) ，双向链表的时间复杂度为 O(1) 。

### **注意点：** ###

现在我们已经对链表有了一个较全面的了解。但开始上手写的时候还是会很容易犯错。

下面我结合自己的一点经验还对容易犯的错误做一个总结，并对其提出相应的解决方案。

### **1、指针的指向问题** ###

首先是写链表时，对于指针的指向错乱问题。

如果遇到简单的插入删除，步骤不是很频繁的情况，相信大家都能够很容易的完成。一旦涉及到链表的指针频繁改变，亦或者是双向链表(再加一个前驱指针)，这时犯错率就会直线提升。

**解决方案是：**

**（1）**放下心来仔细思考，理清整个过程，再动手写代码。

**（2）**借助辅助工具，例如停下手来，找只笔找张纸，把链表的结构画出来，然后在画它们间的指针指向。

**（3）**简单粗暴，多看多练。基本上做个每天做个一两道，坚持一星期基本就可以了。

## ##

### **2、边界问题** ###

在写链表的过程中，还有一种情况就是对边界的处理。可能是忘了对边界的处理；也可能是直接处理错误。

对于链表的边界就是它的头节点与尾节点。由于它们的特殊性，针对它们的插入与删除，可能与别的节点不同，需要额外进行特殊处理。

> 针对这种问题，我们需要做的就是，写完链表之后，时刻都要提醒自己是否对边界做了处理，如果做了也要停下来思考一遍是否处理正确。

这样就能很好的保证边界处理的正确性。

千万不要偷懒，别因为这个边界问题导致在面试过程中的评分打折扣。因为这能从侧面体现一个人的思维的全面与缜密性。

### 3、哨兵优化 ###

针对上面的边界问题，有没有代码上的优化呢？

有的，这里要说的就是哨兵优化。

> 所谓的哨兵，简单的理解就是固定一个标识，让它像边界的士兵一样，一直屹立在他的边界岗位，守卫国土的安全。

例如，我们拿上面的双向链表的删除来说。

对于非头节点的删除，我们只需找到当前的节点，然后改变它前后节点的 next 与 prev 指针的指向即可：

> node.prev.next = node.next
> 
> node.next.prev = node.prev

现在如果当前节点是头节点，上面的代码就不能运行，因为头节点的 prev 节点为 null ，所以常规的做法是做特殊判断

> if (node == head) \{
> 
>     node.next.prev = null
> 
> \}

这样就是边界问题的处理，如果你记得处理那还好，一旦忘了就导致异常。

而使用哨兵就能够完全规避边界的判断，我们来看具体使用方式：

// 建立哨兵，新建#节点，并将其next指针指向头节点
    
    val guard = LinkedNode("#")
    
    val newLinked = guard.next = head
    
    head.prev = guard
    
    ...
    
    // 节点删除(包括头节点)
    
    node.prev.next = node.next
    
    node.next.prev = node.prev
    
    // 返回删除后的链表
    
    return newLinked.next

————————————

![cf445240a1449eb636bd24b4c16c6e74.png][]

### 经典实例 ###

下面是一些关于链表的经典的实例，如果对链表还不熟悉的推荐亲自去写一遍。写完之后你将对链表有一个全新的认识。

1、环的检测；

2、单链表反转；

3、删除链表倒数第n个结点；

4、LRU；

5、求链表的中间结点；

6、两个有序链表的合并；

7、单链表判断回文。

—— 加油 ——

![c543c6ebff39be72cc7b8b5d654aa5c6.png][]

最后，不管你是转行也好，初学也罢，进阶也可，如果你想学编程~

【**值得关注**】我的**[ C/C++编程学习交流俱乐部！][C_C]****【点击进入】**

问题答疑，学习交流，技术探讨，还有超多编程资源大全，零基础的视频也超棒~

[aceb1407fc5942ae0e1bedccd5665607.png]: /images/20221119/4e2d74f126d241d39de7b47f9cd4a54c.png
[a71a0750a04a28252d17130aeb4cb57c.png]: /images/20221119/72a43853d25e4a0d96292242a59551c2.png
[9b69d2bfa324dd29f0a3630356147c51.png]: /images/20221119/7dd169489dc141a097f8a5c2b248503b.png
[cf445240a1449eb636bd24b4c16c6e74.png]: /images/20221119/e4ba9b43034845bcb38411e17e7a3915.png
[c543c6ebff39be72cc7b8b5d654aa5c6.png]: /images/20221119/73efcb4e1e454b47a753caf6e7b78ff1.png
[C_C]: https://jq.qq.com/?_wv=1027&k=DJSbr1Rp