数据结构-List：使用Java实现数组线性表(ArrayList)

JDK中的ArrayList是使用数组来实现的.相对于链表实现,ArrayList查询、修改、在尾部添加和删除元素 效率比较高.

可以自己实现一个ArrayList

 

线性表接口:MyList

public interface MyList<E> {

	public void add(E e);
	public void add(int index,E e);
	public boolean addAll(MyList<E> otherList);
	public boolean addAll(int index,MyList<E> otherList);
	
	public boolean remove(E e);
	public E remove(int index);
	public boolean removeAll(MyList<E> otherList);
	public void clear();
	
	public E set(int index,E e);
	
	public E get(int index);
	
	public boolean contains(E e);
	public int indexOf(E e);
	public boolean retainAll(MyList<E> otherList);
	
	public int size();
	public boolean isEmpty();
	public E[] toArray();
	
	public void print();
}

 

便利类:MyAbstractList 实现了一些通用的操作.

public abstract class MyAbstractList<E> implements MyList<E> {
	
	/**数组大小**/
	protected int size = 0;
	
	/**
	 * 添加元素
	 */
	@Override
	public void add(E e) {
		add(size, e);
	}

	/**
	 * 将一个集合元素添加进来
	 */
	@Override
	public boolean addAll(MyList<E> otherList) {
		return addAll(size, otherList);
	}
	
	/**
	 * 从末尾删除一个元素
	 */
	@Override
	public boolean remove(E e) {
		int index = indexOf(e);
		if(index>=0) {
			remove(index);
			return true;
		}
		return false;
	}

	/**
	 * 差集
	 */
	@Override
	public boolean removeAll(MyList<E> otherList) {
		boolean modified = false;
		for(int i=0;i<otherList.size();i++) {
			if(remove(otherList.get(i))) {
				modified = true;
			}
		}
		return modified;
	}

	/**
	 * 交集
	 */ 
	public boolean retainAll(MyList<E> otherList) {
		boolean modified = false;
		for(int i=0;i<size();) {
			if(!otherList.contains(get(i))) {
				remove(get(i));
				modified = true;
			}else {
				i++;
			}
		}
		return modified;
	}

	@Override
	public int size() {
		return size;
	}

	@Override
	public boolean isEmpty() {
		return this.size==0;
	}
}

 

具体实现：MyArrayList

import java.io.Serializable;
import java.util.Arrays;

public class MyArrayList<E> extends MyAbstractList<E> implements MyList<E>,Cloneable,Serializable {

	
	private static final long serialVersionUID = 5546621768302127857L;

	/**初始容量**/
	private static final int INIT_CAPACITY = 16;
	/**存放元素的数组对象*/
	private transient E[] data;
	
	public MyArrayList() {
		this(INIT_CAPACITY);
	}
	
	/**
	 * 以指定容量创建线性表
	 * @param initCapacity
	 */
	public MyArrayList(int initCapacity) {
		if(initCapacity<0) {
			throw new IllegalArgumentException("Illegal args:"+initCapacity);
		}
		data = (E[]) new Object[initCapacity];
	}
	
	/**
	 * 以一个数组创建线性表
	 * @param es
	 */
	public MyArrayList(E[] es) {
		this(INIT_CAPACITY);
		for(int i=0;i<es.length;i++) {
			add(es[i]);
		}
	}
	
	/**
	 * 以现有集合创建线性表
	 * @param otherList
	 */
	public MyArrayList(MyList<E> otherList) {
		data = otherList.toArray();
		this.size = data.length;
	}
	
	/**
	 * 添加元素
	 */
	@Override
	public void add(int index, E e) {
		if(index<0 || index>size) {
			throw new IndexOutOfBoundsException("index:"+index+",size:"+size);
		}
		ensureCapacity(size+1);
//		for(int i=size;i>index;i--) {
//			data[i] = data[i-1];
//		}
		/**
		 * 1 2 3 4 5 
		 * 1 2 6 3 4 5
		 */
		System.arraycopy(data, index, data, index+1, size-index);
		data[index] = e;
		size++;
	}
	
