Блог

Если я разработаю связанный список с нуля, я могу сохранить указатель на объект Node внутри моего класса бизнес-сущностей и добиться постоянных операций O(1) remove и insertAfter . В реализации стандартной библиотеки Java они равны O (n), которые могут сильно отличаться при обработке больших наборов данных.

Почему они просто не сделали класс Node общедоступным и не инкапсулировали в него некоторые детали, по-прежнему делая сам класс (возможно, через интерфейс) доступным? Это сделало бы LinkedList более гибким.

Есть ли у нас что-то вроде FlexibleLinkedList в Apache Commons или Guava?

ListIterator

Почему они просто не сделали класс Node общедоступным и не инкапсулировали в него некоторые детали, по-прежнему делая сам класс (возможно, через интерфейс) доступным?

В этом нет необходимости.

Почему они просто не сделали класс Node общедоступным и не инкапсулировали в него некоторые детали, по-прежнему делая сам класс (возможно, через интерфейс) доступным? Это сделало бы LinkedList более гибким.

Это уже существует.

Если вы хотите воспользоваться преимуществами операций на основе узлов, например:

• Дайте мне следующий элемент, основанный на текущем узле
• Удалите узел, который у меня уже есть, не найдя его
• Вставьте что-нибудь после моего узла, который у меня уже есть

вам просто нужно использовать a ListIterator as, возвращаемый list.ListIterator() . Этот метод предлагается всеми List s.

Этот класс инкапсулирует логику знания текущего узла в итерации и предлагает эффективные методы для манипулирования, которые напрямую используют Node s, такие как:

• add — Элемент вставляется непосредственно перед элементом, который будет возвращен next()
• set — Заменяет последний элемент, возвращенный next() или previous() указанным элементом
• remove — Удаляет из списка последний элемент, который был возвращен next() или previous()

Предлагая методы для управления итерацией с next() помощью и previous() .

Пример

Так что вы могли бы, например, изменить каждый второй элемент:

 LinkedList<Integer> values = new LinkedList<>(List.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10));

int i = 0;
ListIterator<Integer> iter = values.listIterator();
while (iter.hasNext()) {
    iter.next();

    if (i % 2 == 0) {
        iter.set(100);
    }

    i  ;
}
 

В результате чего

 [100, 2, 100, 4, 100, 6, 100, 8, 100, 10]
 

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

 for (int i = 0; i < list.size(); i  ) {
    if (i % 2 == 0) {
        list.set(i, 100);
    }
}
 

что происходит O(n^2) по тем причинам, которые вы изложили.

Преимущества скрытия Node

В общем, гораздо лучше инкапсулировать и скрывать вашу личную внутреннюю работу. Пользователь не должен беспокоиться о том, как LinkedList выполняет свою работу за кулисами.

Кроме того, если это разоблачит Node их, пользователь может незаметно отредактировать их, и весь список сойдет с ума.

Например, пользователь мог бы затем сделать

 Node a = list.getNodeAtIndex(3);   
Node b = a.next;
Node c = b.next;

// Remove b
a.next = c;
c.previous = a;
 

Также без корректировки size списка. So list.size() вернет неправильный номер сейчас, что, вероятно, приведет к сбоям во время итераций.

Или вы также можете ввести опасный цикл:

 a.next = b;
b.next = a;
 

Или забудьте установить previous , что приведет к другому списку при повторении в обратном направлении:

 a.next = c;
c.previous = b;
 

ListIterator гарантирует, что такого не может случиться, предлагая при этом ту же функциональность. Таким образом, вместо того, чтобы предоставлять узлы непосредственно пользователю, он предоставляет только желаемую функциональность в виде методов, над которыми он имеет полный контроль.