ArrayList数据结构的分析

package com.list;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;

public class Array_List<E>
{

/**
* 存储数据的大小，大小有ArrayList的初始值决定
*/
private Object[] elementData = null;

/**
* ArrayList的大小
*/
private int size = 0;

/**
* 构造一个指定初始值大小的ArrayList
*
* @param initialCapacity
*            ArrayList的初始值
*/
public Array_List(int initialCapacity)
{
if (initialCapacity < 0)
{
// 如果参数不合法或者不正确，就会抛出IllegalArgumentException.
throw new IllegalArgumentException("Illegal capacity:"
+ initialCapacity);
}
this.elementData = new Object[initialCapacity];
}

/**
* 构造一个空的List，初始值大小为10
*/
public Array_List()
{
this(10);
}

/**
* 构造一个包含指定 collection 的元素的列表，这些元素是按照该 collection 的迭代器返回它们的顺序排列的。
*
* @param c
*            其元素将放置在此列表中的 collection
*/
public Array_List(Collection<? extends E> c)
{
// 包含此 collection 中所有元素的数组
elementData = c.toArray();
size = c.size();
if (elementData.getClass() != Object[].class)
{
// 如果elementData里面数据类型不是Object[]类型，需要通过copyOf方式转成Object[]类型
Arrays.copyOf(elementData, size, Object[].class);
}
}

/**
* 增加ArrayList容量
*
* @param minCapacity
*            新容量的大小
*/
public void ensureCapacity(int minCapacity)
{
int oldCapacity = elementData.length;
if (oldCapacity < minCapacity)
{
Object oldData[] = elementData;
// 如果ArrayList现在的大小<minCapacity;（将原来的大小*3）/2+1扩大，
// 如果扩大后的值还是＜minCapacity;那么就让最新的大小等于传入的值。并复制对象。
int newCapacity = (oldCapacity * 3) / 2 + 1;
System.out.println(newCapacity);
if (newCapacity < minCapacity)
{
newCapacity = minCapacity;
System.out.println(newCapacity);
}
elementData = Arrays.copyOf(elementData, minCapacity);
}
}

/**
* 返回ArrayList的大小
*
* @return 大小
*/
public int size()
{
return size;
}

/**
* 判断是否为null
*
* @return size==0?true:false
*/
public boolean isEmpty()
{
return size == 0 ? true : false;
}

/**
* 返回此列表中首次出现的指定元素的索引，或如果此列表不包含元素，则返回 -1
*
* @param o
*            要搜索的元素
* @return 此列表中第一次出现的指定元素的索引，如果列表不包含该元素，则返回 -1
*/
public int indexOf(Object o)
{
if (null == o)
{
for (int i = size - 1; i >= 0; i--)
{
if (elementData[i] == null)
{
return i;
}
}
}
else
{
for (int i = size - 1; i >= 0; i--)
{
if (elementData[i].equals(o))
{
return i;
}
}
}
return -1;
}

/**
* 检查数组是否下标越界
*
* @param index
*            需要检查的下标
*/
private void RangeCheck(int index)
{
if (index >= size)
throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
+ size);
}

/**
* 根据index查询某个值
*
* @param index
*            索引
* @return 索引对应的值
*/
@SuppressWarnings("unchecked")
public E get(int index)
{
RangeCheck(index);
return (E) elementData[index];
}

/**
* 用指定的元素替代此列表中指定位置上的元素。
*
* @param index
*            索引
* @param element
*            元素
* @return 以前位于该指定位置上的元素
*/
public E set(int index, E element)
{
RangeCheck(index);
E oldElement = (E) elementData[index];
elementData[index] = element;
return oldElement;
}

/**
* 添加一个Element,首先要判断ArrayList的大小是否已经用完， 重新申请新的空间，然后在size++，赋值。
*
* @param e
*            新添加的元素
* @return 添加成功
*/
public boolean add(E e)
{
ensureCapacity(size + 1);
elementData[size++] = e;
return true;
}

public void add(int index, E element)
{
if (index > size || index < 0)
throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
+ size);

ensureCapacity(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1, size
- index);
elementData[index] = element;
size++;
}

/**
* 根据索引移除数据，是先将需要移除的数据的索引计算（size - index - 1）， 然后把索引其他数据向前移动，最后把最后的一个数据清除即可。
*
* @param index
*            索引
* @return index对应的数据
*/
public E remove(int index)
{
RangeCheck(index);
E oldValue = (E) elementData[index];
int numMoved = size - index - 1;
System.out.println(numMoved);
if (numMoved > 0)
{
System.out.println(Arrays.toString(elementData));
System.arraycopy(elementData, index + 1, elementData, index,
numMoved);
System.out.println(Arrays.toString(elementData));
}
elementData[--size] = 0;
System.out.println(Arrays.toString(elementData));
return oldValue;
}

public static void main(String[] args)
{
Array_List<String> s = new Array_List<String>(5);
for (int i = 0; i < 15; i++)
{
s.add("" + (i + 1));
}
// s.remove(2);
s.add("33");
}
}