数据结构与算法之美-数组

数据结构与算法之美-数组

概念及关键词

数组(Array)是一种 线性表 数据结构,它用一组 连续的内存空间,来存储一组具有 相同类型 的一组数据。

  • 线性表:顾名思义,线性表就是数据排成一条线一样的结构,每个线性表上的数据最多只有前后两个方向。其实除了数组,链表、队列、栈等也属于线性表结构。
  • 连续的内存空间和相同的数据类型:因为有这样的限制,数组才有了 随机访问 的特性。但有利也有弊,这两个限制也让数组很多操作变得很低效,比如想在数组中插入或删除一个数据,为了保证连续性,就要做大量的数据迁移工作。

优点

  • 支持下标随机访问:通过 a[i]_address = base_address + i * data_type_size 寻址公式访问指定下标的元素时间复杂度为O(1)。
  • 使用连续的内存空间,借助CPU的缓存机制,缓存行作为CPU缓存与物理内存之间进行数据交换的单位,可以实现数据的预读,提高访问效率。

缺点

  • 插入、删除一个数组元素很低效,最好O(1)、最坏O(n)、平均0(n)的时间复杂度。
  • 警惕数据越界。

数组与容器的选择

  • 容器封装了很多底层操作细节,包括插入和删除元素导致的数据迁移操作、数组空间不足需要动态扩容操作等。
  • 表示多维数据时,使用数组更为直观。
  • 业务开发容器即可,底层开发,如网络框架、性能优化选择数组。