什么是数据结构？
数据结构研究的是数据如何在计算机中进行组织和存储，使得我们可以高效的获取数据或者修改数据。
数组封装
定义一个class Array，里面维护数组data，以及数组的长度，使得我们可以对数组增加相应的方法进行操作。
public class Array<E> {
// 维护的内部数组，实际存储数据的地方
private E[] data;
// 当前数据长度
private int size;
// capacity是数组的容量
public Array(int capacity) {
this.data = (E[]) new Object[capacity];
size = 0;
}
}
再增加一些公用的方法
public int getSize() {
return size;
}
public int getCapacity() {
return data.length;
}
public boolean isEmpty() {
return size == 0;
}
操作
通常来讲，数据结构就是封装用来对数据进行存储和查询的，对应的一般有如下操作
增
public void addFirst(E e) {
add(0, e);
}
public void addLast(E e) {
add(size, e);
}
public void add(int index, E e) {
if (size == data.length) {
throw new IllegalStateException("Add failed! Array is full");
}
if (index < 0 || index > size) {
throw new IllegalStateException("Add failed! Require index >=0 && index <= size");
}
for (int i = size; i > index; i--) {
data[i] = data[i - 1];
}
data[index] = e;
size++;
}
删
public E removeFirst() {
return remove(0);
}
public E removeLast() {
return remove(size - 1);
}
public void removeElement(E e) {
int index = find(e);
if (index != -1) {
remove(index);
}
}
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalStateException("Add failed! Require index >=0 && index < size");
}
E removed = data[index];
for (int i = index; i < size - 1; i++) {
data[i] = data[i + 1];
}
size--;
return removed;
}
改
public void set(int index, E e) {
if (index < 0 || index >= size) {
throw new IllegalStateException("Set failed! Require index >=0 && index < size");
}
data[index] = e;
}
查
public int find(E e) {
for (int i = 0; i < data.length; i++) {
if (data[i].equals(e)) {
return i;
}
}
return -1;
}
public boolean contains(E e) {
return find(e) != -1;
}
public E get(int index) {
if (index < 0 || index >= size) {
throw new IllegalStateException("Add failed! Require index >=0 && index < size");
}
return data[index];
}
动态数组
在上面的数组实现中，每当数组个数达到capacity时，就不能往数组中添加元素了。为了能够继续向数组中添加元素，需要在数组满时对数组进行扩容，修改add方法如下：
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalStateException("Add failed! Require index >=0 && index <= size");
}
if (size == data.length) {
// 数组满时，扩容2倍
resize(data.length * 2);
}
for (int i = size; i > index; i--) {
data[i] = data[i - 1];
}
data[index] = e;
size++;
}
对应的resize方法实现如下：
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}
相应的，当remove到数组的一半时，也可以进行缩容操作：
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalStateException("Add failed! Require index >=0 && index < size");
}
E removed = data[index];
for (int i = index; i < size - 1; i++) {
data[i] = data[i + 1];
}
size--;
if (size == data.length / 2) {
resize(size);
}
return removed;
}
算法复杂度分析
对于增加元素操作来讲：
addFirst > O(n)
addLast > O(1)
add > O(n)
由于resize的复杂度也为O(n)，因此按最坏情况算，增加元素的复杂度为O(n)
对于删除元素来讲同理
对于修改元素来讲：O(1)
对于查询元素：
get(index) > O(1)
contains > O(n)
find > O(n)
均摊复杂度
对于addLast来讲，如果数组容量足够的情况下，算法复杂度为O(1)，在数组容量不够的情况下为O(n)。平均来看，假设数组容量为n，需要增加n+1个元素才会扩容，扩容操作为n次，因此对于n+1次添加来说，总共会执行2n+1次操作，平均每次为2次操作。这样一种均摊形式的复杂度可以看成是O(1)级别的。
防止复杂度震荡
如果在整个数组满了的时候，不断的执行addLast和removeLast操作，就会导致不断的扩容和缩容操作，此时每次操作的复杂度都为O(n)，从而导致复杂度震荡。
为了减少复杂度震荡，需要改变缩容的策略。每次不及时的缩容，而是在之后再进行缩容。这是一种从Eager到Lazy策略的转换。我们在数组容量只剩1/4的时候进行缩容，每次缩容1/2。对应remove修改为：
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalStateException("Add failed! Require index >=0 && index < size");
}
E removed = data[index];
for (int i = index; i < size - 1; i++) {
data[i] = data[i + 1];
}
size--;
if (size == data.length / 4 && data.length / 2 != 0) {
resize(data.length);
}
return removed;
}