	/**
	 * 数组容量扩充
	 * @param minCapacity
	 */
	private void ensureCapacity(int minCapacity) {
		int oldCpacity = data.length;
		if(minCapacity > oldCpacity) {
			int newCapacity = (oldCpacity*3)/2+1;
			if(newCapacity < minCapacity) {
				newCapacity = minCapacity;
			}
			E[] oldDate = data;
			data = Arrays.copyOf(oldDate, newCapacity);
		}
	}
	
	
	/**
	 * 在线性表中插入一个集合
	 */
	@Override
	public boolean addAll(int index, MyList<E> otherList) {
		if(index<0 || index>size) {
			throw new IndexOutOfBoundsException("index:"+index+",size:"+size);
		}
		E[] a = otherList.toArray();
		int numNew = a.length;
		ensureCapacity(size+numNew);
		int numMoved = size - index;
		//不在末尾添加元素 才需要进行数组迁移
		if(numMoved>0) {
			System.arraycopy(data, index, data, index+numNew, numMoved);
		}
		System.arraycopy(a, 0, data, index, numNew);
		size  = size+numNew;
		return numNew!=0;
	}

	
	/**
	 * 删除index处的索引
	 * @param index
	 * @return
	 */
	@Override
	public E remove(int index) {
		checkIndex(index);
		E oldElement = data[index];
		/**
		 * 1 2 3 4 5 6 7 8
		 * 1 2 3 4   6 7 8 ---
		 * 					 |
		 * 1 2 3 4 6 7 8   <--
		 * 移动数为size-index-1
		 */
		int numMoved = size - index - 1;
		if(numMoved>0) {
			System.arraycopy(data, index+1, data, index, numMoved);
		}
		data[--size]=null;
		return oldElement;
	}

	/**
	 * 清空线性表
	 */
	@Override
	public void clear() {
		for(int i=0;i<size;i++) {
			data[i] = null;
		}
		size = 0;
	}
	
	/**
	 * 替换元素
	 * @param index
	 * @param e
	 * @return
	 */
	@Override
	public E set(int index, E e) {
		checkIndex(index);
		E oldElement = data[index];
		data[index] = e;
		return oldElement;
	}
	
	/**
	 * 
	 * @param index
	 * @return
	 */
	@Override
	public E get(int index) {
		checkIndex(index);
		return data[index];
	}
	
	/**
	 * 检查索引是否越界
	 * @param index
	 */
	private void checkIndex(int index) {
		if(index<0 || index >= size) {
			throw new IndexOutOfBoundsException("index:"+index+",size:"+size);
		}
	}
	
	/**
	 * 线性表是否包含指定元素
	 * @param e
	 * @return
	 */
	@Override
	public boolean contains(E e) {
		return indexOf(e)>0;
	}
	
	/**
	 * 
	 * @param e
	 * @return
	 */
	@Override
	public int indexOf(E e) {
		for(int i=0;i<size;i++) {
			if(e.equals(data[i])) {
				return i;
			}
		}
		return -1;
	}

	/**
	 * 将线性表转换成数组
	 */
	@Override
	public E[] toArray() {
		return Arrays.copyOf(data, size);
	}
	
	/**
	 * 使当前线性表中数组的长度和线性表中元素的个数相等
	 */
	public void trimToSize() {
		int oldCapacity = data.length;
		//只有当size小于数组长度时才有意义
		if(size < oldCapacity) {
			data = Arrays.copyOf(data, size);
		}
	}
	
	public void print() {
		System.out.print("\n"+this.getClass().getSimpleName()+" [");
		for(int i=0;i<size;i++) {
			System.out.print(data[i]+" ");
		}
		System.out.print("]");
	}
}

 

数组长度是固定的,ArrayList可以看成是增强的数组.长度可以自增长 并提供了一些方便的操作.

由于ArrayList涉及到数组的拷贝和数组元素的迁移 因此 插入和删除比较多的操作 不适合使用ArrayList.

 

评论

1 楼 lvwenwen 2013-04-25  

自己实现一个ArrayList