在程序中，经常需要一组（通常是同为某个类型的）数据元素作为整体管理和使用，需要创建这种元素组，用变量记录它们，传进传出函数等。一组数据中包含的元素个数可能发生变化（可以增加或删除元素）。

对于这种需求，最简单的解决方案便是将这样一组元素看成一个序列，用元素在序列里的位置和顺序，表示实际应用中的某种意义的信息，或者表示数据之间的某种关系。

这种的一组序列元素的组织形式，我们可以将其抽象为线性表，一个线性表是某类元素的一个集合，还记录着元素之间的一种顺序关系。线性表是最基本的数据结构之一，在实际程序中应用非常广泛，它还经常被用作更复杂的数据结构的实现基础。

根据线性表的实际存储方式，分为两种实现模型：

  • 顺序表：将元素顺序地存放在一块连续的存储区里，元素间的顺序关系由它们的存储顺序自然表示
  • 链表：将元素存放再通过链接构造起来的一系列存储块中

数组是一种线性表数据结构，是一种顺序存储结构。它用一组连续的内存空间，储存一组具有相同类型的数据。

连续的内存空间和相同类型的数据。正是因为这两个限制，它才有了一个堪称“杀手锏”的特性：“随机访问”。

但有利也有弊，这两个限制也让数组的很多操作变得非常低效，比如要想在数组中删除、插入一个数据，为了保证连续性，就需要做大量的数据搬移工作。

顺序存储结构的三个属性：

  • 存储空间的起始位置：数组 data，它的存储位置就是存储空间的存储的位置
  • 线性表的最大存储容量：数组长度 MaxSize
  • 线性表的当前长度：length

数组的长度是存放线性表的存储空间的长度，存储分配后这个量是一般是不变的。
线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的。
在任意时刻，线性表的长度应该小于等于数组的长度。

存储器中每个存储单元都有自己的编号，这个编号称为地址。

随机访问

由于它们存储在连续的位置，因此可以使用它们的索引来计算内存地址，以便随机访问数据。

我们知道，计算机会给每个内存单元分配一个地址，计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时，它会首先通过下面的寻址公式，计算出该元素存储的内存地址：

  1. a[i]_address = base_address + i * data_type_size
  3. LOC(ai) = LOC(a1) + (i-1)*c
  • base_address：数组的起始内存地址
  • data_type_size：数组中每个元素的大小


获取操作

线性表 L 中的第 i 个位置元素值返回即可。

插入操作

插入算法的思路：

  • 如果插入位置不合理，抛出异常
  • 如果线性长度大于等于数组长度，则抛出异常或动态增加容量
  • 从最后一个元素开始向前移动到第 i 个位置，分别将它们都向后移动一个位置
  • 将要插入元素填入位置 i 处
  • 表长加 1

但是如果我们要操作的数据并不需要保持一定的顺序，那我们可以直接将第 k 位的数据搬移到数组的最后面，把新数据放到k位置上，可以避免大量搬移数据的操作。

  1. public class TestOpArray {
  2.     public static void main(String[] args) {
  3.       // 解决数组的长度不可变的问题
  4.     int[] arr = new int[] {9,8,7};
  5.     // 快速查看数组中的元素
  6.     System.out.printIn(Arrays.toString(arr));
  7.     // 要加入数组的目标元素
  8.     int dst = 6;
  10.     // 创建新数组，长度是原数组长度+1
  11.     int[] newArr = new int[arr.length+1];
  12.     // 把原数组中的数据全部复制到新数组中
  13.     for(int i = 0; i < arr.length; i++){
  14.         newArr[i]=arr[i];
  15.     }
  16.     // 把目标元素放入新数组的最后
  17.     newArr[arr.length]=dst;
  18.     // 新数组替换原数组
  19.     arr=newArr;
  20.   }
  21. }

删除操作

删除算法的思路：

  • 如果删除位置不合理，抛出异常
  • 取出删除元素
  • 从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置
  • 表长减 1

同插入一样，我们可以把多次删除批量执行。比如要删除数组的前k项，为了避免搬移k次，我们先记录已经删除的数据。每次并不是真正的删除。当数组没有更多的空间的时候，我们才执行一次真正的删除操作，提高性能。

时间复杂度

  • 插入/删除最后一个元素，时间复杂度为 O(1)
  • 插入/删除第一个元素，时间复杂度为O(n)
  • 至于平均情况，取中间值O((n-1)/2)
  • 简化后O(n)

线性表的顺序存储结构，在存、读数据时，不管是哪个位置，时间复杂度都是O(1)。而在插入或删除时，时间复杂度都是O(n)。这就说明，它比较适合元素个数不太变化，而更多是存取数据的应用。

  • 优点：
    • 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
    • 可以快速地存取表中任一位置的元素
  • 缺点
    • 插入和删除操作需要移动大量元素
    • 当线性表长度变化较大时，难以确定存储空间的容量
    • 造成存储空间的“碎片”