【算法&数据结构篇】——数组和链表

落日映苍穹つ 2023-02-11 13:28 206阅读 0赞

算法和数据结构都是非常基础的内容，经常使用，但是又很容易被忽视，而被重视的时候往往是面试官提问的时候。之前很不理解为什么面试官总喜欢问算法和数据结构，日常价值不大的东西。后来随着工作的深入，越发的理解

**         算法+数据结构=程序**

之所以后来理解了这个公式，系统学过算法和数据结构的知识，清楚的知道它们代表什么，才能有自身真正体会。

**什么是数据结构？**

是数据的组织，管理和存储格式，其目的为了更高效地访问和修改数据。数据结构是算法的基石

常见的数据结构有

1、线性结构

数组，链表，基于它们衍生的栈，队列，哈希表等

2、树

相对复杂的数据结构，代表二叉树

3、图

更为复杂的数据结构，因为图中有很多关联关系

**什么是算法？**

在数学领域里，算法是用于解决某一类问题的公式和思想。在计算机科学领域，本质是一系列程序指令，用于解决特定的运算和逻辑问题。算法的应用多种多样。例如下面，包含又不仅仅下面这些

1、运算

2、查找

3、排序

4、最优决策

结合日常的开发过程，我们通常做的就是也就是这些内容了。即程序的组成部分包含算法

程序的衡量标准通常是时间和空间，一般开发业务都会要求响应速度，这是为了客户体验度。其次空间占用，决定企业需要承担成本。从程序对应到算法上，同样适用，所以衡量算法的两个标准同程序。

时间复杂度——计算方式基本操作执行次数

每个算法的执行次数，对应就能转换成耗费时长。通常时间复杂度是O(1) O(logn) O(n) O(n²) O(nlogn)O(n³) O(mn) O(2^*n*)O(n!)等

空间复杂度——运行过程中临时占用存储空间大小

举个例子n个数中找到2个重复的整数。

有很多中实现方案，最简单的就是双重循环，每遍历到一个新整数就开始回顾之前遍历的所有整数，判断之中是否有相等的数，这样时间复杂度就是O(n²)，空间复杂度O(1)。

另一种实现方案，每遍历一个数，将就一个数存到数组中，在比较的时候直接去数组中去获取，如果能得到则证明重复，此时时间复杂度为O(n)，但是它占用空间使用了数组,空间复杂度O(n)

时间与空间的取舍

上述例子就是典型的牺牲空间来换时间，在大部分情况下，时间复杂度更重要些，所以宁可多些内存，也要提升速度。上述例子用，时间之所以提高，是因为我们使用数组，数组就是一种数据结构，而案例中方案一其实本质上使用的是数组，同样都是数据结构，但是空间复杂度却不相同。所以空间复杂度是离不开数据结构的，而算法和数据结构就是相亲相爱的一家人，这样才产生了爱的结晶——程序。

数组

有限个相同类型的变量所组成的有序集合，数组中的每一个变量被称为元素。而且数组还有一个特点，是在内存中顺序存储，因此可以实现逻辑上的顺序表，只要给出一个数组下标，就可以读取到对应的数组元素，根据下标读取元素的方式——**随机读取**。

![2020061322064313.png][]

读取   时间复杂度O(1)

插入，删除 时间复杂度O(n) 因为涉及到数组的插入、删除前后的元素移动。

优缺点

优点   数组拥有非常高效的随机访问能力，只要给出下标，就可以用常量时间找到对应元素。有一种高效查找元素的算法叫作二分查找，即利用数组该优势。

缺点  在插入和删除元素方面，由于数组元素连续紧密地存储在内存中，插入，删除元素都会导致大量元素被迫移动，影响效率。

**链表**

**       **链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

![20200613220404970.png][]

查询 时间复杂度 O(n)