ArrayList的实现方式

 

      这里我想说说我对这个数据结构的理解。之前一直被theSize,size(),theItems.length几个点搞混。现在有点小明白。在java环境下，新建立数组并用int[] a = new int[10]。这样初始化的时候，数组的长度a.length=10。但是全部都是为null。而在上面的线性表中的size，返回的是a数组包含元素的个数，与a.length没有关系。

调试的情况如附件所示：theSize是线性表这个对象的一个属性。表示的是这个对象中的itemElement的个数。而theItem.length则是itemElem的长度，里面的值都是为null。

 

还有增加和删除。

增加为什么是

 

	public void add(int idx, AnyType x) {
		int objectSize = theItems.length;
		if (theItems.length == size())
			ensureCapacity(size() * 2 + 1);
		for (int i = theSize; i > idx; i--)
			theItems[i] = theItems[i - 1];

		theItems[idx] = x;
		theSize++;
	}

 而不是theItems[i+1]=theItems[i]？在当前条件下(i>index)。如果改为这种。那么，比如有theItems[]={0,1,2,3,4,5,6,null,null}、然后在add(4,100)。则执行的时候会是 theItems[8]=theItem[7]。虽然theItems.length=10。数组没有越界。但是却是在null之后插入。而使用上面的情况下则是theItem[7]=theItem[6]。刚好是最后一个元素的下一个空间。

 

删除也同样如此。而且要注意，i<size-1。而不是i<size。如果小于size的话。也会出问题。

 

归根到底，主要是size表示的是元素个数。而i或者index表示的是索引。而数组索引是从0开始的。就像a[0]的index=0而size=1一样。

 

 

 

 

 

 

 

import java.util.Iterator;
import java.util.NoSuchElementException;

public class MyArrayList<T> implements Iterable<T> {

	// 默认大小
	private static final int DEFAULT_CAPACITY = 10;
	// 长度
	private int theSize;
	// 数据
	private T[] theItems;

	// 构造函数
	public MyArrayList() {
		this(DEFAULT_CAPACITY);
	}

	// 构造函数
	@SuppressWarnings("unchecked")
	public MyArrayList(int size) {
		theItems = (T[]) new Object[size];
	}

	// 清除
	public void clear() {
		theSize = 0;
		ensureCapacity(DEFAULT_CAPACITY);
	}

	// 大小
	public int size() {
		return theSize;
	}

	// 是否为空
	public boolean isEmpty() {
		return size() == 0;
	}

	// 扩展数组大小
	public void trimToSize() {
		ensureCapacity(size());
	}

	// 查找
	public T get(int index) {
		if (index < 0 || index >= size())
			throw new ArrayIndexOutOfBoundsException();
		return theItems[index];
	}

	// 修改
	public T set(int index, T newVal) {
		if (index < 0 || index >= size())
			throw new ArrayIndexOutOfBoundsException();
		T old = theItems[index];
		theItems[index] = newVal;
		return old;
	}

	// 增加
	public void add(int index, T t) {
		// 如果数组的长度等于存储元素的长度，则扩展数组长度
		if (theItems.length == size())
			ensureCapacity(size() * 2 + 1);
		// 移动
		for (int i = theSize; i > index; i--) {
			theItems[i] = theItems[i - 1];
		}
		theItems[index] = t;
		theSize++;
	}

	// 增加
	public boolean add(T t) {
		System.out.println("size():" + size());
		add(size(), t);
		return true;
	}

	// 删除
	public T remove(int index) {
		T removeItem = theItems[index];
		for (int i = index; i < size() - 1; i++) {
			theItems[i] = theItems[i + 1];
		}
		theSize--;
		return removeItem;
	}

	// 添加空间
	public void ensureCapacity(int newCapcity) {
		if (newCapcity < theSize)
			return;
		T[] old = theItems;
		theItems = (T[]) new Object[newCapcity];
		for (int i = 0; i < size(); i++) {
			theItems[i] = old[i];
		}
	}

	// 迭代
	@Override
	public Iterator<T> iterator() {
		return new ArrayListIterator();
	}

	private class ArrayListIterator implements Iterator<T> {

		private int current = 0;

		public boolean hasNext() {
			return current < size();
		}

		public T next() {
			if (!hasNext()) {
				throw new NoSuchElementException();
			}
			return theItems[current++];
		}

		@Override
		public void remove() {
			MyArrayList.this.remove(--current);
		}

	}
}