欢迎光临散文网 会员登陆 & 注册

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

2021-11-06 17:09 作者:烤考食Cox  | 我要投稿

P3 链表的基本介绍


链表:基本介绍 P3 - 00:05


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

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


链表:基本介绍 P3 - 07:50


  • 0是无效地址,即null,不指向任何节点
  • 指针变量需要4个字节
  • 指向节点的指针
  • 我们始终保持的关于列表的唯一信息是头节点的地址
  • tips:课本里的头节点不是指第一个节点,而是一个空数据的,next指向第一个节点的特殊节点:
  • 访问链表的某个元素,只能从头开始一个一个的找,因此时间成本不是恒定的,会和列表的大小成正比,假设列表大小和元素都是n,最坏情况下,遍历所有元素,时间复杂度O(n)
  • 好处是插入操作不需要复制,可以按需创建和释放节点,不必猜测列表大小


P4 数组和链表优缺点对比


数组 vs 链表 P4 - 00:19


实际上不存在一个数据结构要好于另一个数据结构的说法,根据需求选择最优解,比如与这个数据结构相关的最频繁的操作,数据量的大小等因素。

本节通过对比,了解什么情况下使用数据和链表较好(注:这里的讨论的链表是经典结构,没有包括循环链表等结构)

  1. 【访问元素的成本】


数组 vs 链表 P4 - 01:15


如果你有一个需要始终访问列表中元素的要求,选数组更好

2.【内存的使用】


数组 vs 链表 P4 - 04:33


  • 数组

优:


缺:

1)当数组被创建时,它占用的内存就是固定的

2)会存在某些空间没被使用

3)当插入的数据溢出时,还要新建,复制,消耗更多的时间成本

4)当我们可能想创建一个非常非常大的数组时,可能没有那么大的一块连续的内存

  • 链表

优:

1)占用的内存可变

2)没有未使用的内存

缺:

1)指针变量会占用额外的内存,但是不同情况不同利弊:

a.当data数据部分是简单的数据类型,占用内存少,那么随着数据量增加,相比数组,链表会使用更多的内存。

b.当data数据部分是复杂的数据类型,占用的字节比指针大得多,那么相比数组,链表对内存的使用效率会更高。


3.【插入元素的时间成本】


数组 vs 链表 P4 - 08:40


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.【哪个使用更简单】


数组 vs 链表 P4 - 11:42


数组:更容易实现和使用

链表:在C或C++中“实现”时更容易出错,比如段错误和内存泄漏


P5 链表:C/C++实现


链表:C/C++实现 P5 - 00:14


前提是要有一些使用C/C++指针的经验并了解动态内存分配的概念,这里的推荐课程:https://www.bilibili.com/video/BV1bo4y1Z7xf/

1.【逻辑视图】

也可以解释为链表的名称

  • tips:课本里的头节点不是指第一个节点,而是一个空数据的,next指向第一个节点的特殊节点:


2.【代码实现】


链表:C/C++实现 P5 - 02:52


定义(整型链表)

如果你是C++


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

遍历

末尾插入

tips:头指针(A)一般不应该被改变


P6 链表:头插入实现


链表:头部插入一个节点 P6 - 00:17




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

分享到微博请遵守国家法律