数据结构与算法——数组
1. 概述
数组(Array)是一种很基础的数据结构,几乎绝大多数编程语言都会支持数组这种数据结构。数组是一种线性结构,使用一组连续的内存空间,来存储相同类型的数据。
所谓线性结构,就是指数据是前后排列的,只有前后两个方向,除了数组,其他的比如链表、栈、队列都是线性结构。
因为数组是使用连续的内存空间来存储数据的,所以数组的最大的特点就是支持根据下标随机访问数据,这是数组最大的优势。但是,有利就有弊,虽然数组高效的支持下标访问,只不过在插入和删除数据的时候就比较低效了,为了保证内存的连续性,必须要进行数据搬移。
2. 插入数据
先来看看插入操作,假如有一个数组 [3, 4, 6, 8, 7, 2, 5],第一种情况是插入的元素位于数组的最后一个位置,那么不用进行数据搬移,时间复杂度为 O(1) ,如果插入的位置是第一个,那么必须移动整个数组,时间复杂度为 O(n) 。
这里有另外一个处理思路:如果数组中存储的数据不在乎彼此顺序的话,那么插入数据的时候,我们可以直接将插入位置的元素放到数组最后一位,腾出位置给新的元素。就像下图这样:
3. 删除数据
再来看看删除操作,还是上面的数组 [3, 4, 6, 8, 7, 2, 5],如果删除的是最后一个元素,那么不需要进行数据搬移,如果删除的是第一个元素,那么数组每一个元素都会向前移动一位。
只不过,在某些场景下,如果不是特别追求数据的连续性,那么我们可以采用另一种思路来处理删除操作。例如数组的大小为 10 ,现在存储了 7 个元素,分别是 [3, 4, 6, 8, 7, 2, 5],如果我们要删除 3 4 6 这三个元素,我们先将其标记为删除,等到数组空间不够的时候,在集中性的进行数据搬移,这样就大大减少了数据搬移的次数!
是不是非常高效呢?
4. Java 容器
在 Java 语言中,提供了一个可以支持动态扩容的数组容器:ArrayList,如果你熟悉 Java 语言的话,几乎每天都会和这个容器打交道,它封装了一些数组的操作,并且在数组空间不够的时候,自动扩容为原来的 1.5 倍。
只不过,在使用 ArrayList 的时候,要是能够指定大小,最好指定,这样会减少申请内存空间和数据搬移的操作。
5. 代码示例
下面是简单的支持动态扩容的数组实现:
/* * 泛型动态数组 */ public class GenericArray<T> { private T[] data; private int count;//数组中存储的个数 public GenericArray(int capacity) { this.data = (T[]) new Object[capacity]; this.count = 0; } public GenericArray() { this(16); } //返回数组中元素的个数 public int getSize() { return this.count; } //返回数组容量 public int getCapacity() { return this.data.length; } //设置某个位置的数据 public void set(int index, T value) { if (count == data.length) { //扩容 resize(data.length * 2); } checkIndex(index); if (index == count) { data[count ++] = value; return; } //常规删除 for (int i = count; i < index; i --) data[i] = data[i - 1]; data[index] = value; count ++; } //在数组末尾插入数据 public void insert(T value) { set(count, value); } //删除数据 public T remove(int index) { if(index == count) throw new IllegalArgumentException("Index Illegal!"); checkIndex(index); T result = data[index]; for (int i = index; i < count - 1; i ++) data[i] = data[i + 1]; count --; //缩容 if (count == data.length / 2) { resize(data.length / 2); } return result; } //检查下标的方法 public void checkIndex(int index) { if(index < 0 || index > count) throw new IllegalArgumentException("Index Illegal!"); } //重新设置数组的容量, 对应的操作是扩容和缩容 private void resize(int capacity) { T[] temp = (T[]) new Object[capacity]; for (int i = 0; i < count; i++) { temp[i] = data[i]; } data = temp; } }
是不是很简单呢?后面接着讲数据结构与算法的知识!