ArrayList

List接口

package changsheng.algorithms.list;

import java.util.Iterator;

public interface List<E> {
	public boolean add(E e);
	public void add(E e,int i);
	
	public E remove(int i);
	public boolean remove(E e);
	public void removeAll();
	
	public E set(int i,E e );
	
	public E get(int i);
	public int indexOf(E e);
	
	int size();
	
	boolean contains(E e);
	
	boolean isEmpty();
	
	Iterator<E> iterator();
	public E[] toArray();
	
}
           

实现ArrayList采用了测试驱动开发的模式，首先书写了Unit Test，然后再进行开发。

JUnit Test

package changsheng.algorithms.list;

import static org.junit.Assert.*;

import org.junit.Test;

public class ArrayListTest {

	@Test
	public void testAddAndGet() {
		/******************************************************/
		List<String> list = new ArrayList<String>();
		for (int i = 0; i < 10; i++) {
			list.add(String.valueOf(i));
		}
		for (int i = 0; i < 10; i++) {
			assertEquals(String.valueOf(i), list.get(i));
		}
	}

	@Test
	public void testSize() {
		List<String> list = new ArrayList<String>();
		for (int i = 0; i < 10; i++) {
			list.add(String.valueOf(i));
		}
		assertEquals(10, list.size());
	}

	@Test
	public void testAddTail() {
		/* 测试边缘情况，在末尾添加元素 */
		List<String> list = new ArrayList<String>();
		for (int i = 0; i < 10; i++) {
			list.add(String.valueOf(i));
		}
		String expected = String.valueOf(11);
		list.add(expected);
		assertEquals(expected, list.get(10));
	}

	@Test
	public void testAddFront() {
		/* 测试边缘情况，在表头添加元素 */
		List<String> list = new ArrayList<String>();
		for (int i = 0; i < 10; i++) {
			list.add(String.valueOf(i));
		}
		list.add(String.valueOf(-1), 0);
		assertEquals(-1, Integer.parseInt(list.get(0)));
	}

	@Test
	public void testRemoveAll() {
		List<String> list = new ArrayList<String>();
		for (int i = 0; i < 10; i++) {
			list.add(String.valueOf(i));
		}
		list.removeAll();
		assertEquals(0, list.size());
	}

	@Test
	public void testRemove() {
		List<String> list = new ArrayList<String>();
		for (int i = 0; i < 10; i++) {
			list.add(String.valueOf(i));
		}
		String number = list.remove(0);

		int expectedValue = 0;
		int expectedSize = 9;

		assertEquals(expectedValue, Integer.parseInt(number));
		assertEquals(expectedSize, list.size());
	}

	@Test
	public void testRemoveFront() {
		/* 测试边缘情况，在表头移除元素 */
		List<String> list = new ArrayList<String>();
		for (int i = 0; i < 10; i++) {
			list.add(String.valueOf(i));
		}

		list.remove(0);

		for (int i = 0; i < 9; i++) {
			int expected = i + 1;
			assertEquals(expected, Integer.parseInt(list.get(i)));
		}
	}

	@Test
	public void testRemoveTail() {
		/* 测试边缘情况，在末尾移除元素 */
		List<String> list = new ArrayList<String>();
		for (int i = 0; i < 10; i++) {
			list.add(String.valueOf(i));
		}
		list.remove(9);

		int expectedSize = 9;
		int expectedNumber = 8;

		assertEquals(expectedNumber, Integer.parseInt(list.get(8)));
		assertEquals(expectedSize, list.size());
	}

	@Test
	public void testSet() {
		List<String> list = new ArrayList<String>();
		for (int i = 0; i < 10; i++) {
			list.add(String.valueOf(i));
		}
		String number = list.set(4, String.valueOf(-1));

		int expectedNumberOld = 4;
		int expectedNumberNew = -1;

		assertEquals(expectedNumberOld, Integer.parseInt(number));
		assertEquals(expectedNumberNew, Integer.parseInt(list.get(4)));
	}

	@Test
	public void testIndexOfFirst() {
		/* 测试边缘情况,第一个元素 */
		List<String> list = new ArrayList<String>();
		for (int i = 0; i < 10; i++) {
			list.add(String.valueOf(i));
		}

		int expecteds = 0;
		int actuals = list.indexOf(list.get(0));

		assertEquals(expecteds, actuals);
	}

