恆定時間插入列和行的矩陣結構

Question

我正在尋找一個矩陣結構，這是一個允許我在常量時間插入新行和列的二維排序數組。有點像二維鏈表。

我不能使用二維鏈接列表的原因是因爲我仍然想保持表格的結構。

我對訪問沒有任何要求，但結構必須可迭代。 去除也應該是恆定的時間。

我在猜測，這是無法完成的，而且在插入新列時插入新行和所有行時必須遍歷所有列。

我問這個問題，以防萬一這樣的事情是可能的。

Answer 1

最後我用我自己的解決方案。我使用兩個鏈接列表和一個將一對鏈接列表節點作爲關鍵字的字典。插入一個行和一列是O（1），因爲鏈接列表和查找是O（1），因爲字典。

Answer 2

您可能想考慮類似稀疏矩陣的東西。缺省值/空值由沒有項目記錄表示，並且整個矩陣結構頭部包含矩陣的維度。只需增加結構的邊界屬性，行和列就可以快速地追加。

但是，如果您還想在現有行和列之間插入行和列，則事情會變得棘手，您需要兩個列表和一個二維雙向鏈表的組合。你不會在這裏得到恆定的時間插入。

您的基本結構將包含一個包含行標題和包含列標題的結構的結構。通過右列表實現，插入/刪除行或列標題將是O（n）（即，與行/列的數量有關）。然後，每行和每個列標題都會有一個指向其數據項的指針列表，它們在哪裏存在。同樣，使用正確的列表實現，插入數據也應該是O（n），與行中項目的數量和列中項目的數量有關。這種表現與列表相似。