Отображение Arraylist на узлы связного списка

Question

Я хочу иметь возможность получить доступ к определенному узлу в моем двусвязном списке за O (1) раз. Я знаю, что если я перейду по списку, чтобы найти определенный узел, потребуется O (n) времени, поэтому я хочу сопоставить узлы со списком массивов, где я могу получить доступ к узлам за O (1) времени.

Я действительно не уверен, как бы я сделал это отображение. Я хотел бы увидеть пример того, как это можно сделать.

Edit: Я хотел бы иметь возможность доступа к любому узлу в связанном списке, чтобы я мог перемещать узлы за O (1) раз.

Пример: переместить узел с идентификатором 5 в конец списка за O (1) раз.

Редактировать 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);

Answer 2

Используйте метод toArray() для преобразования вашего LinkedList в массив для поиска в постоянном времени:

LinkedList.toArray(arr)

Answer 3

LinkedHashMap : обеспечивает время O (1), а ключи - это список с двойной связью.

Answer 4

Я не совсем уверен в вашей цели, вы просто хотите получить индекс объекта в 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 с помощью

mapper.get( o );

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

Re: ваше редактирование

Вы не можете (или я ничего не знаю).По сути, вы требуете лучшего из обоих миров (связанных списков и массивов).