用数组实现线性表

现在开始进入数据结构的复习！数据结构中最简单的结构就是线性表，线性表又分为多种类型，这篇文章讲的是基于数组实现的线性表，说明了就是自己来实现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