Блог

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

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

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

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

Правка 2: Я загрузил пример изображения того, чего я пытаюсь достичь

Вы не можете этого сделать с помощью встроенных структур данных ArrayList и LinkedList.

В общем случае вообще невозможно иметь оба

• O (1) индексирование (по позиции в списке)
• O (1) удаление / добавление / перемещение в любом месте списка.

Возможности:

• Вы можете получить доступ к O (log (N)) для обоих из них, если используете древовидную структуру.
• Вы можете перейти к O (1) для индексации с помощью структуры на основе массива, но тогда удаление / добавление в середине занимает O (n).
• Вы можете использовать структуру, подобную хэш-карте, с добавлением / удалением в 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);
  

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

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

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

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

LinkedList.toArray(arr)