Python算法札记4-数组

数组

数组简介

数组也是一种线性存储排列的数据结构。

• 访问数据十分方便

• 添加和删除非常耗时间

  
  image.png

数组的下标通常是从0开始，类似于Python中切片的索引从0开始

特点

数组是按照顺序存储在连续空间之内的，通过数组下标计算内存地址

• 顺序存储
• 连续空间
• 方便访问

添加数据

• 在末尾增加存储空间
• 把已有数据移开，腾出空间
• 在空出来的位置添加指定的数据

看个栗子

image.png

删除数据

• 先把指定位置的数据删除
• 再把其他位置的数据一个个移动，用来填充空出来的位置
• 最后把末尾的多余空间删除

运行时间

假设有n个数据，

• 由于是通过内存地址直接访问（随机访问），运行时间仅为O(1)；
• 如果是添加或者删除数据，若位置在两端，则运行时间为O(n)

链表和数据比较

-	访问	添加	删除
链表	慢	快	快
数组	快	慢	慢