Перемещение указателей вместо объектов в каком-то списке или очереди в Java

Java предлагает реализацию LinkedList интерфейса List, который на самом деле является двусвязным списком. Если мы делаем следующее:

linkedlist.remove(obj);

а потом:

linkedlist.add(obj);

мы фактически удаляем объект obj из связанного списка и повторно вставляем его с правого конца (хвоста).

Мы также можем вручную реализовать связанный список с узлами, головой и хвостом. В таких языках, как C++, которые имеют некоторые низкоуровневые характеристики, можно использовать указатели для следующего и предыдущего объекта объекта obj. Таким образом, нам не нужно удалять элемент, а просто обновлять предыдущий и следующий указатели.

Существует ли в Java какая-либо структура данных, с которой мы можем получить такой же эффект (и, следовательно, тот же прирост производительности, когда удаляются только "указатели", вставленные из самих объектов)?

Обратите внимание, что я хотел бы использовать готовую структуру данных вместо того, чтобы вручную писать свою единую реализацию связного списка (и, возможно, заново изобретать колесо). Кроме того, обратите внимание, что он не обязательно должен быть связанным списком - это может быть, например, какая-то очередь, такая как ArrayDeque.

РЕДАКТИРОВАТЬ: Проще говоря, если внутренне реализация LinkedList интерфейса List в Java использует указатели prev и next, то почему l.remove(obj) - это O(n), а не O(1)? И, таким образом, на практике, когда у вас есть LinkedList со многими миллионами объектов (как в моем случае), так много времени уходит на удаление и повторную вставку? (То же самое с ArrayList, то же самое с ArrayDeque - очень долго).

Источник

2 ответа

Решение

Ответить на вопрос о том, почему remove(Object obj) является O(n):

Во-первых, для того, чтобы оно было O(1), вам нужно дать remove Настоящий Node ссылка, а не Object, Object не будет указывать на Node, Для того, чтобы найти правильный Node чтобы вернуться, код должен либо искать в списке, чтобы найти Node который содержит объект, или сохранить хэш-карту, которая позволит ему найти Node, Настоящий LinkedList Реализация делает простой линейный поиск. Тем не менее, даже хеш-карта, технически, будет O (n), поскольку существует вероятность того, что все объекты в списке имеют одинаковый хеш-код, хотя все равно будет намного быстрее, чем линейный поиск.

Во-вторых, remove(Object obj) определяется с точки зрения equals, Если есть другой объект obj2 который был добавлен в список, и obj2.equals(obj) является true, затем remove(obj) удалит obj2 если obj Сама ссылка никогда не была добавлена ​​в список.

Чтобы действительно сделать это правильно, вам понадобится либо add метод, который возвращает ссылку на узел, чтобы ваша программа могла отслеживать ссылку на узел и использовать ее в качестве remove аргумент; или вы могли бы потребовать, чтобы объекты в списке реализовали какую-то NodePointer интерфейс:

interface NodePointer {
    void setNodePointer(Object node);
    Object getNodePointer();
}

этот список затем будет использовать для вставки указателей узлов в объекты. (Но это, вероятно, означает, что объект может жить только в одном связанном списке за раз, ограничение, которое LinkedList не навязывает.) В любом случае, я не думаю, что это то, что поддерживает библиотека Java.

Источник

Java делает то же самое, что и C++. Все ссылки на объекты являются указателями. Итак, в узле, как

public class Node [
    private Object value;
    private Node next;
    private Node previous;
}

value, next а также previous являются указателями (называемыми ссылками в Java) соответственно на значение узла, следующего узла и предыдущего узла.

Разница с C++ в том, что у вас нет арифметики указателей: value++например, не компилируется и не делает ссылку на указатель на то, что находится по следующему адресу памяти.

РЕДАКТИРОВАТЬ:

Класс LinkedList не раскрывает свои узлы снаружи. Они полностью закрыты для LinkedList. Таким образом, удаление объекта заключается в итерации по всем узлам, чтобы найти тот, который имеет значение, равное (с точки зрения Object.equals()) к данному объекту и удалить найденный узел из списка. Удаление узла состоит в том, чтобы сделать предыдущую точку следующей, и наоборот. Вот почему удаление объекта является O(n). Конечно, если у вас есть доступ к узлу и вы можете удалить его, операция будет O(1). Если вам это нужно, вам придется реализовать свой собственный LinkedList, точно так же, как вы делали бы это в C++. Ссылки являются указателями.

Источник
Другие вопросы по тегам