链表其实并不难，结构体里加指针

作者 | 梁唐

出品 | 公众号：Coder梁（ID：Coder_LT）

大家好，我是梁唐。

在这一篇文章当中我们正式进入了全书第四章的内容——链表。

链表是一个非常基础的数据结构，也在各类LeetCode问题、面试题当中反复出现。并且还是很多高级数据结构的基础，虽然实际应用相对没有那么广泛，但仍然不可轻视。

链表简介

在百度百科当中对于链表的定义是：链表是一种非连续、非顺序的数据结构，数据元素中的逻辑顺序是通过指针链接实现的。

对于萌新而言，看这段话估计犹如天书，每个字都认识，连在一起就似懂非懂。要搞明白链表究竟是什么，需要我们从链表本身的特性开始说起。而要展示链表的特性，最好的方法就是来看一下链表的定义代码。

struct ListNode {
   int val;
    ListNode *next;
};

这是一个经典的链表节点的结构体，里面只有两个元素，val和next。这里的val就是我们希望存入链表的值，next从它的类型可以看得出来，它是一个指向自身类型的指针。通过这个指针我们可以找到另外一个节点，这个节点也是ListNode类型，其中两个元素，一个是val一个是next。我们再通过它的next指针又可以继续往下访问……

这些节点就是这样通过next指针串联在一起，逻辑上就好像构成了一条链：

为什么说它是非连续、非顺序的数据结构呢？原因也在这里，因为在计算机的内存当中，这些节点不是紧挨着存储的，中间可能隔了很远。

我们知道数组的元素都是紧挨着存储的，当前元素的下一个内存位置就是下一个元素。所以数组只需要知道了头元素的地址，就知道了所有元素的地址。在初始化的时候，我们要告诉编译器数组的类型以及它的长度，这样编译器会直接帮我们直接分配一块固定大小的内存来存储数据的元素。

但链表不是，链表里每个元素的地址都存在上一个元素当中。元素完全可以不用挨着，反正有地址，在哪里都能访问到。链表也没办法直接初始化链表中节点的数量，因为链表中每个节点的地址不固定，所以节点都是一个一个插入进去的，随时需要随时插入都可以。可能上一个节点和下一个节点之间相隔了很远，想要连续都没办法。

链表类型

理解了链表的特性和基本定义之后，我们再来看看不同类型的链表。

目前链表主要有三种类型：单链表、双向链表和循环链表，其实我个人觉得这不太能算作是链表的类型，其实是链表的三种应用方式。但不管叫什么，相信大家只要理解了链表的定义之后，不难弄懂其中的差别。

单链表就是我们刚才介绍的最普通的链表，每个节点只有一个next指针用来寻找下一个节点的位置。所以每个节点只知道后面的位置，不知道前面，只能单向遍历。

有的时候我们可能也会想要能从后往前遍历节点，这样的话就需要我们每个节点也存储下它之前的节点的位置。所以就需要在结构体当中增加一个指针，一般我们用prev来存储前继，即previous的简写。

而循环链表更多的像是一个trick，当我们把链表的最后一个节点的next指针指回到链表的头节点，就得到了一个环，整个链表将不再有头尾，从每一个节点出发都可以遍历完其他所有节点。不过这种链表只在极少数特殊的场景当中出现，一般情况下不会遇到。

链表的操作

最后来介绍一下链表的操作，链表的操作有三种：插入、删除和遍历。其中遍历很好理解，我们不同地访问节点的next指针获取下一个节点，就相当于遍历了链表中的每一个节点。

链表的插入

下面来说说链表的插入，假设当前节点是cur，我们要在cur节点之后插入一个新的元素。应该怎么处理呢？

首先，我们要先创建一个新的节点，它的值是我们要插入的值：

auto tmp = new ListNode(val);

接着， 我们要把cur->next赋值成tmp。但是这里有一个问题，如果我们直接进行赋值，会导致原本的cur->next被覆盖。这样我们就找不到原本cur之后的内容了。相当于抛弃了cur之后的部分。

所以我们要先把cur->next的值记录在tmp->next当中，这样再来修改cur->next，就不会丢失了。

tmp->next = cur->next;
cur->next = tmp;

链表的删除

理解了插入，删除其实就是反向操作。假设我们要删除cur之后的元素，只需要将cur->next跳过要被删除的节点，指向它的下一个即可。

cur->next = cur->next->next

为了防止内存泄漏，我们最好把要删除的节点delete掉。同样，由于这里已经发生了变更，所以我们需要先缓存cur->next的地址。

auto tmp = cur->next;
cur->next = cur->next->next;
delete tmp;

这里要注意，由于我们使用了cur->next->next，要防止cur->next是空指针的情况，这会导致程序报错。

链表的原理和操作逻辑上来说并不难，只不过由于涉及指针的操作和变更，要特别小心。很容易由于指针使用不当导致一些潜在的问题和bug，另外指针也会一定程度上增加debug和代码编写的难度。因此初学者在学习这个部分时非常容易浮躁，这是特别要当心的。

关于链表的理论部分就写这么多，之后我们将会来看几道例题来练习。