Преимущество связанного списка над списком

Question

Я читал во многих статьях, где упоминалось, что связанный список будет работать хорошо, когда мы должны выполнить вставку / удаление в середине коллекции. Но у меня есть сомнения здесь. Я изучаю структуру данных, пожалуйста, дайте мне знать, если мое понимание неверно.

Предположим, если у нас есть 10 элементов в списке

индекс: - 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

предметов: - A | Я | Z | S | J | T | V | J | A | T

И я хочу удалить элемент с индексом 6, что означает «V», а затем другие элементы мы должны сдвинуть на один уровень вверх. Я понимаю, что это изменение является дорогостоящей операцией, когда у нас очень большой список.

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

ПРИМЕР-

HeadNode A => D => Z => S => C => W => M => Q => E => T

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

Answer 1

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

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

Хорошим примером использования LinkedList будет кеш LRU - кеш состоит из словаря и связанного списка. Когда вы найдете элемент в словаре, вы переместитесь в начало списка. Если у элемента есть ссылка на его LinkedListNode, вы можете переместить его на передний план в постоянное время, независимо от того, в каком месте списка он был изначально.

В Java, которая не предоставляет класс узла, коллекция LinkedList в основном бесполезна.

Answer 2

Преимущество связанного списка в том, что элементы могут быть добавлены в него на неопределенный срок (зависит от доступной памяти), в то время как массив в конечном итоге будет заполнен или его размер будет изменен (дорогостоящая операция, которая не всегда возможна).

Связанные списки лучше всего подходят, когда общее количество элементов в списке неизвестно и произвольный доступ к элементам не требуется. Массивы больше подходят, когда у нас есть представление о верхнем пределе числа элементов в списке, и требуется произвольный доступ к элементам.

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