tags: java

隨手閒聊 ArrayDeque

• 隨手閒聊 ArrayDeque
  • 前言
  • 核心想法
    • addFirst
    • addLast
    • 擴容時機

前言

在寫leetcode 題目 LRUCache, 想說可以試試看用ArrayDeque.

突然想到 array 如果依照一般操作, addFirst 在最開頭插入, 那不是效率很差嗎？ 每次都要把東西往後搬

Ex:

因此就起了勁trace一下, 應該是有特別的做法

核心想法

Deque 主要就是一個讓使用者可以在頭、尾都可以加入元素的 container, 因此主要重點在於 怎麼加入頭、尾

我們先專注在 addFirst

addFirst

一樣的例子, 在頭部插入一個 -1.
一般的想法就是:

將元素插入array 的第一個位置

那現在我想要不移動其他元素的前提, 增加一個元素進來.
就得換個想法:

1. 將新的元素視為插入原本array 的左邊
2. 為了不移動原有元素, 當作原本的內容就在右邊

0	0	0	0	1	2

0	0	0	-1	1	2

如此一來就辦到所想的了~~~

addLast

一樣的想法, 不多贅述

擴容時機

• addFirst 變成從右到左加入, index_head 每次 -1
• addLast 變成從左到右加入, index_tail 每次 +1

因此當執行 addFirst or addLast 時,

發現即將添加的地點, 已有元素存在, 那就是額滿需擴容了

也就是

// call `addFirst` or `addLast`
if (index_head == index_tail) {
  // 需要擴容摟~
}

實際上java.util.ArrayDeque 的index 做法很特別~
這裡因為要讓各位簡單理解, 採用上述敘述方式.
建議各位自己trace 看一下~
是利用餘數的概念去做的~