數組線性表ArrayList的内部實作

線性表是按順序存儲資料是常用的一種資料結構。大多數線性表的典型操作是：

1，初始化線性表

2，判斷表是否為空

3，求線性表的長度

4，讀取線性表中的第i個元素

5，查找滿足條件的資料元素

6，線上性表的第i個位置之前插入一個新的資料元素

7，删除線性表中的第i個資料元素

8，表置空

9，查找第i個元素的前驅或後繼

10，按一個或多個資料項遞增或遞減重新排列資料元素

數組線性表是順序存儲結構，是最簡單，最常用的資料結構。是在記憶體中開辟一片連續的存儲空間，用一組連續的存儲單元一次存放資料元素。順序存儲的特點是邏輯上相鄰的資料元素，它們實體位置也是相連的。

優點是：簡單，直覺，随機存取元素十分容易實作，根據定位公式很容易找到表中每個元素的存儲位置，是以指定第i個結點很友善

缺點是：插入和删除結點困難，算法效率不高。因為結點是順序存放的，是以插入或删除一個結點時，必須将該結點以後的所有元素依次向後移動，或者依次向前移動。

JDK1.5以後ArrayList開始引入泛型

接口MyList<E>有操作線性表的基本方法，MyAbstractList<E>抽象類實作了MyList<E>接口，但是該抽象類隻是實作了接口中的部分方法，MyArrayList<E>繼承擴充抽象類MyAbstractList<E>抽象類

接口MyList<E>

public interface MyList<E> {
  //添加一個元素
  public void add(E e);
  //在index處添加一個元素
  public void add(int index,E e);
  //清楚一個list清單
  public void clear();
  //删除一個元素
  public boolean remove(E e);
  //删除并傳回index處的元素
  public E remove(int index);
  //index處的元素設定為元素e
  public Object set(int index,E e);
  //判斷是否包含元素e
  public boolean contains(E e);
  //傳回index處的元素
  public E get(int index);
  //傳回清單中第一個與元素e比對的下标index
  public int indexOf(E e);
  //傳回清單中最後一個與元素e比對的元素下标index
  public int lastIndeOf(E e);
  //判斷清單是否為空
  public boolean isEmpty();
  //傳回清單的大小
  public int size(); 
}
           

MyAbstractList<E>抽象類

public abstract class MyAbstractList<E> implements MyList<E> {//部分實作MyList接口
    protected int size=0;  
	protected MyAbstractList(){
    	
    }
    protected MyAbstractList(E[] objects){
    	for(int i=1;i<objects.length;i++)
    	add(objects[i]);
    }
    @Override
    public void add(E e){
    	add(size,e);
    }
    @Override
    public void add(int index,E e){
    	
    }
    @Override
    public boolean isEmpty(){
    	return size==0;
    }
    @Override
    public int size(){
    	return size;
    }
    @Override
    public boolean remove(E e){
    	if(indexOf(e)>=0){
    		remove(indexOf(e));
    		return true;
    	}
    	else return false;
    }
    @Override
    public E remove(int index){
    	return null;
    }
    @Override
   	public void clear() {
   		// TODO Auto-generated method stub
   		
   	}
   	@Override
   	public Object set(int index, E e) {
   		// TODO Auto-generated method stub
   		return null;
   	}
   	@Override
   	public boolean contains(E e) {
   		// TODO Auto-generated method stub
   		return false;
   	}
   	@Override
   	public E get(int index) {
   		// TODO Auto-generated method stub
   		return null;
   	}
   	@Override
   	public int indexOf(E e) {
   		// TODO Auto-generated method stub
   		return 0;
   	}
   	@Override
   	public int lastIndeOf(E e) {
   		// TODO Auto-generated method stub
   		return 0;
   	}
}
           

MyArrayList<E>

public class MyArrayList<E> extends MyAbstractList<E> {
      public static final int INITIAL_CAPACITY=16;
      private E[] data=(E[])new Object[INITIAL_CAPACITY];
      
      public MyArrayList(){
    	  
      }
      public MyArrayList(E[] objects){
    	  for(int i=0;i<objects.length;i++)
    	  add(objects[i]);
      }
      public void add(int index,E e){
    	  ensureCapacity();
    	  for(int i=size-1;i>=index;i--)
    		  data[i+1]=data[i];
         data[index]=e;
         size++;   	  
      }
	private void ensureCapacity() {
		if(size>=data.length){
			E[] newData=(E[])(new Object[size*2+1]);
			System.arraycopy(data, 0, newData, 0, size);
			data=newData;
		}
	}
	
	public void clear(){
		data=(E[])new Object[INITIAL_CAPACITY];
		size=0;
	}
	public boolean contains(E e){
		for(int i=0;i<size;i++){
			if(e.equals(data[i])) return true;			
		}
		return false;
	}
	public E get(int index){
		return data[index];
	}
	public int indexOf(E e){
		for(int i=0;i<size;i++)
			if(e.equals(data[i])) return i;
		return -1;
	}
	public int lastIndexOf(E e){
		for(int i=size-1;i>=0;i--)
			if(e.equals(data[i])) return i;
		return -1;
	}
	public E remove(int index){
		E e=data[index];
		for(int j=index;j<size-1;j++)
			data[j]=data[j+1];
		
		data[size-1]=null;
		size--;
		return e;
	}
	public E set(int index,E e){
		E old=data[index];
		data[index]=e;
		return old;
	}
	public String toString(){
		StringBuilder result=new StringBuilder("[");
		for(int i=0;i<size;i++){
			result.append(data[i]);
			if(i<size-1) result.append(",");
		}
		return result.toString()+"]";
	}
	public void trimToSize(){
		if(size!=data.length){
			E[] newData=(E[])new Object[size];
			System.arraycopy(data, 0, newData, 0, size);
			data=newData;
		}
	}
}