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）时间和键是双向链表有序。