java - Arraylist 映射到链表节点

Question

我希望能够在 O(1) 时间内访问双向链表中的某个节点。我知道，如果我遍历列表来查找某个节点，则需要 O(n) 时间，因此我想将节点映射到数组列表，在其中我可以在 O(1) 时间内访问节点。

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

编辑:我希望能够访问链表中的任何节点，这样我就可以在 O(1) 时间内移动节点。

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

编辑2:我上传了一张图片示例来说明我想要完成的任务

Answer 1

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

一般来说，两者根本不可能兼得

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

可能性:

• 如果您使用基于树的结构，则这两种情况的复杂度都可以达到 O(log(N))。
• 使用基于数组的结构进行索引的时间复杂度为 O(1)，但在中间删除/添加则需要 O(n)。
• 您可以使用类似于 Hash-Map 的结构，在 O(1) 中添加/删除，但它只允许通过键进行 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);