Разница между списком <T>и LinkedList <T>

Question

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

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

Answer 1

Ну, List<T> в основном поддерживается массивом, который обычно больше, чем текущее количество элементов.Элементы помещаются в массив, и новый массив создается, когда у старого заканчивается свободное место.Это быстро для доступа по индексу, но медленно при удалении или вставке элементов в списке или в начале.Добавление / удаление записей в конце списка достаточно дешево.

LinkedList<T> - список с двойной связью - каждый узел знает свою предыдущую запись и свою следующую.Это быстро для вставки после / перед определенным узлом (или головой / хвостом), но медленно при доступе по индексу.

LinkedList<T> будет обычно займет больше памяти, чем List<T>потому что ему нужно место для всех этих следующих / предыдущих ссылок - и данные, вероятно, будут иметь меньшую локальность ссылок, поскольку каждый узел является отдельным объектом.С другой стороны, List<T> может иметь резервный массив, который намного больше, чем его текущие потребности.

Answer 2

A List<T> на самом деле является массивом, что означает, что его операция Add - это O (1) в конце и O (n) спереди, но вы можете индексировать его в O (1). LinkedList<T> - это, как говорится, связанный список. Поскольку он имеет двойную связь, вы можете добавлять элементы вперед или назад в O (1), но индексирование в нем - O (n).

Answer 3

Почти во всех сценариях List будет превосходить LinkedList.Реальные результаты часто отличаются от теории сложности Big O.