用数组实现线性表

现在开始进入数据结构的复习！数据结构中最简单的结构就是线性表，线性表又分为多种类型，这篇文章讲的是基于数组实现的线性表，说明了就是自己来实现ArrayList集合，ArrayList采用的数据结构是数组，存储的元素有序但不唯一，查找效率高，但是增删没有LinkedList的效率高。 通过这篇文章你可以知道ArrayList的基本工作方式。

设计ADT

数据结构实际上就是针对一系列数据，设计一系列针对这些数据的操作方法，由于这些数据和操作方法一般来说是共性的特征，所以我们可以使用接口来进行抽象。接口代码如下所示：

public interface ListInterface<T> {

	public boolean add(T newEntry);
	
	public boolean add(int newPosition,T newEntry);
	
	public T remove(int givenPosition);
	
	public void clear();
	
	public boolean replace(int givenPosition,T newEntry);
	
	public T getEntry(int givenPosition);
	
	public boolean contains(T anEntry);
	
	public int getLength();
	
	public boolean isEmpty();
	
	public boolean isFull();
	
	public void display();
	
	public Iterator<T> getIterator();
}

线性表类
定义一个类，implements上面的接口，在类中数据域须为数组，实现接口中声明的操作方法来对数组中的数据进行操作。

public class array_list<T> implements ListInterface<T> {
	PRivate T[] list;
	private int length;
	private static final int MAX_AIZE=10;
	
	public array_list(){
		this(MAX_AIZE);
	}

	public array_list(int capacity) {
		length=0;
		list=(T[]) new Object[capacity];
	}
	
	public void makeRoom(int newPosition){
		for(int i=length;i>=newPosition;i--)
			list[i]=list[i-1];
	}

	public void removeGap(int givenPosition){
		assert givenPosition>0 && givenPosition<length;
		for(int i=givenPosition-1;i<length-1;i++)
			list[i]=list[i+1];
	}

	public boolean isArrayFull() {
		return length==list.length;
	}

	@SuppressWarnings("unchecked")
	private void doubleArray(){
		T[] oldArray=list;
		list=(T[]) new Object[2*oldArray.length];
		System.arraycopy(oldArray, 0, list, 0, oldArray.length);
	}

	@Override
	public boolean add(T newEntry) {
		if(isArrayFull())
			doubleArray();
		list[length]= newEntry;
		length++;
		return true;
	}

	@Override
	public boolean add(int newPosition, T newEntry) {
		if(isArrayFull())
			doubleArray();
		makeRoom(newPosition);
		list[newPosition-1]= newEntry;
		length++;

		return true;
	}

	@Override
	public T remove(int givenPosition) {
		T result=null;
		if(givenPosition>0 && givenPosition<=length){
			assert !isEmpty();
			result=list[givenPosition-1];
			if(givenPosition<length)
				removeGap(givenPosition);
			length--;
		}
		return result;
	}

	@Override
	public void clear() {
		length=0;
		for(int i=0;i<list.length;i++)
			list[i]=null;
	}

	@Override
	public boolean replace(int givenPosition, T newEntry) {
		boolean isSuccessful=true;
		if(givenPosition>0 && givenPosition<=length)
			list[givenPosition-1]= newEntry;
		else
			isSuccessful=false;
		return isSuccessful;
	}

	@Override
	public T getEntry(int givenPosition) {
		T result=null;
		if(givenPosition>0 && givenPosition<=length){
			assert !isEmpty();
			result=list[givenPosition-1];
		}
		return result;
	}

	@Override
	public boolean contains(T anEntry) {
		boolean found=false;
		for(int i=0;!found && i<length;i++)
			if(anEntry.equals(list[i]))
				found=true;
		return found;
	}

	@Override
	public int getLength() {
		return length;
	}

	@Override
	public boolean isEmpty() {
		return length==0;
	}

	@Override
	public boolean isFull() {
		//		return length==entry.length;
		return false;
	}

	@Override
	public void display() {
		Iterator iterator=getIterator();
		while(iterator.hasNext()){
			System.out.print(iterator.next()+" ");
		}
	}

	@Override
	public Iterator<T> getIterator() {
		return new IteratorForArrayList();
	}
	
	private class IteratorForArrayList implements Iterator<T>{
		
		private int nextIndex;
		private boolean wasNextCalled;
		
		public IteratorForArrayList() {
			nextIndex=0;
			wasNextCalled=false;
		}

		@Override
		public boolean hasNext() {
			return nextIndex<length;
		}

		@Override
		public T next() {
			if(hasNext()){
				wasNextCalled=true;
				T nextEntry=list[nextIndex];
				nextIndex++;
				return nextEntry;
			}else
				throw new NoSuchElementException("");
		}
		
		public void remove(){
			if(wasNextCalled){
				array_list.this.remove(nextIndex);
				nextIndex--;
				wasNextCalled=false;
			}else
				throw new IllegalStateException("");
		}
	}

}

测试代码
public class main {

	private static array_list<Integer> list;
	public static void main(String[] args) {
		list=new array_list<Integer>();
		for(int i=0;i<20;i++)
			list.add(i);
		list.display();
		
		System.out.println();
		list.add(16, 167);
		list.display();
		
		System.out.println();
		list.replace(3, 101);
		list.display();
		
		System.out.println();
		list.remove(6);
		list.display();
		
		System.out.println();
		System.out.println(list.contains(99));
	}
}测试结果
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 167 15 16 17 18 19 
0 1 101 3 4 5 6 7 8 9 10 11 12 13 14 167 15 16 17 18 19 
0 1 101 3 4 6 7 8 9 10 11 12 13 14 167 15 16 17 18 19 
false