数据结构与算法系列2 线性表 使用java实现动态数组+ArrayList源码详解
对数组有不了解的可以先看看我的另一篇文章，那篇文章对数组有很多详细的解析，而本篇文章则着重讲动态数组，另一篇文章链接如下，可点击跳转：
链接：https://blog.csdn.net/pjh88/article/details/107166950
什么是数组与动态数组？
数组
数组是相同数据类型的元素按照一定的顺序排列的集合，若将有限个类型相同的变量的集合命名，那么这个名称称为数组名，组成数组的各个变量称为数组的分量，也称为数组的元素，有时爷称为下标变量，用于区分数组的各个元素的数组编号称为下标。数是程序设计中，为了处理方便把具有相同类型的若干变量按有序的形式组织起来的一种形式，这些按序排序的同类元素的集合称为数组
动态数组
顾名思义，动态数组即可以动态扩容的数组，一般的数组是不能扩容的，及在创建数组对象的时候就规定了数组的大小，规定数组是多大就是多大，后期不可以存储多余的元素
动态数组的好处也显而易见：
1.动态的增加和减少元素
2.实现collection和list接口
3.灵活设置数组的大小
java中已经给我们封装好了一个动态数组Arraylist的类，我们可以直接使用，其内部有许多方法，我们先来看看有什么方法，下面仅仅讲我们经常使用到的方法那些不怎么使用的我们在这就不讲了：
int size（）；元素的数量
boolean isEmpty（）；是否为空
boolean contains（E element); 判断是否包含某个元素
void add（E element） ；添加元素到最后
E get（int index）；返回index对应位置的元素
E set（int index，E element）；往index位置添加元素
void add（int index，E element）；往index位置添加元素
E remove（int index）； 删除index位置对应的元素
int indexOf（E element）； 查看元素的位置
void clear（）；清除所有元素
接下来我们逐一讲解这些方法
定义的变量
//元素的数量
private int size;
//存储元素
private E[] elements;
//初始化大小
private static final int DEFAULT_CAPACITY=16;
//元素没有找到时的放回值
private static final int ELEMENT_NOT_FOUND=-1;
构造方法
//自定义大小
public ArrayList(int capacity){
//如果传入的大小小于默认数组的大小，则使用默认的大下
capacity= (capacity<DEFAULT_CAPACITY)?DEFAULT_CAPACITY:capacity;
elements=(E[])new Object[capacity];
}
//默认大小的构造方法
public ArrayList(){
this(DEFAULT_CAPACITY);
}
判断index的范围有没有越界
public void rangeCheak(int index){
if (index<0||index>size){
outofBounds(index);
}
}
获取指定位置的元素
public E get(int index){
rangeCheak(index);
return elements[index];
}
重新设定指定位置的元素
public E set(int index,E element){
//检查插入位置是否合法
rangeCheak(index);
//返回原来的元素
E oldelement1 = elements[index];
//插入新的元素
elements[index]=element;
return oldelement1;
}
判断是否为空
public boolean isEmpty(){
return size==0;
}
返回元素的数量
public int size(){
return size;
}
判断是否包含某个指定元素
public boolean contains(E element){
return indexOf(element)!=ELEMENT_NOT_FOUND;
}
返回指定元素的位置
public int indexOf(E element){
if (element==null){
for (int i = 0; i < size; i++) {
if (elements[i]==null){
return i;
}
}
}else{
for (int i = 0; i < size; i++) {
if (element.equals(elements[i])){
return i;
}
}
}
return ELEMENT_NOT_FOUND;
}
在末尾插入元素
public void add(E element){
add(size,element);}
在指定位置插入元素
public void add(int index,E element){
//检查范围
rangeCheakForadd(index);
//判断容量是否足够
ensureCapacity(size+1);
for (int i = size; i > index; i--) {
elements[i]=elements[i-1];
}
elements[index]=element;
size++;
}
检查插入范围
public void rangeCheakForadd(int index){
if (index<0||index>size){
outofBounds(index);
}
}
移除指定位置的元素
public E remove(int index){
//检查范围
rangeCheak(index);
E removeElement = elements[index];
for (int i=index+1;i<size;i++) {
elements[i-1]=elements[i];
}
elements[--size]=null;
return removeElement;
}
清除所有元素
public void clear(){
for (int i = 0; i < size; i++) {
elements[i]=null;
}
}
其实动态数组最重要的一个方法就是扩容，下面来重点讲解
public void ensureCapacity(int capacity){
int oldcapacity = elements.length;
//如果比原来小则不做改变
if (oldcapacity>= capacity){
return;
}
//使用位运算，速度更快
//我这里用的是二倍扩容，这里的扩容大小可以自己来设置，以达到最高的使用率
int newCapacity=oldcapacity+(oldcapacity>>1);
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i]=elements[i];
}
//将elements的地址赋值新的地址
elements=newElements;
System.out.println(oldcapacity+"扩容为："+newCapacity);
}
复写toString（)方法
@Override
public String toString(){
//使用StringBuilder
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append('[');
for (int i = 0; i < size; i++) {
if (i!=0){
stringBuilder.append(",");
}
stringBuilder.append(elements[i]);
}
stringBuilder.append(']');
return stringBuilder.toString();
}