线性表实现之顺序表——MyArrayList
在上一篇博文讨论了数据结构这门课中那些让人难以理解的基础概念之后，博主打算自己实现一些常见的数据结构，毕竟学习再多书本上的知识也不如自己手动实现一次收获更大。
由于博主的主编程语言是java，所以接下来的博文中都会以Java语言来实现一些常见的数据结构。
今天的数据结构是线性表的一个常用实现顺序表——ArrayList。顺序表就是在Java语言中以数组为底层的存储容器实现的一种允许动态扩容的线性表。
我们的任务很简单就是从无到有自己构建一个MyArrayList数据结构来巩固自己的知识。这里我们先列出我们想要实现一个什么样的MyArrayList，只有先定出明确的目标，才可以根据目标来设计程序。
MyArrayList： 1. 我们的MyArrayList应该可以装各种各样的类型，因此泛型会被用到。 2. MyArrayList内部是以数组作为存储容器的。 3. MyArrayList应该拥有自动扩容的功能，这样才没有数组定长的限制。 4. 应该提供集合常见的方法如：
- get(int index) //返回指定位置元素 - set(int index, E element) //修改指定位置的元素 - add(E element) //在列表末尾增加元素 - add(int index, E element) //在指定位置添加元素 - remove(int index) //删除指定位置的元素 - remove(E element) //从列表中删除指定的元素 - contains(E element) //检查列表中是否存在指定元素 - size() //返回列表中元素的个数 - clear() //清空列表中所有的元素 - isEmpty() //检查列表是否为空 - 等等……既然理清了思路我们就来一步步地构建自己的MyArrayList吧
首先我们来写这个数据结构的私有成员，一个能装泛型E的数组，size表示列表中元素的数目，以及一个默认的初识数组大小
public class MyArrayList<E>{ //在声明MyArrayList时，如不指明大小，则初始大小为10 PRivate static final int DEFAULT_CAPACITY = 10; private E[] contents; private int size = 0; //两种构造函数，允许用户创建指定大小或者默认大小的线性表 public MyArrayList(){ init(DEFAULT_CAPACITY); } public MyArrayList(int initCapacity){ init(initCapacity); } //私有化方法init帮助构造函数来初始化数组contents private void init(int capacity){ //注意不能建立泛型数组，因此我们强行转换一个Object数组 contents = (E[]) new Object[capacity]; }接下来我们提供几个简单的获取元素数量、查看是否为空的方法
public int size(){ return this.size; } public boolean isEmpty(){ return size()==0; } public void clear(){ for(int i=0;i<size();i++){ //将数组中元素的引用指向null，这样GC就可以回收内存 contents[i] = null; } this.size = 0; }接着我们提供两种不同情形下的插入方法
public boolean add(E element){ if(size()>=contents.length){ //一旦列表中的元素个数等于了数组的长度，我们就对数组进行扩容 ensureCapacity(); } //将元素放置最后位置并把元素数目加1 contents[size++] = element; return true; } public void add(int index, E element){ //一旦要插入元素的位置为负或大于目前的元素数量就抛出异常 //此处允许index等于size，相当于在列表末尾插入元素 if(index<0 || index>size()) throw new IndexOutOfBoundsException(); if(size()>=contents.length) ensureCapacity(); //将数组中前一个元素的值赋予后一个元素 for(int i=size();i>index;i--) contents[i] = contents[i-1]; //将要插入的元素放到index位置上 contents[index] = element; this.size++; } private void ensureCapacity(){ //此处新数组的容量是旧数组的2倍加1，你可以自己选择扩容的多少 E[] newContents = (E[]) new Object[2*contents.length+1]; //将就数组中的值全部拷于新数组中 System.arraycopy(contents,0,newContents,0,size()); //在让contents指向新的数组 contents = newContents; }下一个提供的是两种不同的删除方法
public boolean remove(E element){ if(element == null){ for(int i=0;i<size();i++){ if(contents[i] == null){ //如果找到元素为null，就使用私有方法fastRemove将该位置元素删除 fastRemove(i); return true; } } return false; }else{ for(int i=0;i<size();i++){ if(element.equals(contents)){ //如果找到元素为element，就使用私有方法fastRemove将该位置元素删除 fastRemove(i); return true; } } return false; } } public void remove(int index){ //一旦要插入元素的位置为负或大于目前的元素数量就抛出异常 //此处不允许index等于size if(index<0 || index>=size()) throw new IndexOutOfBoundsException(); fastRemove(index); } //私有化方法实现无须检查边界就直接删除某一位置的元素 private void fastRemove(int index){ //需要从后向前移动的元素数目 int numMoved = size() - index -1; if(numMoved > 0){ //将数组i+1位置开始的numMoved个元素移动到数组i的位置 //相当于将i位置上的元素删除，并将后面的元素向前移一位 System.arraycopy(contents,index+1,contents,index,numMoved); } //将元素数目减一并释放原来最后一位的内存 contents[--size] = null; }实现完了添加、删除方法之后，我们最后实现获取、修改与查看是否存在三个简单的方法
public E get(int index){ //一旦要获取元素的位置为负或大于目前的元素数量就抛出异常 //此处不允许index等于size if(index<0 || index>=size()) throw new IndexOutOfBoundsException(); return contents[index]; } public void set(int index, E element){ //一旦要获取元素的位置为负或大于目前的元素数量就抛出异常 //此处不允许index等于size if(index<0 || index>=size()) throw new IndexOutOfBoundsException(); contents[index] = element; } public boolean contains(E element){ if(element == null){ for(int i=0;i<size();i++){ if(contents[i] == null) return true; } return false; }else{ for(int i=0;i<size();i++){ if(element.equals(contents[i])) return true; } return false; } }在完成了自己写的一个MyArrayList之后，我们分析一下这种数据结构的特点。很明显,对于基于数组实现的线性表来说
我们要读取或修改某一个位置的元素只花费常数时间 O(1)； 我们要增加或删除某一个元素最坏情况下要花费线性时间 O(n)
因此，当我们在遇到频繁访问列表中元素时，ArrayList是一个很好的选择；但当我们需要频繁添加、删除列表中元素，尤其是在表的前端进行增删操作时，ArrayList就不是一个特别好的选择了。
到这里我们自己实现的MyArrayList就完成了，是不是感觉自己写数据结构也没有那么难呢？但是我们这里完成的这个只是一个很简单的数据结构，也没有实现Itrable等接口。
要想真正提高巩固自己的Java水平，我们需要在自己写完之后去对比源码中ArrayList的实现。看看尽管功能都是实现的差不多，为什么大牛写的代码就很优雅、效率高。不断地比较、吸收、学习，我们才能进步下去。
本博文源码下载地址，欢迎下载测试。