【强烈推荐】深入浅出数据结构 - 顶尖程序员图文讲解 - UP主翻译校对 (已完

P3 链表的基本介绍
- 【数组线性表的内存使用】使用数组来实现动态列表,就内存利用率和消耗量而言,它不是最有效的。在学习链表之前我们有必要了解数组使用的限制。链表:基本介绍 P3 - 01:09
- 计算机中管理内存的东西叫内存管理器
- 一个字节一个内存空间,int类型是四个字节,一个int元素需要4个内存空间,这个内存块的地址是内存中第一个字节的地址。
- 计算机访问数组中任一元素的时间成本是恒定的:O(1),只要知道首地址和访问元素在表中的位置,通过就可以知道地址直接访问

- 数组是作为一个连续的内存块存储在内存中

- 当满元素的数组要插入新元素,需要创建新的更大的数组,复制旧内容并放入新内容,还要释放旧数组的内存空间。

2.【先看看链表是如何解决这个问题的】

- 0是无效地址,即null,不指向任何节点
- 指针变量需要4个字节
- 指向节点的指针
- 我们始终保持的关于列表的唯一信息是头节点的地址
- tips:课本里的头节点不是指第一个节点,而是一个空数据的,next指向第一个节点的特殊节点:

- 访问链表的某个元素,只能从头开始一个一个的找,因此时间成本不是恒定的,会和列表的大小成正比,假设列表大小和元素都是n,最坏情况下,遍历所有元素,时间复杂度O(n)
- 好处是插入操作不需要复制,可以按需创建和释放节点,不必猜测列表大小
P4 数组和链表优缺点对比
实际上不存在一个数据结构要好于另一个数据结构的说法,根据需求选择最优解,比如与这个数据结构相关的最频繁的操作,数据量的大小等因素。
本节通过对比,了解什么情况下使用数据和链表较好(注:这里的讨论的链表是经典结构,没有包括循环链表等结构)
- 【访问元素的成本】
如果你有一个需要始终访问列表中元素的要求,选数组更好

2.【内存的使用】
- 数组
优:
缺:
1)当数组被创建时,它占用的内存就是固定的
2)会存在某些空间没被使用
3)当插入的数据溢出时,还要新建,复制,消耗更多的时间成本
4)当我们可能想创建一个非常非常大的数组时,可能没有那么大的一块连续的内存

- 链表
优:
1)占用的内存可变
2)没有未使用的内存
缺:
1)指针变量会占用额外的内存,但是不同情况不同利弊:
a.当data数据部分是简单的数据类型,占用内存少,那么随着数据量增加,相比数组,链表会使用更多的内存。
b.当data数据部分是复杂的数据类型,占用的字节比指针大得多,那么相比数组,链表对内存的使用效率会更高。

3.【插入元素的时间成本】
1)在列表的开头插入元素
数组:将每个元素向后移动一个位置,花费时间与列表大小成正比:O(n)
链表:创建新节点,next指向旧的第一个节点,头指针指向新节点。时间成本是恒定的:O(1)

2)在数组末尾插入元素
数组:如果数组未满,只需要写到列表的下一个更高的索引,时间复杂度恒定O(1);如果数组已满,得创建新数组并复制先前内容,时间复杂度O(n),n为列表大小
链表:需要遍历整个列表,找到最后一个元素的位置才能将创建的新节点链接在后面,时间复杂度为O(n),n为列表元素数量
3)在列表的第 i 个中间位置插入
数组:平均情况下,插在n/2的位置,也就要移位n/2,n为列表元素数量,时间复杂度为O(n)
链表:也必须遍历到该位置才能做调整,时间复杂度为O(n)
Tips:删除操作也会有这三种情况,时间复杂度也和插入一样
4.【哪个使用更简单】
数组:更容易实现和使用
链表:在C或C++中“实现”时更容易出错,比如段错误和内存泄漏
P5 链表:C/C++实现
前提是要有一些使用C/C++指针的经验并了解动态内存分配的概念,这里的推荐课程:https://www.bilibili.com/video/BV1bo4y1Z7xf/
1.【逻辑视图】

也可以解释为链表的名称
- tips:课本里的头节点不是指第一个节点,而是一个空数据的,next指向第一个节点的特殊节点:

2.【代码实现】
定义(整型链表)
如果你是C++


课本里typedef struct Node{ ... }LNode,*linklist;这段的意思是给Node类型变量和Node*类型指针起了个别名,使用时LNode和Node不做区分,当用户声明指针时可以写linklist head;就不用多写个*号(我觉得没什么意义),声明时一定要用typedef。
遍历

末尾插入

tips:头指针(A)一般不应该被改变
P6 链表:头插入实现