代碼實(shí)現(xiàn)參見(jiàn)github/algorithm中各個(gè)類別下wz包中的代碼。

1.數(shù)據(jù)結(jié)構(gòu)中常犯錯(cuò)誤

1.1 數(shù)組

• 1）空數(shù)組的寫法——{}

private static final Object[] EMPTY_ELEMENTDATA = {};

• 2）入?yún)z查
  比如數(shù)組的索引有效性檢查
• 3）引用類型數(shù)組刪除時(shí)需要置為null，GC用

// clear to let GC do its work
elementData[--size] = null;

• 4）數(shù)組擴(kuò)容時(shí)新容量各種情況的處理（容易遺漏情況）

    private void ensureExplicitCapacity(int minCapacity) {
        int oldCapacity = elementData.length;
        if (minCapacity - oldCapacity > 0) {
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            // 忘記處理newCapacity比minCapacity小的情況
            // 即使newCapacity溢出，newCapacity - minCapacity也仍大于0
            if (newCapacity - minCapacity < 0) {
                newCapacity = minCapacity;
            }
            // 忘記處理溢出的情況
            if (newCapacity - MAX_CAPACITY > 0) {
                if (newCapacity < 0) {
                    throw new OutOfMemoryError();
                }
                newCapacity = newCapacity > MAX_CAPACITY ? Integer.MAX_VALUE : MAX_CAPACITY;
            }
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    }

1.2 泛型數(shù)組

• 5）set(int, E), add(E); remove(Object), contains(Object)
  涉及到equals的，入?yún)⒍际荗bject

doSomeReading(S<? extends Foo> foos) {
    foos.contains(foo); 
    foos.contains(subFoo);
}

如果contains(E e)函數(shù)只能接受一個(gè)明確類型的參數(shù)。
但是在doSomeReading函數(shù)中，編譯器無(wú)法確定到底是什么類型，它是Foo類型，還是SubFoo類型，還是SubSubFoo類型？
因此這里為了適應(yīng)S<? extends Foo>，將contains的參數(shù)類型設(shè)置為Object，同理remove等的參數(shù)類型也為Object

• 6）刪除的時(shí)候，注意前置條件：數(shù)組中還有元素

1.3 雙鏈表

• 7）確保狀態(tài)更新：add remove時(shí)會(huì)忘了更新size
• 8）循環(huán)語(yǔ)句，尤其是while，也不要忘了三要素
  控制變量的初始化
  循環(huán)條件
  循環(huán)控制變量的更新

1.4 數(shù)組實(shí)現(xiàn)的棧

• 9）定義清楚各個(gè)狀態(tài)變量的含義

    /**
     * 指向棧頂元素，push操作時(shí)是減少head
     */
    private int head;
    /**
     * 指向棧底元素的下一個(gè)，（不考慮大小）因此棧中元素范圍[head, tail)
     */
    private int tail;

• 10）環(huán)形棧push注意事項(xiàng)
  普通寫法：

// 這里錯(cuò)寫成head--導(dǎo)致不更新，忘記了+elements.length，導(dǎo)致負(fù)數(shù)報(bào)錯(cuò)
 head = (--head + elements.length) % elements.length;
 elements[head] = e;

高效寫法，確保數(shù)組大小為2的冪次方

elements[head = (head - 1) & (elements.length - 1)] = e;

• 11）棧為空和棧滿
  （不考慮大?。┮虼藯Ｖ性胤秶鶾head, tail)，因此?？盏臈l件是

public boolean isEmpty() {
        return head == tail;
    }

但要注意：push的時(shí)候，head == tail表示棧滿，但此時(shí)會(huì)進(jìn)行擴(kuò)容，會(huì)重置head和tail

• 12）擴(kuò)容
  注意新容量溢出情況；
  特別注意：不要忘了更新head tail

        // 這里忘了更新head tail，導(dǎo)致出現(xiàn)錯(cuò)誤
        head = 0;
        tail = rightNum;

1.5 雙鏈表實(shí)現(xiàn)的棧

• 13）push
  首先，建議先畫圖再寫代碼，注意更新時(shí)除了結(jié)點(diǎn)之間之間更新之外，不要忘了size
  其次，注意特殊情況，棧為空情況
• 14）pop
  注意將刪除結(jié)點(diǎn)的element和next置為null，help GC

1.6 數(shù)組隊(duì)列

編程時(shí)特別注意的事情：
a）分析清楚方法的前置和后置條件
前置條件：輸入?yún)?shù)需要滿足什么要求
后置條件：操作完要處于什么狀態(tài)
b）注意對(duì)對(duì)象狀態(tài)的更新，這里必須要注意更新head tail elements，若有size，也需注意size
c）對(duì)于集合類的操作，需要在刪除元素時(shí)，將相應(yīng)的slot置為null'

• 15）出隊(duì)
  首先，不要忘了檢查隊(duì)列是否為空（前置條件）
  其次，對(duì)于集合類，刪除時(shí)，不要忘了置為null，help GC

    public E dequeue() {
        // 忘了檢測(cè)當(dāng)隊(duì)列為空時(shí)的錯(cuò)誤
        if (isEmpty()) {
            throw new IllegalStateException("queue is empty!");
        }
        E value = (E)elements[head];
        // 這里必須將elements[head]置為null，忘了
        elements[head] = null;
        head = (head + 1) & (elements.length - 1);
        return value;
    }

1.7 雙鏈表隊(duì)列

無(wú)

1.8 優(yōu)先隊(duì)列

• 16）注意清晰的定義
  實(shí)現(xiàn)最大堆，這里特別注意索引是從1開始的；
  另外，數(shù)組中1..size已經(jīng)存儲(chǔ)了元素，size本身也表示堆中存儲(chǔ)元素的個(gè)數(shù)
