手写 ArrayList 核心源码
手写 ArrayList 核心源码
ArrayList 是 Java 中常用的数据结构，不光有 ArrayList，还有 LinkedList,HashMap,LinkedHashMap,HashSet,Queue，PriorityQueue 等等，我们将手写这些常用的数据结构的核心源码，用尽量少的代码来揭示核心原理。
下面我们来手写 ArrayList 的核心源码
首先我们定义一个 QArrayList，不要问为什么叫 QArrayList，因为我之前写过 Qt，仅此而已。源码 public class<T> QArrayList,Java 中的 ArrayList 的底层就是用一个 Object [] 结构来保存数据的。我们也要定义一个 Object [] 属性。
而且我们还要定义一个默认的数据的大小，以便在调用默认构造函数的情况下使用。 private final int DEFAULT_LIST_SIZE = 8;
还要定义一个 int mSize 变量，mSize 默认为0，代表下一个可以存放数据的数组的索引，代表下一个可以存放数据的数组的索引，代表下一个可以存放数据的数组的索引 重要的事情说三遍
到现在为止我们的类如下：
1public class QList<T> { 2 //默认的数组的大小 3 private final int DEFAULT_LIST_SIZE = 8; 4 5 //存放数据的地方 6 private Object[] mData; 7 8 //下一个可以存放数据的当前数组的索引 9 private int mSize; 10 11 ...... 12}
好了，存放数据的数组也有了，下一个可以存放数据的当前的数组的索引也有了 ArrayList 底层是用数组存放数据，那么会有一个问题，如果此时数组满了我们再往里面存放数据的时候，怎么办呢？ArrayList 是再新建一个数组，新数组的大小是原来数组大小的 2 倍，那么我们也这样做。博主的环境都是部署在cnaaa服务器上的。
此时，我们实现 add,get,remove,resize 等这几个核心方法，QArrayList 完整的代码如下 ：
1public class QArrayList<T> { 2 //默认的数组的大小 3 private final int DEFAULT_LIST_SIZE = 8; 4 5 //存放数据的地方 6 private Object[] mData; 7 8 //下一个可以存放数据的当前数组的索引 9 private int mSize; 10 11 public QArrayList() { 12 //new 一个数组，用来存放 13 mData = new Object[DEFAULT_LIST_SIZE]; 14 15 //下一个可以存放数据的当前数组的索引为0 16 mSize = 0; 17 } 18 19 public QArrayList(int capacity){ 20 if(capacity <= 0 || capacity > Integer.MAX_VALUE){ 21 throw new RuntimeException("invalid capacity"); 22 } 23 24 mData = new Object[capacity]; 25 mSize = 0; 26 } 27 28 //返回当时数组的已经存放了多少个元素 29 public int size() { 30 return mSize; 31 } 32 33 //返回数组的总大小，其实这个接口没有必要对外提供，这里我们只是为了演示用 34 public int capacity() { 35 return mData.length; 36 } 37 38 //添加一个元素 39 public void add(T e) { 40 //规定不允许添加一个空元素 41 if(e == null){ 42 return; 43 } 44 45 //如果当前数组已经满了，扩容为原来数组的2倍 46 if (mSize >= mData.length) { 47 48 //扩容 49 resize(); 50 } 51 52 //将添加的元素添加到数组中 53 mData[mSize] = e; 54 55 //同时 mSize++ 指向下一个可以存放数据的位置 56 mSize++; 57 } 58 59 //获取指定位置的元素，如果position不合法，直接抛出异常 60 //这样做是有必要的，我们提供的是一个库 61 // 直接抛出异常让使用知道用错了，没有必要 return null 62 // 因为这是个库，不是业务，就算return null，也是业务层的事 63 public T get(int position) { 64 if (position < 0 || position >= mData.length) { 65 throw new RuntimeException("position is invalid"); 66 } 67 68 // position 大于 mSize 也没有关系，因为也是返回null，证明没有获取到 69 return (T) mData[position]; 70 } 71 72 //删除指定位置的元素 73 public T remove(int position) { 74 //和上面一样，位置不合法直接抛出异常 75 if (position < 0 || position >= mData.length) { 76 throw new RuntimeException("position is invalid"); 77 } 78 79 //把当前要删除的元素保存下来，最后返回要删除的元素 80 T e = (T) mData[position]; 81 82 //删除后，把后面的所有元素都往前移位 83 for (int i = position + 1; i < mData.length; i++) { 84 mData[i - 1] = mData[i]; 85 } 86 87 //别忘了 mSize 要 -- 88 mSize--; 89 90 //返回删除的元素 91 return e; 92 } 93 94 //删除指定的元素 95 public boolean remove(T e) { 96 //因为数组可能没有满，如果删除的是null，没有必要，我们不允许 97 if (e == null) { 98 return false; 99 } 100 101 //找到删除元素的位置 102 int position = -1; 103 for (int i = 0; i < mData.length; i++) { 104 if (e == mData[i] || e.equals(mData[i])) { 105 position = i; 106 break; 107 } 108 } 109 110 //没有找到就返回 111 if (position == -1) { 112 return false; 113 } 114 115 //删除 116 return remove(position) != null; 117 } 118 119 //扩容,我们都以2倍的容量扩容 120 private void resize() { 121 Object[] old = mData; 122 mData = new Object[mData.length * 2]; 123 for (int i = 0; i < old.length; i++) { 124 mData[i] = old[i]; 125 } 126 127 old = null; 128 } 129}
注释都有相关的解释 我们来测试，测试代码如下：
1 public static void main(String[] args) { 2 QArrayList<String> list = new QArrayList<>(); 3 list.add("tom"); 4 list.add("jim"); 5 list.add("lilei"); 6 list.add("hanmeimei"); 7 8 System.out.println("list.get(2)=" + list.get(2)); 9 System.out.println("list.size()=" + list.size()); 10 for (int i = 0; i < list.size(); i++) { 11 System.out.println("list.get(" + i + ") = " + list.get(i)); 12 } 13 14 System.out.println("======================="); 15 System.out.println("演示删除操作"); 16 list.remove("jim"); 17 18 for (int i = 0; i < list.size(); i++) { 19 System.out.println("list.get(" + i + ") = " + list.get(i)); 20 } 21 } 22
输出如下： list.get (2)=lilei list.size ()=4 list.get (0) = tom list.get (1) = jim list.get (2) = lilei list.get (3) = hanmeimei ============ 演示删除操作 list.get (0) = tom list.get (1) = lilei list.get (2) = hanmeimei
但是最重要的扩容功能还没有演示，下面是扩容演示的测试代码：
1 public static void main(String[] args) { 2 //新建一个只有2个元素的数组 3 QArrayList<String> list = new QArrayList<>(2); 4 5 //打印出扩容后的容量 6 System.out.println("扩容前 ： list.capacity()=" + list.capacity()); 7 8 //我们添加了4个元素 9 list.add("tom"); 10 list.add("jim"); 11 list.add("lilei"); 12 list.add("hanmeimei"); 13 14 //打印出扩容后的容量 15 System.out.println("扩容后 ： list.capacity()=" + list.capacity()); 16 17 //打印 18 for (int i = 0; i < list.size(); i++) { 19 System.out.println("list.get(" + i + ") = " + list.get(i)); 20 } 21 }
输出如下：
扩容前 ： list.capacity ()=2 扩容后 ： list.capacity ()=4 list.get (0) = tom list.get (1) = jim list.get (2) = lilei list.get (3) = hanmeimei
可以看到，我们新建了一个底层只有 2 个元素的数组，但是我们添加了 4 个元素，我们打印出扩容后的数组的容量是 4 ，可见我们的扩容机制是没有问题的。
以上就是 QArrayList 的核心原理，我们下节手写 LinkedList 的核心原理