資料結構和集合概論

資料結構、集合概述、集合架構中的接口

• 資料結構
• • 線性表
  • 連結清單
• 概述集合
• • 數組和集合的比較
• 集合架構中的接口
• • Collection接口
  • • 常見方法
  • Iterator疊代器
  • • List接口
    • Set接口
  • 常見的List接口的實作類
  • • ArrayList實作類

資料結構

線性表

（數組）存儲區間是連續的，占用記憶體嚴重，故空間複雜度很大。但數組的二分查找(前提是必須有序)時間複雜度小，為O(1)；

數組的特點是：

• 尋址容易(arr[n]=arr[0]+n*每個元素的長度，時間複雜度為O(1))
• 插入和删除困難(可能會引發一半以上的資料元素移動，時間複雜度為O(n))；
• Java中的數組是定長的，如果需要變長則需要自行程式設計實作

連結清單

存儲區間離散(資料不是連續存放的)，占用記憶體比較寬松，故空間複雜度很小，但操作元素的時間複雜度很大，達O（N）。

連結清單的特點是：

• 尋址困難（可能需要通過周遊的方式查找元素，時間複雜度為O(n)）
• 插入和删除容易(不需要引發元素的移動，僅僅隻是進行位址的拷貝，時間複雜度為O(1))。

概述集合

• 集合隻能存放對象。比如你存一個 int 型資料 1放入集合中，其實它是自動轉換成 Integer 類後存入的(裝箱操作)，Java中每一種基本類型都有對應的引用類型
• 集合存放的是多個對象的引用，對象本身還是放在堆記憶體中
• 集合可以存放不同類型，不限數量的資料類型。定義集合變量時如果不指定資料類型，則預設資料類型為Object

數組和集合的比較

針對Java中的數組定長，Java提出了集合架構，實作了一種變長存儲資料的容器—集合【容積和目前元素個數】

數組不是面向對象的，存在明顯的缺陷，集合彌補了數組的缺點，比數組更靈活更實用，而且不同的集合架構類可适用不同場合。如下：

• 數組能存放基本資料類型和對象，而集合類存放的都是對象的引用，而非對象本身
• 數組容量固定無法動态改變，集合類容量動态改變
• 數組無法判斷其中實際存有多少元素，length隻告訴了數組的容量，而集合的size()可以确切知道元素的個數
• 集合有多種實作方式和不同适用場合，不像數組僅采用順序表方式
• 集合以類的形式存在，具有封裝、繼承、多态等類的特性，通過簡單的方法和屬性即可實作各種複雜操作，大大提高了軟體的開發效率

集合架構中的接口

Collection接口

• 頂級接口，繼承Iterable接口
• 無序、允許重複

常見方法

• size():int擷取元素個數
• contains(Object):boolean 判斷集合中是否有指定對象
  • 使用的是equals方法進行判斷，不是==
• toArray():Object[] 将集合中的所有元素以數組方式進行傳回
• add(Object):boolean 向集合中添加元素
• remove(Object):boolean 從集合中删除指定的元素
  • 使用的是equals方法進行判斷，不是==
• clear():void 删除集合中的所有元素，清空集合

• isEmpty():boolean 判斷元素個數是否為0，不判斷null
  • list.size()<1

Iterator疊代器

用于周遊集合中的所有元素

• Collection接口繼承于Iterable接口，是以所有的Collection接口的實作類都可以進行周遊通路
  • Iterator it=list.iterator();
  • while(it.hasNext()){ //判斷是否還有沒有周遊通路的元素
    • Object tmp=it.next(); //指針後移，同時擷取一個元素
  • }

如何擷取疊代器

list.iterator():Iterator 具體的疊代器一般是由實作類提供具體的實作

List接口

List接口是Collection接口的子接口

有序、允許重複

注意：凡是使用下标參數的，要求下标必須在[0,list.size())

