算法图解数组与链表

算法图解 数组与链表

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

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

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

爱好： Americano More Ice !

数组

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

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

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

	数组(array)	链表(list)
读取	O(1)	O(n)
插入	O(n)	O(1)

需要注意的“术语”

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

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

场景1：中间插入元素

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

场景2：删除某个元素

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

	数组(array)	链表(list)
读取	O(1)	O(n)
插入	O(n)	O(1)
删除	O(n)	O(1)

实际使用

使用次数：数组>链表

为啥呢？

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

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

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

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

画了个简图hhh

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

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

如果小白的博客有建议或批评的，下方留言即可！如果觉得小白此文章有帮助，留下你的点赞????????，Star Click和收藏❤️哦！谢谢谢！