大家好,我是梁唐。 在这一篇文章当中我们正式进入了全书第四章的内容——链表。 链表是一个非常基础的数据结构,也在各类LeetCode问题、面试题当中反复出现。并且还是很多高级数据结构的基础,虽然实际应用相对没有那么广泛,但仍然不可轻视。 链表简介在百度百科当中对于链表的定义是:链表是一种非连续、非顺序的数据结构,数据元素中的逻辑顺序是通过指针链接实现的。 对于萌新而言,看这段话估计犹如天书,每个字都认识,连在一起就似懂非懂。要搞明白链表究竟是什么,需要我们从链表本身的特性开始说起。而要展示链表的特性,最好的方法就是来看一下链表的定义代码。 struct ListNode { 这是一个经典的链表节点的结构体,里面只有两个元素, 这些节点就是这样通过 为什么说它是非连续、非顺序的数据结构呢?原因也在这里,因为在计算机的内存当中,这些节点不是紧挨着存储的,中间可能隔了很远。 我们知道数组的元素都是紧挨着存储的,当前元素的下一个内存位置就是下一个元素。所以数组只需要知道了头元素的地址,就知道了所有元素的地址。在初始化的时候,我们要告诉编译器数组的类型以及它的长度,这样编译器会直接帮我们直接分配一块固定大小的内存来存储数据的元素。 但链表不是,链表里每个元素的地址都存在上一个元素当中。元素完全可以不用挨着,反正有地址,在哪里都能访问到。链表也没办法直接初始化链表中节点的数量,因为链表中每个节点的地址不固定,所以节点都是一个一个插入进去的,随时需要随时插入都可以。可能上一个节点和下一个节点之间相隔了很远,想要连续都没办法。 链表类型理解了链表的特性和基本定义之后,我们再来看看不同类型的链表。 目前链表主要有三种类型:单链表、双向链表和循环链表,其实我个人觉得这不太能算作是链表的类型,其实是链表的三种应用方式。但不管叫什么,相信大家只要理解了链表的定义之后,不难弄懂其中的差别。 单链表就是我们刚才介绍的最普通的链表,每个节点只有一个 有的时候我们可能也会想要能从后往前遍历节点,这样的话就需要我们每个节点也存储下它之前的节点的位置。所以就需要在结构体当中增加一个指针,一般我们用 而循环链表更多的像是一个trick,当我们把链表的最后一个节点的 链表的操作最后来介绍一下链表的操作,链表的操作有三种:插入、删除和遍历。其中遍历很好理解,我们不同地访问节点的 链表的插入下面来说说链表的插入,假设当前节点是 首先,我们要先创建一个新的节点,它的值是我们要插入的值:
接着, 我们要把 所以我们要先把 tmp->next = cur->next; 链表的删除理解了插入,删除其实就是反向操作。假设我们要删除
为了防止内存泄漏,我们最好把要删除的节点 auto tmp = cur->next; 这里要注意,由于我们使用了 链表的原理和操作逻辑上来说并不难,只不过由于涉及指针的操作和变更,要特别小心。很容易由于指针使用不当导致一些潜在的问题和bug,另外指针也会一定程度上增加debug和代码编写的难度。因此初学者在学习这个部分时非常容易浮躁,这是特别要当心的。 关于链表的理论部分就写这么多,之后我们将会来看几道例题来练习。 感谢大家的阅读,如果喜欢的话,恳请帮忙转发扩散。算法学习之旅,与你同行。
|
|
来自: mynotebook > 《待分类》