Arraylist映射到鏈表列表節點

Question

我希望能夠在O（1）時間訪問我的雙鏈表中的某個節點。我知道，如果我遍歷列表來查找某個節點，它將花費O（n）時間，所以我想將節點映射到一個數組列表，我可以在O（1）時間訪問節點。

我真的不確定我會如何做這個映射。我希望看到如何做到這一點的例子。

編輯： 我想能夠訪問鏈表中的任何節點，所以我可以在O（1）時間移動節點。

示例：在O（1）時間內將ID爲5的節點移動到列表的末尾。

編輯2：我上傳的是什麼，我試圖完成

Answer 1

你不能用內置的數據結構ArrayList和LinkedList來做到這一點。

通常，不可能在所有具有兩個

• O（1）索引（通過在列表中的位置）
• O（1）刪除/添加/在任何地方移動名單。

可能性：

• 你可以得到O（日誌（N））對於這兩種，如果你使用基於樹的結構。
• 你可以通過基於數組的結構獲得O（1）的索引，但是在中間去除/添加需要O（n）。
• 你可以在O（1）中使用Hash-Map like結構來添加/刪除，但它只允許O（1）通過鍵訪問，而不是通過索引訪問（除了迭代，即O（n）） 。（這意味着，如果您在中間添加/刪除某些內容，其後的索引將不會更改。）

即使您嘗試將鏈接列表與數組組合，您也會有O（n ）刪除/添加（因爲您仍然需要更新數組）。

---

好的，用你添加的圖像來顯示你想要的，這是可行的。實際上，您實際上重新實現了LinkedHashMap之類的東西，但只能使用連續的整數鍵並能夠操作「鏈接」部分。

如果您的鏈接列表由Node對象組成，您將有一個ArrayList<Node>。

在將新節點添加到鏈接列表時，您只會將元素添加到ArrayList，否則僅使用ArrayList進行查找。

下面是一個例子：

class FastIndexLinkedIntList<X> { 
    class Node { 
     Node next; 
     Node prev; 
     int key; 
     X value; 
     Node(int key, X val) { this.key = key; this.value = val; } 
    } 

    ArrayList<Node> indexedNodes = new ArrayList<Node>(); 
    Node head; 
    Node tail; 


    public void add(X value) { 
     int key = indexedNodes.size(); 
     Node node = new Node(key, value); 
     insertAtEnd(node); 
     indexedNodes.add(node); 
    } 

    private void insertAtEnd(Node n) { 
     if(tail == null) { 
     assert head == null; 
     head = n; 
     tail = n; 
     return; 
     } 
     n.prev = tail; 
     n.next = null; 
     tail.next = n; 
     tail = n; 
    } 

    private void removeNode(Node n) { 
     if(n.next == null) { 
     assert n == tail; // last node 

     tail = n.prev; 
     tail.next = null; 
     } 
     else { 
     n.next.prev = n.prev; 
     } 

     if(n.prev == null) { 
     assert n == head; // first node 

     head = n.next; 
     head.prev = null; 
     } 
     else { 
     n.prev.next = n.next; 
     } 
    } 

    public void moveNodeToEnd(int key) { 
     Node n = indexedNodes.get(key); 
     removeNode(n); 
     insertAtEnd(n); 
    } 

} 

你可能想在這裏補充更多的操作，但這些是不夠的問題的例子：

FastIndexedLinkedList<String> ll = new FastIndexedLinkedList<String>(); 
ll.add("0"); 
ll.add("1"); 
ll.add("2"); 
ll.add("3"); 
ll.moveNodeToEnd(2); 

Answer 2

我不能完全肯定你的目的的畫面例子，你只是想檢索對象爲O指數（1）？

這是它會怎樣看：

LinkedList<Object> aList; // your LinkedList 
Map<Object, Integer> mapper = new HashMap<Object, Integer>(); 
Object[] arr = aList.toArray(); 
for(int i = 0; i < arr.length; i++){ 
    mapper.put(arr[i], i); 
} 

現在，如果你想找到你的列表中的對象，你要做的就是獲得從映射對象的指數與

mapper.get(o); 

================================

回覆：您的編輯

你不能（或沒有我知道）。你基本上要求兩個世界中最好的（鏈表和數組）。

Answer 3

使用toArray()方法到您的LinkedList轉換爲固定時間檢索數組：

LinkedList.toArray(arr)

Answer 4

LinkedHashMap：提供O（1）時間和鍵是雙向鏈表有序。