Java集合之ArrayList和LinkedList的實現原理

ArrayList實現可變數組的原理：

　　當元素超出數組內容，會產生一個新數組，將原來數組的數據復制到新數組中，再將新的元素添加到新數組中。

　　ArrayList:是按照原數組的50%來延長，構造一個初始容量為10的空列表

用ArrayList模擬數組：

 package iterater.patten.design;
 
 //探索ArrayList實現的可變數組的原理，用ArrayList實現一個容器存儲對象
 public class ArrayList {
     Object[] objects = new Object[10];
     // 定義計數器，用於計算數組中的元素個數
     int index = 0;
 
     public void add(Object o) {
         // 當數組滿時，則創建一個新的數組，將原數組中的元素復制進新數組中，再將新的元素加入到數組中
         if (index == objects.length) {
             // 按原數組的2倍長度創建新數組，其實這樣不太合理
             Object[] newObjects = new Object[objects.length * 2];
             // 將原數組中的元素復制進新數組中，再將新的元素加入到數組中
             System.arraycopy(objects, 0, newObjects, 0, objects.length);
             // 數組引用指向新的數組
             objects = newObjects;
         }
 
         // 將新增元素放到數組中
         objects[index] = o;
         index++;
     }
 
     // 定義size函數獲取元素個數
     public int size() {
         return index;
     }
 }

　　用LinkedList模擬數組

 package iterater.patten.design;
 
 //探索LinkedList實現的可變數組的原理，用LinkedList實現一個容器存儲對象
 public class LinkedList {
 
     //定義鏈表的頭指針head以及尾指針tail
     Node head = null;
     Node tail = null;
     int size = 0;
 
     //添加元素
     public void add(Object o) {
         //一個新的結點
         Node n = new Node(o, null);
         //當鏈表為空時，head指向新添加的結點，tail也指向該結點
         if (head == null) {
             head = n;
             tail = n;
         }
         //鏈表不為空時，tail包含的下一個結點的引用指向這個新加入的結點
         
         tail.setNext(n);
         tail = n;
         size++;
     }
 
     public int size() {
         return size;
     }
 }

　　Node結點的類定義　

 package iterater.patten.design;
 
 //定義一個類來存儲鏈表中的結點
 public class Node {
 
     private Object data;
     private Node next;
     public Object getData() {
         return data;
     }
     public void setData(Object data) {
         this.data = data;
     }
     public Node getNext() {
         return next;
     }
     public void setNext(Node next) {
         this.next = next;
     }
     public Node(Object data, Node next) {
         super();
         this.data = data;
         this.next = next;
     }
     
 }

　　添加的元素對象所屬的類的類定義

 package iterater.patten.design;
 
 public class Cat {
 
     private int id;
 
     public int getId() {
         return id;
     }
 
     public void setId(int id) {
         this.id = id;
     }
 
     public Cat(int id) {
         super();
         this.id = id;
     }
 }

　　測試類　

 package iterater.patten.design;
 
 import iterater.patten.design.*;
 
 public class IteratorTest {
 
     /**
      * @param args
      */
     public static void main(String[] args) {
 
         // ArrayList al=new ArrayList();
         LinkedList al = new LinkedList();
         for (int j = 0; j < 15; j++) {
             al.add(new Cat(j));
         }
         System.out.println(al.size());
     }
 
 }

　　輸出結果：15

【溫情提示】：我們在測試類中為了提高容器的可替換性，可以定義一個接口Collection,定義add、size方法，只要保證容器類實現該接口，當用戶使用add添加元素或者使用size獲取元素個數的時候就可以更加方便(因為如果ArrayList中的添加元素方法叫add，而LinkedList中添加元素的方法叫addall,用戶在使用的時候就會造成困擾，使用定義接口的方式，我們只對接口進行編程使用，不用去關心具體的實現內容。

　　代碼實現：

 public interface Collection {
 
     public Object add(Object o);
     public int size();
 }

　　ArrayList和LinkedList實現該接口，並覆蓋抽象方法即可，測試類中可以這樣使用兩個方法：

　　Collection c=new ArrayList();

　　c.add(object)、c.size;

　　父接口引用指向子類對象，並調用子類中覆蓋的方法