4
我遇到的訪談問題涉及到Gap Buffer數據結構的實現。特別是，我正在討論一個基本上是LinkedList的數據結構，其中每個Node都是一個（相當小的）char數組。這是文本編輯的理想選擇，因爲您可以在任何位置插入更多字符，如果您沒有找到空間，可以分配新陣列。訪談解決方案 - 修改間隙緩衝區
實現間隙緩衝區本身沒有什麼大不了，因爲它看起來完全像一個LinkedList，並且實現像Add和Remove這樣的方法在算法上是直截了當的。如果有空間，只需將新字符插入相應位置的節點中，如果需要更多空間，則分配新節點。
最困難的問題是一個有效的實施Trim方法與後置條件，當運行Trim，間隙緩衝區中的所有非空白元素將被「壓縮」朝開始，也就是說，所有的元素儘可能向前移動，並將空間裁剪掉。
簡單的方法是簡單地遍歷每個數組元素，將其移動到下一個空閒空間，直到所有元素都被迭代，然後刪除列表末尾的所有空節點。然而，這並不理想：
如果在迭代過程中我們接近一個空的數組，我們應該立即從列表中移除該數組，從而連接它周圍的2個數組。另一方面，如果我們接近一個完全滿的數組，我們應該跳過數組，因爲它已經被壓縮了。
這兩種情況是我們在效率方面需要考慮的唯一情況嗎？還有其他可能的改進嗎？那麼完全有效的Trim看起來像算法嗎？
因此，gap buffer是小陣列的列表。我們可以在修整過程中創建新的陣列嗎？ – Dialecticus
我很困惑這個問題，可能是因爲如果濫用術語。間隙緩衝區不是鏈接列表;它們甚至與鏈接列表沒有太大的共同之處。間隙緩衝區是一個數組，其中所有可用空間在中間某處（在當前的「光標」位置）保持連續。不需要壓縮操作。一些編輯使用鏈接列表的間隙緩衝區。這是你問的嗎？ –
是的，我正在談論當許多間隙緩衝區作爲節點鏈接在一起時實現的數據結構。因此，當插入緩衝區中的任何位置時，可以將一個字符插入到數組位置，或者如果該位置的數組已滿，則分配另一個節點以提供更多空間。 – donnyton