使用數組實現鏈表 - 優點和缺點

Question

我知道如何使用數組實現鏈表。例如 我們定義一個結構如下：

struct Node{ 
    int data; 
    int link; 
} 

「數據」存儲下一個節點的數組中的信息和「鏈接」存儲的索引。

任何人都可以告訴我，與「普通」鏈表相比，使用數組實現鏈表的優點和缺點是什麼？任何建議將不勝感激。

Answer 1

如果你返回一個鏈接列表與數組，你最終會有的缺點。因此，這可能不是一個很好的實施方法。

一些缺點立刻：

1. 你必須在數組中死亡空間（當前未使用的項目條目）佔用內存
2. 你必須跟蹤免費的條目 - 在一些插入和刪除之後，這些免費條目可以在任何地方。
3. 使用數組會對鏈表的大小施加上限。

我想一些優點是：

1. 如果你是一個64位系統上，你的「指針」，將佔用更少的空間（儘管要求的免費項目額外的空間可能遠遠超過這一優勢）
2. 您可以將數組序列化到磁盤並輕鬆地使用mmap()調用重新讀取它。儘管如此，你最好使用某種協議緩衝區來實現可移植性。
3. 您可以對陣列中的元素在內存中彼此靠近做出一些保證。

Answer 2

有誰可以告訴我什麼是使用數組鏈接列表實現鏈接列表與「普通」鏈接列表的優勢和劣勢？

鏈表具有以下的複雜性：

• 缺點X的xs：O（1）
• 追加納米：爲O（n）
• 索引i的xs：Ò （n）

如果您的代表ntation採用嚴格的，連續的數組，你將有不同的複雜性：

• 利弊需要複製舊的陣列：O（n）的
• 追加既需要陣列複製到一個新的連續空間：O（N + M）
• 索引可被實現爲數組訪問：O（1）

即，在術語實現的鏈表API數組的行爲將像一個數組一樣。

您可以通過使用嚴格數組的鏈表或樹來緩解這種情況，從而導致繩索或手指樹或惰性序列。

Answer 3

堆棧實現兩種方式。 首先使用數組，第二使用鏈表。

使用數組然後大部分程序員使用鏈表中的一些缺點在堆棧中實現。

首先是使用鏈表的堆棧首先不聲明堆棧大小並且不限制數據存儲在堆棧中。第二是指針作文中的鏈表來聲明和使用它。

只有一個指針在鏈表中使用。它被稱爲頂級指針。

堆棧是lifo方法的用法。但鏈表程序實現中存在一些缺點。

大多數程序員使用喜歡的列表使用堆棧實現。

Answer 4

使用數組實現，您可以更快速地訪問列表中的節點，另一方面，可以使用指針實現鏈接列表，您可以隨機訪問節點。 當您處理固定編號時，數組實現很有用。因爲如果需要從列表的中間插入/刪除節點，因此調整數組的大小是昂貴的，因爲如果需要從列表的中間插入/刪除節點，則必須在每個節點之後進行移動。 與此相反，當你不知道否時，應該使用指針實現。的節點，因爲這樣的列表可以有效地增長/縮小，您不需要移動任何節點，只需通過取消引用&引用指針即可完成。