	@Test
	public void testIndexOfLast() {
		/* 测试边缘情况,最后一个元素 */
		List<String> list = new ArrayList<String>();
		for (int i = 0; i < 10; i++) {
			list.add(String.valueOf(i));
		}

		int expecteds = 9;
		int actuals = list.indexOf(list.get(9));

		assertEquals(expecteds, actuals);
	}

	@Test
	public void testIndexOfNo() {
		List<String> list = new ArrayList<String>();
		for (int i = 0; i < 10; i++) {
			list.add(String.valueOf(i));
		}

		int expecteds = -1;
		int actuals = list.indexOf(new String());

		assertEquals(expecteds, actuals);
	}

	@Test
	public void testContains() {
		/* 测试边缘情况,最后一个元素 */
		List<String> list = new ArrayList<String>();
		for (int i = 0; i < 10; i++) {
			list.add(String.valueOf(i));
		}

		int expecteds = 9;
		int actuals = list.indexOf(list.get(9));

		assertEquals(expecteds, actuals);
	}

	@Test
	public void testContainsNo() {
		List<String> list = new ArrayList<String>();
		for (int i = 0; i < 10; i++) {
			list.add(String.valueOf(i));
		}

		boolean expecteds = false;
		boolean actuals = list.contains(new String());

		assertEquals(expecteds, actuals);
	}

	@Test
	public void testToArray() {
		List<String> list = new ArrayList<String>();
		int[] actuals = new int[10];
		for (int i = 0; i < 10; i++) {
			list.add(String.valueOf(i));
			actuals[i] = i;
		}
		int[] expecteds = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
		assertArrayEquals(expecteds, actuals);
	}
	
	@Test(expected=IndexOutOfBoundsException.class)
	public void testAddException1() {
		List<String> list = new ArrayList<String>();
		for (int i = 0; i < 10; i++) {
			list.add(String.valueOf(i));
		}
		list.add(new String(), -1);
	}
	
	@Test(expected=IndexOutOfBoundsException.class)
	public void testAddException2() {
		List<String> list = new ArrayList<String>();
		for (int i = 0; i < 10; i++) {
			list.add(String.valueOf(i));
		}
		list.add(new String(), 10);
	}
	
	@Test(expected=IndexOutOfBoundsException.class)
	public void testRemoveException1() {
		List<String> list = new ArrayList<String>();
		for (int i = 0; i < 10; i++) {
			list.add(String.valueOf(i));
		}
		list.remove( -1);
	}
	
	@Test(expected=IndexOutOfBoundsException.class)
	public void testRemoveException2() {
		List<String> list = new ArrayList<String>();
		for (int i = 0; i < 10; i++) {
			list.add(String.valueOf(i));
		}
		list.remove( 10);
	}
	
	@Test(expected=IndexOutOfBoundsException.class)
	public void testSetException1() {
		List<String> list = new ArrayList<String>();
		for (int i = 0; i < 10; i++) {
			list.add(String.valueOf(i));
		}
		list.set(-1,new String());
	}
	
	@Test(expected=IndexOutOfBoundsException.class)
	public void testSetException2() {
		List<String> list = new ArrayList<String>();
		for (int i = 0; i < 10; i++) {
			list.add(String.valueOf(i));
		}
		list.set(10,new String());
	}
	
	@Test(expected=IndexOutOfBoundsException.class)
	public void testGetException1() {
		List<String> list = new ArrayList<String>();
		for (int i = 0; i < 10; i++) {
			list.add(String.valueOf(i));
		}
		list.get(-1);
	}
	
	@Test(expected=IndexOutOfBoundsException.class)
	public void testGetException2() {
		List<String> list = new ArrayList<String>();
		for (int i = 0; i < 10; i++) {
			list.add(String.valueOf(i));
		}
		list.get(10);
	}
	
	

}
           

ArrayList实现

在JDK源码中，ArrayList对null元素进行了处理，感兴趣的可以查看JDK源码。

package changsheng.algorithms.list;

import java.util.Arrays;
import java.util.Iterator;

public class ArrayList<E> implements List<E> {

	private E[] elementData;
	private int elementCount;
	private int DEFAULT_SIZE = 10;

	@SuppressWarnings("unchecked")
	public ArrayList() {
		elementData = (E[]) new Object[DEFAULT_SIZE];
		elementCount = 0;
	}

