contributed by < vacantron
>
如果逐次檢查相加的數值,時間複雜度為 ;若改用 hash table
記錄差值只與對應的索引,即可將時間複雜度降為
container_of
巨集透過利用 offset_of
巨集從結構體成員的指標計算出結構體的指標
從以下定義得知 pprev 為一個指向前一個節點的 next ( 或是 first ) 成員的 indirect pointer
使用 indirect point 的好處是當我們要從串列中刪除節點 0 時,只要將節點 0 的 pprev 成員指向的指標重新指派給節點 1 的 pprev 成員以及更新 pprev 中指標指向的節點 ( 即前一個元素的 next ( 或是 first ) 指向的節點 ) 即可,不用管節點 0 是不是串列中的第一個元素
故 AAA
應填入 n->next = first
讓新增的節點的 next 成員指向原串列的第一個元素
而 BBB
應填入 n->pprev = &h->first
連接新增的節點與串列的 head
在第 17 行中發現可以藉由更新 indirect pointer 指向的指標的內容來更新上一個節點的 next 指標指向的節點