每日一记--2014.10.11（2）

今天终于进展到了第三章，好好读了读链表

其实对于linkedlist来说，它的remove也会是O(N)，因为对于删除这个动作确实是常数时间的，但是对于定位到被删除元素的位置就需要有线性时间的开销了

今天参照书上的把ArrayList类编了编，定名为MyArrayListM

  1 package myarraylist;
  2 
  3 import java.util.Iterator;
  4 import java.util.NoSuchElementException;
  5 
  6 public class MyArrayListM<AnyType> implements Iterable<AnyType>{
  7     private static final int DEFAULT_SIZE=10;
  8     private int theSize;
  9     private AnyType[] items;
 10     
 11     MyArrayListM(){
 12         theSize=0;
 13         ensureCapacity(DEFAULT_SIZE);
 14     }
 15     public int size(){
 16         return theSize;
 17     }
 18     public boolean isEmpty(){
 19         return theSize==0;
 20     }
 21     public void trimToSize(){
 22         ensureCapacity(size());
 23     }
 24     public AnyType get(int idx){
 25         if(idx<0|idx>size())
 26             throw new ArrayIndexOutOfBoundsException();
 27         return items[idx];
 28     }
 29     public AnyType set(int idx,AnyType element){
 30         if(idx<0|idx>size())
 31             throw new ArrayIndexOutOfBoundsException();
 32         AnyType old = items[idx];
 33         items[idx]=element;
 34         return old;
 35     }
 36     public void add(AnyType element){
 37         add(size(),element);
 38     }
 39     public void add(int idx,AnyType element){
 40         if(idx<0|idx>size())
 41             throw new ArrayIndexOutOfBoundsException();
 42         if(items.length==size())
 43             ensureCapacity(size()*2);
 44         for(int i=size();i>idx;i--){//改变一下i的取值，可以减少使用一个临时的数组
 45             items[i]=items[i-1];
 46         }
 47         items[idx]=element;
 48         
 49         theSize++;//嗯嗯，这个忘记了
 50     }
 51     
 52     public AnyType remove(int idx){
 53         if(idx<0|idx>size())
 54             throw new ArrayIndexOutOfBoundsException(); 
 55         AnyType removed =items[idx];
 56         for(int i=idx;i<size()-1;i++){
 57             items[i]=items[i+1];
 58         }
 59         theSize--;
 60         return removed;
 61         
 62     }
 63     @SuppressWarnings("unchecked")
 64     private void ensureCapacity(int cap) {
 65         if(cap<size())
 66             return;
 67         AnyType[] old = items;
 68         items = (AnyType[]) new Object[cap];
 69         for(int i=0;i<size();i++){
 70             items[i]=old[i];
 71         }
 72         
 73     }
 74     public Iterator<AnyType> iterator(){
 75         return new ArrayListIterator();
 76     }
 77     private class ArrayListIterator implements Iterator<AnyType> {//ArrayListIterator之后不能加<AnyType>,否则报错
 78         int current =0;
 79         @Override
 80         public boolean hasNext() {
 81             return current <size();
 82         }
 83 
 84         @Override
 85         public AnyType next() {
 86             if(!hasNext())
 87                 throw new NoSuchElementException();
 88             return items[current++];
 89         
 90         }
 91 
 92         @Override
 93         public void remove() {
 94             // TODO Auto-generated method stub
 95             MyArrayListM.this.remove(current--);
 96         }
 97         
 98     }
 99     
100 
101 }