算法图解(一) 数组与链表_图解数组中插入元素

最近在看算法图解，顺便将个人学习过程中的提炼，沉底一哈~
算法图解，一集一沉淀

导语：算法之路–数组与链表

作者：变优秀的小白，Click 进入主页

爱好：Americano More Ice !

QQ群(new): 811792998

算法第一集

算法图解(一) 数组与链表

数组

• 特点：在内存地址中相连
• 优点：执行效率高
• 缺点：初始化占用多余空间，浪费内存

由于数组的缺点，引出“链表”

• 优点：元素可存储在内存的任何地方
• 原因：每个元素存储下一个元素的地址，从而使一系列随机的内存地址串在一起
• 缺点：若元素需要跳跃，效率极差
  • ex：当访问最后一个元素，需访问从第一个查起，效率极差

需要注意的“术语”

元素的位置为索引，索引从0开始到N

O(1)=线性时间
O(n)=常量时间

场景1：中间插入元素

• 数组：
  • 1.若中间插入元素，必须将后面的数组后移
  • 2.若中间插入元素且没有足够空间，需要移动整个数组
• 链表：
  • 1.只需要修改前面一个元素的指向地址

场景2：删除某个元素

• 数组：
  • 1.若删除某个元素，必须所有元素向前移动一位
• 链表：
  • 1.若删除某个元素，只需要修改前一个元素指向地址即可

实际使用

使用次数：数组>链表

为啥呢？

• 原因：
  • 数组支持随机访问，读取速度快

访问方式有两种：随机访问 和 顺序访问

• 随机访问：可直接访问任一元素
• 顺序访问：访问必须从第1个元素开始访问

有没有一个最优解呢？“数组链表”

画了个简图hhh

数组链表：将同类构成链表，放入数组中，成为一个多链表的数组，达到了性能最大化，也就是最优解！

下集预告

算法图解(二) 二分查找

结束语：大家如果遇到什么疑问或者建议的地方，可直接留言评论！作者看到会马上一一回复！

如果小白的博客有建议或批评的，下方留言即可！如果觉得小白此文章有帮助，留下你的点赞

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/556366