【数据结构与算法】【04】数据结构之数组

数组

数组，英文名Array

是一种最简单的数据结构，即用一段连续的内存，存储若干个相同类型的对象

这种结构只需要根据对象数量，直接在内存中分配连续的空间就行了，是所有语言都默认支持的基本类型

数组特点

• 内存连续分配，按下标就能直接找到对象地址，所以访问和修改速度非常快，相当于直接根据内存地址查数值
• 由于是连续内存，所以只能一次性分配，不可能后面再修改数组长度
• 由于数组长度不可改变，因此添加和删除只能变通进行，不方便且效率低

动态数组

虽然数组长度不可变，但我们可以新建一个数组，再将旧数组的数据拷贝过去

这样就间接达到了改变数组长度的效果，这种技术就叫做动态数组

动态数组并不是一种数据结构，而是一种数组扩容方案

数组操作实现代码

	@SuppressWarnings("all")
	public class Array {
	
	    Object[] elementData;
	
	    int size;
	
	    //创建初始数组
	    //给数组一个初始长度，这样就可以避免频繁创建新数组
	    //但实际数据数量仍然通过size记录，而不是elementData
	    public Array(int initialLength) {
	        elementData = new Object[initialLength];
	        size = 0;
	    }
	
	    //增加元素
	    public void add(T element) {
	        //数组已满，扩容一倍
	        if (elementData.length == size)
	            elementData = Arrays.copyOf(elementData, size * 2);
	        elementData[size++] = element;
	    }
	
	    //删除元素
	    public void remove(T element) {
	        int index = indexOf(element);
	        if (index  0)
	            System.arraycopy(elementData, index + 1, elementData, index, numMoved);
	        elementData[--size] = null;
	    }
	
	    //修改元素
	    public void set(int index, Object element) {
	        elementData[index] = element;
	    }
	
	    //查找元素
	    public T get(int index) {
	        return (T) elementData[index];
	    }
	
	    //查找元素位置
	    public int indexOf(T element) {
	        for (int index = 0; index