数组和链表是非常基本的数据结构，而数据结构就像我们常用的数据库一样，只不过我们将数据存在了运行程序的内存中，不同的数据结构就像是不同的数据库，每一个都有自己的特点，需要进行深入的了解。像我们常用的ArrayList，LinkedList就是对数组和链表的一个很好的实现。
数组简介 在计算机科学中，数组数据结构，简称数组，是由相同类型的元素的集合所组成的数据结构，分配一块连续的内存来进行存储。利用元素的索引可以计算出改元素对应的存储地址。 - 来自维基百科
众所周知，数组的特点就是最大的优点是查询速度快。这是因为在知道改元素的索引下，可以直接根据arr[index] 获取到该值，时间复杂度为O(1)。缺点是数组容量固定死的。那么什么场景下应该使用数组呢？数组最好应用在索引有语意的情况下。比如score[6] = 100，表示学号为6的学生分数是100分。
容量和大小 什么是数组容量，什么是数组的大小。做一个比喻，家用冰箱一般是8层，每一层都是隔开来的。现在冰箱里面6层放了食材。那么8就代表数组的容量，也就是capacity，6层放了食材代表数组的大小，也就是size。在Java中数组只有一个公开的域，也就是length。代表数组的容量。
链表简介 链表是一种常见的基本数据结构，是一种线性表，但是不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针。 - 来自维基百科
链表是真正的动态数据结构，也是最简单的动态数据结构。优点是真正的动态，不需要处理固定容量的大小。缺点是失去了随机访问的能力。
动态数组 在Java中我们可以对一个数组进行扩容，让一个数组达到一个动态的效果。其中java.util中的ArrayList就是对一个数组的动态实现。现在我通过代码实现以下动态数组。原理和ArrayList差不多。
代码如下：
/** * @ClassName Array * @Description 自己封装的一个动态数组 * @Author ouyangkang * @Date 2019-01-21 09:24 **/ public class Array<E> { //数组 private E[] data; //数组大小 private int size; // 容量 可以不用，为什么？ 因为 他的大小就是data.length; // private int capacity; // 构造函数，传入数组容量capacity构造函数Array public Array(int capacity) { data = (E[]) new Object[capacity]; size = 0; } // 默认参数 容量等于10 public Array() { this(10); } // 获取数组大小 public int getSize() { return size; } // 获取数据容量 public int getCapacity() { return data.length; } // 数组大是否为空 public boolean isEmpty() { return getSize() == 0; } // 添加一个元素 扩容 public void addLast(E e) { add(size, e); } public void addFirst(E e) { add(0, e); } // 在第index插入e public void add(int index, E e) { if (index < 0 || index > size) { throw new IllegalArgumentException("addLast failed : index < 0 or index > size"); } if (size == getCapacity()) { resize(2 * data.length); } // 数组插入前的元素，后移 for (int i = size - 1; i >= index; i--) { data[i + 1] = data[i]; } data[index] = e; size++; } // 获取index位置上的元素 public E get(int index) { if (index < 0 || index > size) { throw new IllegalArgumentException("Get failed . Index is illegal"); } return data[index]; } // 更新index位置上的元素 public void set(int index, E e) { if (index < 0 || index > size) { throw new IllegalArgumentException("Set failed . Index is illegal"); } data[index] = e; } // 是否包含某个元素e public boolean contains(E e) { for (int i = 0; i < size; i++) { if (data[i] == e){ return true; } } return false; } // 查找改元素的位置 public int find(E e) { for (int i = 0; i < size; i++) { if (data[i] == e) { return i; } } return -1; } //移除指定index位置上的元素 public E remove(int index) { if (index < 0 || index > size) throw new IllegalArgumentException("remove failed . Index is illegal"); E ret = data[index]; for (int i = index + 1; i < size; i++) { data[i - 1] = data[i]; } size--; data[size] = null; //缩容操作 if (size == data.length / 4 && data.length / 2 != 0) { resize(data.length / 2); } return ret; } // 移除第一个 public E removeFirst() { return remove(0); } //移除最后一个 public E removeLast() { return remove(size - 1); } // 移除某一个元素 有就删除 没有就不删除 public void removeElement(E e) { int i = find(e); if (i != -1) { remove(i); } } // 删除所有元素 public void removeAllElement(E e) { boolean flag = true; while (flag) { int i = find(e); if (i != -1) { remove(i); } else { flag = false; } } } // 扩容操作 想要扩容大小 private void resize(int newCapacity) { E[] newData = (E[]) new Object[newCapacity]; for (int i = 0; i < size; i++) { //全部赋值给新的数组 newData[i] = data[i]; } data = newData; } public E getLast() { return get(size - 1); } public E getFirst() { return get(0); } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append(String.format("Array: size = %d, capacity=%d \n", size, data.length)); res.append('['); for (int i = 0; i < size; i++) { res.append(data[i]); if (i != size - 1) { res.append(", "); } } res.append(']'); return res.toString(); } }有兴趣的可以仔细看一下，写个main方法测试一下。
链表实现