《数据结构与算法-王争》学习笔记，记录备查

基本概念

数组（Array）是一种线性表数据结构。他用一组连续的内存空间，来存储一组具有相同类型的数据。

线性表，数据排成一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。主要数据结构有：数组、链表、队列、栈等。

非线性表，主要有二叉树、堆、图。

操作

随机访问

正由于数组的两个特性线性表和连续的内存空间，才使得数据支撑通过下标的随机访问。通过下标随机访问时，计算机的寻址可通过下边公式计算得到：

a[i]_address = base_address + i * data_type_size

要访问的元素地址等于数据的地址加上访问元素下标和元素空间大小的乘积。

这里需要注意，随机访问是依赖下标的。即可通过下标随机访问，时间复杂度为O(1)。若通过值，即使是排好序的数据，时间复杂度最好也为O(logn)。

插入

若数组为有序数组，插入到某下标的元素时，为了保持有序性，需要将之后的元素依次后移，时间复杂度为O(n)。

若数组为无序数据，插入某下标元素时，可将之前元素移至末尾后直接插入，时间复杂度为O(1)。

删除

删除某个中间元素时，为了保持数据内存的连续性，需要将之后的元素往前移，时间复杂度为O(n)。

删除开头元素时，时间复杂度为O(n)。删除结尾时，时间复杂度为O(1)。所以删除的平均时间复杂度为O(n)。

在删除时，可合并删除的操作，以达到减少搬移元素的次数，从而提高效率。

应用

注意数组越界问题

单看数据结构数组，当访问下标超出数组长度的数据时，并没有数据。针对这种下标越界的情况，不同的语言有不同的处理。像C语言，它不会有任何提示，所以这种情况很难发现。Java/Python 等略高级的语言，它们都对数组做了封装，对该种越界问题做了处理，当遇到事，就会抛出对应的错误。

总结

每种高级的编程语言几乎都有数组这个数据结构，它们是数据结构的封装，或者叫容器类。平时业务开发，使用它们即可，它们从语言层面封装了数组的一些操作。对应更底层的开发，追求极致的效率，那么直接用数组更好。