資料結構之--單連結清單MyArrayList

仿照Java集合類庫中的ArrayList，自己手動寫了一個MyArrayList，内部使用一個數組來維護。具體的adt描述如下

isEmpty()　　　　判斷是否為空

size()　　　　　　擷取目前存儲的元素個數

clear()　　　　　清空目前的所有元素

set(idx, e)　　　　重置指定位置的元素

ensureCapacity(newCapacity)　　指定底層數組的大小

add(e)　　　　　　添加一個元素，預設在尾部

add(idx, e)　　　　在指定位置添加一個元素

remove(idx)　　　　删除指定位置的元素

iterator()　　　　　　傳回相應的疊代器

1 /**
  2  * 手寫的一個MyArraylist實作ArrayList的正常操作，并且也實作了疊代器
  3  * 實作疊代器操作，必須要實作Iteratable接口
  4  * @author Administrator
  5  *
  6  * @param <AnyType> 手寫的這個順序表支援泛型
  7  */
  8 public class MyArrayList<AnyType> implements Iterable<AnyType>{
  9     private static final int DEFAULT_CAPACITY = 10;    //預設的 大小為 10
 10     
 11     private int thisSize ;    // 目前已經存入的元素的個數
 12     private AnyType[] theItems;    //定義一個數組用來存儲元素, 而且是一種懶漢模式來維護的
 13     
 14     public MyArrayList(){
 15         clear();
 16     }
 17     
 18     /**
 19      * 清空這個連結清單
 20      */
 21     public void clear()
 22     {
 23         thisSize = 0;
 24         ensureCapacity(DEFAULT_CAPACITY);
 25     }
 26     
 27     public int size(){
 28         return thisSize;
 29     }
 30     public boolean isEmpty()
 31     {
 32         return size()==0;    // 當thisSize==0說明為空連結清單
 33     }
 34     public void trimToSize()
 35     {
 36         ensureCapacity(size());
 37     }
 38     
 39     public AnyType get(int idx)
 40     {
 41         if(idx < 0 || idx >= size())
 42             throw new ArrayIndexOutOfBoundsException();    //    抛出數組越界的異常
 43         return theItems[ idx ];
 44     }
 45     /*
 46      * 重置指定位置idx處的元素 為 newVal
 47      */
 48     public AnyType set(int idx, AnyType newVal)
 49     {
 50         if(idx <= 0 || idx >= size())
 51             throw new ArrayIndexOutOfBoundsException();
 52         AnyType old = theItems[ idx ];
 53         theItems[idx] = newVal;
 54         return old;
 55     }
 56     
 57     public void ensureCapacity( int newCapacity )
 58     {
 59         if(newCapacity < thisSize)// 不需要 修改數組的大小
 60             return ;
 61         
 62         AnyType[] old = theItems;    //先把原來的數組記錄下來
 63 //        theItems = new AnyType[newCapacity]; 注意了 不能這樣建立一個泛型的數組 向下面那樣操作就行了
 64         theItems = (AnyType[]) new Object[ newCapacity ];
 65         for (int i = 0; i < size(); i++) {
 66             theItems[i] = old[i];
 67         }
 68     }
 69     
 70     // 預設在尾部插入
 71     public boolean add(AnyType x)
 72     {
 73         add(size(), x);
 74         return true;
 75     }
 76     
 77     public void add(int idx, AnyType x)
 78     {
 79         if(theItems.length == size())
 80             ensureCapacity(size()*2 + 1);    //一旦size不夠 就擴容兩倍
 81         // 先把 [idx, size]的元素向後移動
 82         for(int i = thisSize; i > idx; i--)// 為什麼 不是 i = thisSieze - 1; 因為初始 thisSize=0的時候 會出現數組越界的情況
 83             theItems[i] = theItems[i-1];
 84         theItems[idx] = x;
 85         thisSize ++;
 86     }
 87     
 88     public AnyType remove(int idx)
 89     {
 90         if(idx <= 0 || idx > size())
 91             throw new ArrayIndexOutOfBoundsException();
 92         AnyType removeItem = theItems[idx-1];
 93         // 吧[idx+1, size]元素想做移動1
 94         for(int i = idx-1; i < size(); i++)
 95             theItems[i] = theItems[i+1];
 96         
 97         thisSize --;
 98         return removeItem;
 99     }
100     
101     
102     @Override
103     public Iterator<AnyType> iterator() {
104         return new MyArrayListIterator();
105     }
106     
107     // 内部類的形式 定義一個自己的 疊代器  内部類 可以友善的通路 外部類的 資料成員
108     private class MyArrayListIterator implements Iterator<AnyType>
109     {
110         private int current = 0;
111         
112         @Override
113         public boolean hasNext() {
114             return current < size();
115         }
116 
117         @Override
118         public AnyType next() {
119             if(!hasNext())
120                 throw new NoSuchElementException();
121             
122             return theItems[current++];
123         }
124 
125         @Override
126         public void remove() {
127             MyArrayList.this.remove(--current);    // 建立調用内部類的方法
128         }
129         
130     }
131     
132     public static void main(String[] args) {
133         MyArrayList<Integer> list = new MyArrayList<Integer>();
134         
135         System.out.println(list.isEmpty());
136         System.out.println(list.size());
137         
138         list.add(1);
139         list.add(2);
140         list.add(3);
141         list.add(4);
142         System.out.println(list.isEmpty());
143         System.out.println(list.size());
144         
145         System.out.println(list.remove(2));
146         
147         System.out.println(list.size());
148         
149         Iterator<Integer> it = list.iterator();
150         while(it.hasNext())
151             System.out.print(it.next()+", ");
152         System.out.println();
153     }
154 
155 }      

 line103~line130其實是很有内容的，這裡把ArrayListIterator定義成了一個内部類。

private class ArrayListIterator implements Iterator<AnyType>{

　　private int current = 0;

　　public boolean hasNext()

　　{return current < size()}　　//current < MyArrayList.this.size()

　　………………

　　public void remove()

　　{MyArraylList.this.remove(--current);}　　// 為了消除歧義，就不能簡寫了

},

上面其實都是内部類（Internal class），内部類裡面可以直接通路外部類的屬性和方法，其實在内部類中調用外部類的方法和屬性時，實際上應當是帶上外部類的一個引用比如應當是current < MyArrayList.this.size(),内部類的一大好處是允許程式員簡寫成current < size(),簡寫的前提是内部類和外部類沒有回引起歧義的同名方法或者同名屬性，如果會引起歧義時就不能再簡寫了，比如下面的 remove方法，内部類ArrayListIterator和外部類MyArrayList都有這個方法，那麼在内部類總調用外部類的remove方法時，就不能簡寫了，應當寫成MyArrayList.this.remove(--current);

private static class ArrayListIterator implements Iterator<AnyType>{

}

這種定義情況和上一中乍一看差不多，隻是多了一個static關鍵字而已，這時ArrayListIterator就不在是一個内部類，搖身一變成了一個嵌套類（Nest額的 Class）。嵌套類因為是一個static的，隻能通路被嵌套類中的靜态屬性和靜态方法。

轉載于:https://www.cnblogs.com/OliverZhang/p/6596897.html