	/**
	 * 在末尾添加元素e
	 * 
	 * @param e
	 *            待添加的元素
	 * @return 如果添加成功返回true
	 */
	@Override
	public boolean add(E e) {
		ensureCapacity(elementCount + 1);
		elementData[elementCount++] = e;
		return true;
	}

	/**
	 * 将e元素添加到index位置上
	 * 
	 * @param e
	 *            待添加的元素
	 * @param index
	 *            待添加的索引位置
	 */
	@Override
	public void add(E e, int index) {
		if (index < 0 || index > elementCount - 1) {
			throw new IndexOutOfBoundsException();
		}
		ensureCapacity(elementCount + 1);
		for (int i = elementCount - 1; i > index; i--) {
			elementData[i] = elementData[i - 1];
		}
		elementCount++;
		elementData[index] = e;

	}

	/**
	 * 移除索引位置为index的元素，并返回该元素
	 */
	@Override
	public E remove(int index) {
		if (index < 0 || index >= elementCount) {
			throw new IndexOutOfBoundsException();
		}
		E oldValue = elementData[index];
		for (int i = index; i < elementCount - 1; i++) {
			elementData[i] = elementData[i + 1];
		}
		elementData[--elementCount] = null;

		return oldValue;
	}

	/**
	 * 移除e元素
	 * 
	 * @param e
	 *            待移除的元素
	 * @return 如果找到该元素成功删除返回true，否则返回false
	 */
	@Override
	public boolean remove(E e) {
		if (elementCount == 0) {
			return false;
		}
		for (int i = 0; i < elementCount; i++) {
			if (e.equals(elementData[i])) {
				remove(i);
				return true;
			}
		}
		return false;
	}

	/**
	 * 移除所有元素
	 */
	@SuppressWarnings("unchecked")
	@Override
	public void removeAll() {
		/**
		 * JDK源码中clear方法中的清空方式为将数组中的元素都赋值为null，
		 * 让GC进行回收，并没有改变数组的大小。
		 * 
		 * 在此处的方法只是将elementData赋值为一个新的默认数组。
		 */
		elementData = (E[]) new Object[DEFAULT_SIZE];
		elementCount = 0;
	}

	/**
	 * 将index位置的元素设置为e，并返回原始元素
	 * 
	 * @param index
	 *            索引位置
	 * @param e
	 *            元素
	 * @return 返回原始元素
	 */
	@Override
	public E set(int index, E e) {
		if (index < 0 || index >= elementCount) {
			throw new IndexOutOfBoundsException();
		}

		E oldValue = elementData[index];
		elementData[index] = e;
		return oldValue;

	}

	/**
	 * 获取index位置的元素
	 */
	@Override
	public E get(int index) {
		if (index < 0 || index >= elementCount) {
			throw new IndexOutOfBoundsException();
		}
		return elementData[index];
	}

	/**
	 * 获取待寻找元素的索引
	 * 
	 * @param e
	 *            待寻找的元素
	 * @return 如果存在返回待寻找元素的索引，否则返回-1
	 */
	@Override
	public int indexOf(E e) {
		for (int i = 0; i < elementCount; i++) {
			if (e.equals(elementData[i])) {
				return i;
			}
		}
		return -1;
	}

	/**
	 * 返回元素
	 */
	@Override
	public int size() {
		return elementCount;
	}

	/**
	 * 判断是否包含此元素
	 * 
	 * @param e
	 *            待寻找的元素
	 * @return 如果找到该元素返回true，否则返回false
	 */
	@Override
	public boolean contains(E e) {
		return indexOf(e) >= 0;
	}

	/**
	 * 返回迭代器
	 */
	@Override
	public Iterator<E> iterator() {
		return null;
	}

	/**
	 * 返回对象数组
	 */
	@Override
	public E[] toArray() {
		return Arrays.copyOfRange(elementData, 0, elementCount - 1);
	}

	/**
	 * 扩展容器数组
	 * 
	 * @param newLength
	 *            长度
	 */
	private void ensureCapacity(int newLength) {
		if (newLength == elementData.length) {
			/* 对其进行2倍长度扩展 */
			elementData = Arrays.copyOf(elementData, elementData.length * 2);
		}
	}

	/**
	 * 列表是否为空
	 */
	@Override
	public boolean isEmpty() {
		return elementCount == 0;
	}

}