Arraylist 映射到链表节点 [英] Arraylist mapping to linkedlist nodes

问题描述

我希望能够在 O(1) 时间内访问我的双向链表中的某个节点.我知道如果我遍历列表以找到某个节点需要 O(n) 时间，所以我想将节点映射到一个数组列表，我可以在 O(1) 时间内访问这些节点.

I want to be able to access a certain node in my Doubly Linked List in O(1) time. I know that if i traverse the list to find a certain node it would take O(n) time so I want to map the nodes to an array list where I can access the nodes in O(1) time.

我真的不确定我将如何进行此映射.我想看看如何做到这一点的示例.

I'm really unsure how I would do this mapping. I would like to see an example of how this can be done.

我希望能够访问链表中的任何节点，以便我可以在 O(1) 时间内移动节点.

I would like to be able to access any node in the linked list so I can move the nodes around in O(1) time.

示例:在 O(1) 时间内将 ID 为 5 的节点移动到列表的末尾.

Example: Move node with ID 5 to end of list in O(1) time.

编辑 2:我上传了我想要完成的图片示例

Edit 2: I uploaded a picture example of what I'm trying to accomplish

推荐答案

使用内置数据结构 ArrayList 和 LinkedList 无法做到这一点.

You can't do this with the built-in data structures ArrayList and LinkedList.

一般来说，两者都不可能同时拥有

In general, it is not possible at all to have both of

• O(1) 索引(按列表中的位置)
• O(1) 删除/添加/移动列表中的任何位置.

可能性:

• 如果您使用基于树的结构，则这两者都可以达到 O(log(N)).
• 您可以使用 O(1) 来使用基于数组的结构进行索引，但随后在中间删除/添加需要 O(n).
• 您可以在 O(1) 中使用具有添加/删除功能的 Hash-Map 类结构，但它只允许 O(1) 通过键访问，而不允许通过索引访问(迭代除外，即 O(n)).(这意味着，如果您在中间添加/删除某些内容，则其后面的索引不会更改.)

即使您尝试将链表与数组组合，您也将有 O(n) 来删除/添加(因为您仍然需要更新数组).

Even if you try to combine a linked list with an array, you'll have O(n) for removing/adding (since you still have to update the array).

好的，使用您添加的图像来显示您想要的内容，这是可行的.实际上，您是在重新实现 LinkedHashMap 之类的东西，但只能使用连续的整数键和操作Linked"部分的能力.

Okay, with your added image to show what you want, it is doable. You are in fact reimplementing something like LinkedHashMap, but only with consecutive integer keys and with ability to manipulate the "Linked" part.

如果您的链表由 Node 对象组成，您将拥有一个 ArrayList.

If your linked list consists of Node objects, you would have an ArrayList<Node>.

只有在向链表添加新节点时才向 ArrayList 添加元素，否则仅将 ArrayList 用于查找.

You would only add elements to the ArrayList when adding new nodes to the linked list, else use the ArrayList only for lookup.

这是一个例子:

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);
   }

}

您可能想在此处添加更多操作，但对于问题中的示例来说，这些已经足够了:

You might want to add more operations here, but these are enough for the example in the question:

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

这篇关于Arraylist 映射到链表节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！