3.增删查：掌握数据结构基本操作

3-1 代码对数据的处理

回顾上一个例子，在数组中找到出现次数最多的元素，在处理数据时，我们主要做了以下几个步骤

• 查找：看能否在数据结构中找到该元素，也就是判断元素是否出现过
• 新增：针对没有出现过的情况，新增这个元素
• 改动：针对出现过的情况，需要对这个元素出现的次数加1

k-v 数据结构方式查找数据时，时间复杂度为O(1)

3-2 数据处理的基本操作

设计合理的数据结构，才能达到降低时间损耗的目的，而设计合理的数据结构，需要从问题本身出发

• 首先我们分析这段代码到底对数据先后进行了哪些操作
• 然后再根据分析出来的数据操作，找到合理的数据结构

代码对数据处理的操作类型非常少，代码对数据的处理就是代码对输入数据进行计算，得到结果并输出的过程。
数据处理的操作就是找到需要处理 的数据,计算结果，再把结果保存下来，总结过程为:

• 找到要处理的数据，这就是按照某些条件进行查找
• 把结果存到一个新的内存空间中，这就是在现在数据上进行新增
• 把结果存到一个已使用的内存空间中，这就需要先删除内存空间中的已有数据，再新增新的数据

经过对代码的拆解，会发现即使很复杂的代码，对数据处理也就3个基本操作：新增、删除、查找；总结步骤：

• 首先，这段代码对数据进行了哪些操作？
• 其次，这些操作中，哪个操作最影响效率，对时间复杂度的损耗最大
• 最后，哪种数据结构最能帮助你提高数据操作的使用效率

3-3 数据操作与数据结构的案例

3-3-1 第一个例子：查找

例子：从复杂的数据结构中，找到满足某个条件的元素 对于一个数组，找到第二个元素并输出

 这个例子很简单
 直接使用数组的index索引就可以，这个和数组的长度无关
 所以复杂度为O(1)

3-3-2 第二个例子：链表查找

例子：如果是链表，如果查找链表中第二个元素并输出
链表和数组一样，，都是O(n)空间复杂度，区别在于，数组有index索引，链表没有，链表有指针
链表，查找时，需要一个一个元素，按照顺序逐一去查找，所以时间复杂度就是O(n)

3-3-3 第三个例子：数值查找

例子：要查找数组中，值为5的元素，是否存在
按照顺序一个一个去查找，这样时间复杂度为O(n)
有没有办法，可以降低时间复杂度呢？答案是按照字典的方式k-v来查找

3-3-4 第四个例子：复杂数据结构中新增一条数据

• 第一个是在这个复杂的数据结构的最后，新增一条数据
• 第二个是在这个复杂的数据结构中的某一个位置，新增一条数据

这两个的区别在于：新增数据之后，是否导致原数据位置顺序改变

• 1.假设在最后新增

首先，通过查找操作找到数据结构中最后一个数据的位置
接着，在这个位置之后，通过新增操作，赋值或插入一条新的数据即可

• 2.假设在数据结构中间某个位置新增

如果是在中间插入，就会对插入元素的位置之后的元素产生影响，导致数据的位置变化

3-3-5 第五个例子：复杂数据结构中删除一条数据

• 第一个是在这个复杂的数据结构的最后，删除一条数据
• 第二个是在这个复杂的数据结构中的某一个位置，删除一条数据

这两个的区别在于：删除数据之后，是否导致原数据位置顺序改变

3-3-5 第六个例子：在第二个元素后新增一个元素、再删除第一个满足大于6的元素

第一步：在第二个元素之后新增一条数据；这里面包含了查找和新增两个操作
第二步：删除第1个满足数值大于6的元素；这里包含了查找和删除两个操作

3-4 总结

• 处理数据的基本操作只有三个：增、删、查；
• 增和删又可以细分为在中间删除新增还是在末尾删除新增
• 几乎所有的数据处理都是这些基本操作的叠加