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

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

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

Ответы

Ответ 1

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

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

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

Ответ 2

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