是否有任何方式來實現鏈接列表與索引訪問呢？

Question

我需要一種鏈接列表結構，但是如果它已經索引訪問，它會很好。

是否有任何方法可以實現這一目標？

編輯：我在C寫，但它可能是任何語言。

Answer 1

您可能可以使用樹來實現您的目標。製作一棵維護樹中每個節點權重的二叉樹（其中權重等於連接到該節點的節點數量，包括其本身）。如果您有一個可用於樹的平衡方案，那麼插入仍然是O（log n），因爲您只需要向祖先節點的權重添加一個。通過索引獲取節點是O（log n），因爲您只需查看所需節點的祖先和每個祖先的兩個孩子的索引。

Answer 2

爲了在像C++，Java，Python這樣的語言中實現像索引這樣的數組索引，必須爲實現鏈表數據結構的類重載數組索引操作符[]。實現將是O（n）。在C中，由於運算符重載是不可能的，因此必須編寫一個函數，該函數接受鏈表數據結構和位置並返回相應的對象。

如果需要更快的訂單訪問，則需要使用不同的數據結構，例如jprete建議的BTree或動態數組（其自動增長並添加新元素時）。一個簡單的例子是C++標準庫中的std::vector。

Answer 3

在clustered index are arranged like so SQL服務器行項目：

. 
/\ 
/\ /\ 
*-*-*-* 

鏈表是葉(*-*-*)。鏈接列表的順序允許快速定向掃描，並且該樹作爲鏈接列表中的「路線圖」。因此，您需要爲您的項目設置鍵值對，然後使用封裝樹和鏈接列表的數據結構。

所以你的數據結構可能是這個樣子：

實現目標的

struct ll_node 
{ 
    kv_pair current; 
    ll_node * next; 
}; 

struct tree_node 
{ 
    value_type value; 
    short isLeaf;   

    union 
    { 
     tree_node * left_child; 
     kv_pair * left_leaf; 
    } 
    union 
    { 
     tree_node * right_child; 
     kv_pair * right_leaf 
    } 
}; 

struct indexed_ll 
{ 
    tree_node * tree_root; 
    ll_node * linked_list_tail; 
}; 

Answer 4

一種方法是實現一個隨機或確定性skip list。在最底層 - 你有你的物品的鏈接列表。

爲了獲得使用索引的元素，您需要向內部節點添加信息 - 多少個節點處於最低級別，從此節點到此級別上的下一個節點。這些信息可以在O（logn）中添加和維護。

此解決方案的複雜性是： 添加，刪除，轉到索引，所有工作在O（logn）。

該解決方案的缺點是實現比常規鏈表要困難得多。因此，使用常規鏈接列表，您可以在O（1）中獲取添加，刪除以及轉到O（n）中的索引。