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.

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

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

我上传了我要完成的图片示例

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).
• 您可以在H(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<Node>.

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屋！