数据结构之数组

写在前面

看下数组。

1：巴拉巴拉

数组是一种线性数据结构，使用连续的内存空间来存储数据，存储的数据要求有相同的数据类型，并且每个元素占用的内存空间相同。获取元素速度非常快，为O(1)常量时间复杂度，所以数组在我们工作直接或者是间接的用到还是比较多的。

2：代码

定义接口：

package com.dahuyou.datastructure.arraylist;public interface List<E> {/*** Appends the specified element to the end of this list (optional* operation).* <p>* 追加元素到尾部！*/boolean add(E e);/*** Removes the element at the specified position in this list (optional* operation).  Shifts any subsequent elements to the left (subtracts one* from their indices).  Returns the element that was removed from the* list.** 删除指定位置的元素**/E remove(int index);/*** Returns the element at the specified position in this list.** 返回指定位置的元素*/E get(int index);}

实现类，这里不贴所有代码了，只看下重要的方法。

• add

@Override
public boolean add(E e) {// 确保内部容量int minCapacity = size + 1;if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}// 判断扩容操作，即将满时扩容，扩容为原来的1.5倍，直接通过oldCapacity + (oldCapacity >> 1)移位操作完成，效率高if (minCapacity - elementData.length > 0) {int oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1);if (newCapacity - minCapacity < 0) {newCapacity = minCapacity;}elementData = Arrays.copyOf(elementData, newCapacity);}// 添加元素elementData[size++] = e;return true;
}

这里在两种情况下会进行扩容，第一次插入元素时扩容到10，之后元素满时扩容到原来的1.5倍，这里使用了移位运算，效率更高。

• remove

@Override
public E remove(int index) {E oldValue = (E) elementData[index];int numMoved = size - index - 1;if (numMoved > 0) {// 从原始数组的某个位置，拷贝到目标对象的某个位置开始后n个元素System.arraycopy(elementData, index + 1, elementData, index, numMoved);}elementData[--size] = null; // clear to let GC do its workreturn oldValue;
}

注意这里删除元素并不是通过一个一个的交换元素来实现的，而是直接通过native方法java.lang.System#arraycopy：

public static native void arraycopy(Object src,  int  srcPos,Object dest, int destPos,int length);

因为是底层直接操作内存，所以效率更高。
测试：

package com.dahuyou.datastructure.arraylist;public class TT {public static void main(String[] args) {List<String> list = new ArrayList<>();list.add("01");list.add("02");list.add("03");list.add("04");list.add("05");list.add("06");list.add("07");list.add("08");list.add("09");list.add("10");list.add("11");list.add("12");System.out.println(list);list.remove(9);System.out.println(list);}}

运行：

ArrayList{elementData=[01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 11, 12, null, null, null], size=12}
ArrayList{elementData=[01, 02, 03, 04, 05, 06, 07, 08, 09, 11, 12, null, null, null, null], size=11}Process finished with exit code 0

写在后面

参考文章列表