什么是数组
- 数组是有序的元素序列，若将有限个类型相同的变量的集合命名，那么这个名称为数组名。
- 组成数组的各个变量称为数组的分量，也称为数组的元素，有时也称为下标变量。
- 用于区分数组的各个元素的数字编号称为下标。
- 数组是在程序设计中，为了处理方便， 把具有相同类型的若干元素按有序的形式组织起来的一种形式。这些有序排列的同类数据元素的集合称为数组。
数组的特点
- 数组是相同数据类型的元素的集合。
- 数组中的各元素的存储是有先后顺序的，它们在内存中按照这个先后顺序连续存放在一起。
- 数组元素用整个数组的名字和它自己在数组中的顺序位置来表示。例如，a[0]表示名字为a的数组中的第一个元素，a[1]代表数组a的第二个元素，以此类推。
表现形式
- 一维数组
int[] a; String[] strs; - 二维数组
int[][] a; String[][] strs;
随机访问
数组是由一块连续的内存空间和相同类型的数据构成的，所有他有个非常重要的特性：随机访问，它可以不需要通过遍历而直接取出某个下标中的元素。
而也正是由于需要保证数组的连续性，当进行插入和删除操作时，就必须做大量的迁移工作。
一维数组寻址公式： i_loc = init_loc + i * size
size为元素的数据长度 如int类型为4个字节
example: init_loc = 100000
| 元素 | 内存地址 | 寻址公式 |
| a[0] | 100000 | 100000 + 0*4 |
| a[1] | 100004 | 100000 + 1*4 |
| a[2] | 100008 | 100000 + 2*4 |
这也是为什么数组都是以0为下标开始的原因
手写一个ArrayList
java
//定义接口 public interface MyList<E> extends Iterable<E> { int size(); void add(E e); void add(E e,int index); void remove(int index); void remove(E e); E get(int index); Iterator<E> iterator(); int indexOf(E e); } public class MyArrayList<E> implements MyList<E> { private Object[] data; private int size; private static final int DEFAULT_CAPACITY = 10; public MyArrayList() { this(DEFAULT_CAPACITY); } public MyArrayList(int initialCapacity) { if (initialCapacity == 0) { data = new Object[DEFAULT_CAPACITY]; } else { data = new Object[initialCapacity]; } } @Override public void add(E element) { ensureAdd(); //判断是否即将越界，扩容 data[size++] = element; } @Override public void add(E element, int index) { //6 3 size = 5 ensureAdd(); // 1 2 3 4 5 -> 1 2 3 6 4 5 int srcPost = index; int destPost = index + 1; int length = size - index; System.arraycopy(data, srcPost, data, destPost, length); data[index] = element; size++; } private void ensureAdd(){ if (size + 1 > data.length) { int newCapacity = data.length * 2; data = Arrays.copyOf(data, newCapacity); } } @SuppressWarnings("unchecked") @Override public E get(int index) { return (E) data[index]; } @Override public Iterator<E> iterator() { return new Iterator<E>() { int cursor; // index of next element to return @Override public boolean hasNext() { return cursor != size; } @SuppressWarnings("unchecked") @Override public E next() { if (cursor >= size) throw new NoSuchElementException(); Object[] elementData = MyArrayList.this.data; if (cursor >= elementData.length) throw new ConcurrentModificationException(); return (E) elementData[cursor++]; } }; } @Override public void remove(int index) { // index = 2 size = 5 //1 2 3 4 5 -> 1 2 4 5 int srcPost = index + 1; int destPost = index; int length = size - index - 1; //2 System.arraycopy(data, srcPost, data, destPost, length); data[--size] = null; } @Override public void remove(E element) { // 3 size=5 //1 2 3 4 5 -> //1 2 4 5 for (int i = 0; i < size; i++) { if (element == data[i]) { remove(i); } } } @Override public int indexOf(E element) { for (int i = 0; i < size; i++) { if (element == data[i]) return i; } return -1; } @Override public int size() { return size; }
