您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 相關知識

Java 資料結構核心類別與自定義雙向鏈表實作

編輯：Java 相關知識

1. 陣列

陣列是物件，需實例化。元素可為基本型別或物件參考，但型別必須一致。
宣告：String[] names = new String[10]; 或 String[] names = {"a","b","c"};
多維：int[][] coords = new int[12][12];
屬性：length。

2. Enumeration 介面

hasMoreElements()：是否有下一個
nextElement()：取得下一個，無則拋 NoSuchElementException

3. BitSet

位元集合，適合布林旗標群組。方法：set(index)、clear(index)、get(index)、size()、xor(BitSet) 等。

4. Vector

動態陣列，容量不足自動擴充。建構子：new Vector(20, 5)（初始 20，每次增 5）。
方法詳見 java.util。

5. Stack

先進後出 (LIFO)。方法：push()、pop()、peek()、empty()、search(Object)。

6. Dictionary 抽象類別

定義鍵值對應結構。Hashtable 繼承自此。抽象方法：put(k,v)、get(k)、remove(k)、size()、isEmpty()、keys()、elements()。

7. Hashtable

繼承 Dictionary，實作 Serializable，常用於序列化傳輸。
建構子：Hashtable()、Hashtable(int)、Hashtable(int, float)、Hashtable(Map)。
capacity * loadFactor 達臨界值時 rehash（擴容為 2x capacity）。預設 loadFactor=0.75。
put(key, value) 會計算 hashCode。

8. 自定義雙向鏈表

三個類別：

LinkedListEntry：節點（值、前驅、後繼）
LinkedList：主類別（頭、尾、節點數）
LinkedListEnumerator：實作 Enumeration

8.1 LinkedListEntry

class LinkedListEntry {
    protected Object val = null;
    protected LinkedListEntry next = null;
    protected LinkedListEntry prev = null;
    public LinkedListEntry(Object obj) {
        if (obj == null) throw new NullPointerException();
        val = obj;
    }
}

8.2 LinkedListEnumerator

class LinkedListEnumerator implements Enumeration {
    protected LinkedListEntry pos;
    public LinkedListEnumerator(LinkedList list) { pos = list.start; }
    public boolean hasMoreElements() { return pos != null; }
    public Object nextElement() {
        if (pos == null) throw new NoSuchElementException();
        LinkedListEntry tmp = pos;
        pos = pos.next;
        return tmp.val;
    }
}

8.3 LinkedList 核心方法節錄

欄位：start、end、numElements

addElement (尾端新增)

public void addElement(Object obj) {
    if (obj == null) throw new NullPointerException();
    LinkedListEntry newElement = new LinkedListEntry(obj);
    numElements++;
    if (start == null) {
        start = end = newElement;
    } else {
        end.next = newElement;
        newElement.prev = end;
        end = newElement;
    }
}

insertElementAt (指定節點前插入)

public void insertElementAt(Object obj, Object pos) {
    if (obj == null || pos == null) throw new NullPointerException();
    LinkedListEntry posEntry = find(pos);
    if (posEntry == null) throw new NullPointerException();
    LinkedListEntry newElement = new LinkedListEntry(obj);
    numElements++;
    newElement.next = posEntry;
    newElement.prev = posEntry.prev;
    if (posEntry == start) start = newElement;
    else posEntry.prev.next = newElement;
    posEntry.prev = newElement;
}

find (依值查找)


private LinkedListEntry find(Object obj) {
    if (isEmpty() || obj == null) return null;
    LinkedListEntry tmp = start;
    while (tmp != null) {
        if (tmp.val == obj) return tmp;
        tmp = tmp.next;
    }
    return null;
}

contains / isEmpty / elements


public boolean contains(Object obj) { return find(obj) != null; }
public boolean isEmpty() { return start == null; }
public Enumeration elements() { return new LinkedListEnumerator(this); }