• 17）siftUp siftDown
  類似于插入排序，while循環(huán)內(nèi)是queue[parent]，循環(huán)外也是；
  在循環(huán)內(nèi)涉及到right和left，也要進(jìn)行索引是否超出范圍的檢查。

    private void siftDown(int index, int e) {
        int parent = index;
        int left = index << 1;
        int right = left + 1;
        int half = size >> 1;
        while (parent <= half) {
            // 簡(jiǎn)化寫法，合并左右對(duì)稱寫法
            int child = left;
            int c = queue[child];
            // 這個(gè)地方少了對(duì)right索引的判斷，right可能會(huì)超出范圍！
            if (right < size && queue[right] > queue[left]) {
                c = queue[child = right];
            }
            
            if (queue[child] <= e) {
                break;
            }
            queue[parent] = c;
            parent = child;
            left = parent << 1;
            right = left + 1;
        }
        // 最后一個(gè)賦值要放在循環(huán)外，之前放在break里面，會(huì)導(dǎo)致e無(wú)法放到正確的位置！
        queue[parent] = e;
    }

1.9 索引優(yōu)先隊(duì)列

• 18）注意清晰的定義，結(jié)合多路歸并排序來(lái)透徹理解
  在堆數(shù)組中存儲(chǔ)索引i，同時(shí)通過(guò)數(shù)組keys將索引i與key關(guān)聯(lián)起來(lái)，保證堆性質(zhì)的比較還是通過(guò)key來(lái)實(shí)現(xiàn)的（只不過(guò)需要通過(guò)i來(lái)獲取對(duì)應(yīng)的key，多了這一道取值的過(guò)程）

    // 實(shí)際的堆數(shù)組，所有的堆操作都是在pq上進(jìn)行，但是這里存儲(chǔ)的是索引，比較的時(shí)候需要通過(guò)索引關(guān)聯(lián)的key來(lái)進(jìn)行比較
    private int[] pq;
    // 索引關(guān)聯(lián)的key
    private K[] keys;
    // 索引在堆數(shù)組中的位置，這個(gè)與pq是相反的，引入這個(gè)數(shù)組的核心目的是能夠通過(guò)索引快速找到存儲(chǔ)在堆數(shù)組中的位置
    private int[] qp;

• 19）對(duì)索引的范圍的小心處理，在while循環(huán)內(nèi)部少了檢查

1.10 鏈表形式哈希表（非常經(jīng)典）

• 20）putVal
  對(duì)于while循環(huán)，要清楚各個(gè)變量的定義以及三個(gè)要素，并且不要忘了更新size。
  如下，特別重要的是p與node的含義：
  p——是(hash,key)的前驅(qū)結(jié)點(diǎn)，兩種情況：在鏈表末尾和在鏈表中間
  node——是(hash, key)結(jié)點(diǎn)本身，兩種情況：在鏈表末尾（此時(shí)node為null）和在鏈表中間

    private V putVal(int hash, K key, V value) {
        // 數(shù)組table為空
        Node<K,V> p;
        int i;
        if (table == null || table.length == 0) {
            table = resize();
            table[hash & (table.length - 1)] = newNode(hash, key, value, null);
        } else if ((p = table[i = (hash & (table.length - 1))]) == null) {
            // slot為空
            table[i] = newNode(hash, key, value, null);
        } else {
            // 遍歷鏈表，查看是否有key，如果有則更新value；否則放到鏈表尾部
            Node<K,V> node;
            if (p.hash == hash && ((p.key == key) || Objects.equals(key, p.key))) {
                node = p;
            }  else {
                node = p.next;
                do{
                    // 到了鏈表末尾，同時(shí)是首先檢測(cè)node是否為null
                    if (node == null) {
                        p.next = newNode(hash, key, value, null);
                        break;
                    }
                    // 這里需要node不為null
                    if (node.hash == hash && ((node.key == key) || Objects.equals(key, node.key))) {
                        break;
                    }
                    p = node;
                    node = node.next;
                } while (p != null); // 此處之前寫的是node != null，導(dǎo)致無(wú)法在鏈表末尾插入
            }
            if (node != null) {
                afterNodeAccess(node);
                return node.setValue(value);
            }
        }
        // 不要忘了更新size，并判斷是否擴(kuò)容
        size++;
        if (size > threshold) {
            resize();
        }
        afterNodeInsertion();
        return null;
    }

• 21）removeNode
  前置條件：哈希表為空
  特殊情況：刪除的是鏈表首元素
  后置條件：不要忘了更新size
• 22）resize
  數(shù)組擴(kuò)容各種情況的考慮
  將舊表數(shù)組移動(dòng)到新表中時(shí)，需要將舊表對(duì)應(yīng)位置置為null

1.11 開放尋址法哈希表

• 23）刪除
  關(guān)鍵在于刪除，需要將該位置之后的數(shù)據(jù)重新插入
• 24）建議養(yǎng)成編程新習(xí)慣
  首先列出方法的前置條件、后置條件以及各種情況；
  其次根據(jù)這些條件寫出程序大體輪廓
  最后在深入各個(gè)細(xì)節(jié)進(jìn)行處理

1.12 緩存LRU實(shí)現(xiàn)——LinkedHashMap

• 25）afterNodeAccess、linkNodeLast
  e.next不要忘了置為null（畫圖，另一方面，對(duì)于鏈表情況，要注意檢查一下結(jié)點(diǎn)的各個(gè)域是否更新正確）
  不要忘了對(duì)特殊情況的處理

1.13 并查集（不相交集合）

• 26）注意對(duì)count的更新
• 27）find
  對(duì)于遞歸方法，注意不要if和while搞混了