Есть ли различия в производительности между одно- и двусвязными списками?

Question

Наше домашнее задание просит нас доказать, что реализация Java LinkedList является двусвязной, а не односвязной. Однако операции со списками, такие как добавление элементов, удаление элементов и поиск элементов, по-видимому, имеют одинаковую сложность для обеих реализаций, поэтому не представляется возможным использовать аргумент производительности для демонстрации двусвязной природы Java. LinkedList. Кто-нибудь знает лучший способ проиллюстрировать разницу между ними?

Answer 1

Это довольно простое доказательство - вы смотрите на исходный код и видите, что у каждого узла есть указатель .previous :) http://www.docjar.com/html/api/java/util/LinkedList.java.html

Answer 2

Посмотрите на итерации в прямом или обратном направлении, удалив элемент "before-last" и тому подобное.

Answer 3

В интерфейсе Java List нет метода, позволяющего удалить элемент без поиска в связанном списке.Он имеет функцию удаления (int index), которая должна сканировать список, чтобы найти проиндексированную запись, а также функцию удаления (объект o), которая также должна сканировать список.Поскольку реализация связанного списка может сохранять необходимый контекст записи предыдущего элемента при сканировании, удаление имеет эквивалентную сложность для односвойных и двусвязных списков.Это состояние также может быть сохранено в итераторе, поэтому Iterator.remove () не меняет этого.Поэтому я не думаю, что вы можете отличить производительность от удаления.

Я предполагаю, что «правильный» ответ на этот вопрос заключается в создании нескольких списков разных размеров и времени выполнения .indexOf () и .lastIndexOf() при поиске первого или последнего объекта.Предполагая, что реализация является двусвязной и ищет в начале списка .indexOf () и ищет в конце .lastIndexOf (), производительность будет зависеть от длины или длины.

Answer 4

Рассмотрим следующие узлы, одинарные и двойные.

class SingleLinkedNode { E данные; SingleLinkedNode next; }

class DoubleLinkedNode { E данные; DoubleLinkedNode prev; DoubleLinkedNode next; }

Если мы хотим удалить из DoubleLinkedList (при условии, что мы уже НАШЛИ узел, который сильно отличается), что нам нужно сделать?

1. Сделать узел перед удаленным одна точка после другой.
2. Сделать узел после удаленной на одну точку предыдущей.

Если мы хотим удалить из SingleLinkedList (при условии, что мы уже НАШЛИ узел, который сильно отличается), что нам нужно сделать?

1. Сделать узел перед удаленным на одну точку, а после на следующий.

Можно подумать, это означает, что в одном связанном списке это даже быстрее, чем в двойном.

Но как мы делаем удаление узла, если у нас нет ссылки на предыдущий? У нас есть только ссылка на следующее. Разве нам не пришлось бы делать совсем другой поиск в списке, чтобы найти предысторию? : -О