• E get(int index);按照下标擷取指定位置上的元素，index就是下标值，要求index的值不能超過[0,list.size())，否則IndexOutOfBoundsException
• E set(int index, E element) 修改指定位置index上的元素為新元素element，并傳回原始位置上的元素 修改操作
• void add(int index, E element) 在指定位置index上添加新元素element
• E remove(int index)删除指定下标index位置上的元素，并傳回删除的元素
• int indexOf(Object o) 從前向後查找o在集合中的第一個下标位置，如果查找不到則傳回-1
• int lastIndexOf(Object o);
• default void sort(Comparator<? super E> c) 使用自定義的比較器對象對資料元素進行排序，按照升序進行排序

Set接口

Set接口是Collection接口的子接口

無序、不允許重複[重複元素的添加會産生覆寫]

沒有新方法

boolean add(E e);向集合中追加元素e對象，如果出現重複則後蓋前

問題：如何判斷兩個元素相等

• 首先比較兩個對象的hashcode值是否相等，如果hashcode值不相等則不會調用equals，認為兩個對象不相等
• 如果hashcode值相等才調用equals進行比較，否則不相等

潛規則【不是文法】：SUN要求當兩個對象的equals為true時，hashcode值應該相等

常見的List接口的實作類

• ArrayList：數組實作，查詢快，增删慢，輕量級；(線程不安全)
• LinkedList：雙向連結清單實作，增删快，查詢慢 (線程不安全)
• Vector：數組實作，重量級 (線程安全、使用少)

ArrayList實作類

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
           

内部實作

transient Object[] elementData;  用于存儲資料，展現ArrayList采用的是數組的方式提供實作
           

構造器

//new ArrayList(1000);
public ArrayList(int initialCapacity) {  //參數是初始化容積
      if (initialCapacity > 0) { 如果容積初始值大于0則建立對應的對象
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) { 如果容積值位0則建立一個空數組
            this.elementData = EMPTY_ELEMENTDATA;
        } else { 如果小于0則抛出一個運作時異常
            throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
        }
}
//new ArrayList();
 public ArrayList() {  沒有初始化參數值，則自動建立一個0個長的空數組
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
           

add方法的實作

//向存儲資料的elementData添加新元素
public boolean add(E e) {
     ensureCapacityInternal(size + 1);  //確定内部容量,處理數組elementData的長度，確定可以存放資料，如果目前數組長度不足，則需要增加數組長度。參數的含義是滿足條件的最小容積
     elementData[size++] = e;
     return true;   //如果添加過程中不出異常，則傳回一定是true
}
           

ensureCapacityInternal方法

private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
     
  private void ensureExplicitCapacity(int minCapacity) {
        modCount++;  //修改次數加1
        if (minCapacity - elementData.length > 0)  如果所需要的最小容積大于實際存儲資料的數組長度，則需要進行擴容處理
            grow(minCapacity);
    }
     
    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;  擷取實際數組的長度
        //符号>>表示二進制向右移位計算，>>1表示除以2,>>2表示除以4(2的平方).如果<<表示乘以2的多少次方
        int newCapacity = oldCapacity + (oldCapacity >> 1);  //新的容積值=舊有容器*1.5
        if (newCapacity - minCapacity < 0)  新容器如果小于所需要的最小容積，則新容積為最小容積值
            newCapacity = minCapacity;
             
        //int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
        if (newCapacity - MAX_ARRAY_SIZE > 0)   如果新容積值大于所允許的最大容積值
            newCapacity = hugeCapacity(minCapacity);  擷取滿足最小容積需求的合法的容積值
        //從elementData拷貝所有的數組元素，Arrays是工具類，提供了常見的針對數組的操作方法
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
     
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0)   如果最小容積值小于0則抛出錯誤，表示OOM記憶體溢出
            throw new OutOfMemoryError();
            //例如擷取的最小容積值為Integer.MAX_VALUE-7
        return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
+
 
           

add方法用于向集合中添加元素，如果ArrayList中真正存放資料的數組長度不足，則建立一個數組，新數組的長度為原始長度1.5倍，并拷貝原始數組中的資料到新數組中，最後再追加新元素