Является ли List <T> связанным списком?

Возможный дубликат:
Когда мне следует использовать список против LinkedList
Что представляет собой отличный ресурс для изучения деталей реализации общих коллекций .NET?

Является System.Collections.Generic.List<T> типом связанным списком (а не классом LinkedList<T>)?

A связанный список - это структура данных, состоящая из группы узлов, которые вместе представляют последовательность. В простейшей форме каждый node состоит из привязки и ссылки (другими словами, ссылки) к следующей node в последовательности.

Linear Linked List
Связанный список, узлы которого содержат два поля: целочисленное значение и ссылку на следующий node.
Последний node связан с терминатором, используемым для обозначения конца списка.

wikipedia.org

Если это так, какой у него связанный список?

Ответы

Ответ 1

Нет, List<T> поддерживается массивом - это, по существу, общая версия ArrayList из .NET 1.0. Из документов:

Класс List<T> является общим эквивалентом класса ArrayList. Он реализует общий интерфейс IList<T>, используя массив, размер которого динамически увеличивается по мере необходимости.

Обратите внимание, что из-за поддержки массивом его доступ через индексаторы равен O (1) в отличие от O (N) для связанного списка.

Если вы хотите связанный список, используйте LinkedList<T>. Обратите внимание, что это двусвязный список. Я не верю, что .NET предоставляет односвязный тип списка.

Ответ 2

List<T>, с технической точки зрения, НЕ тип связанного списка.

Если вы хотите иметь связанный список в С#:

  • используйте встроенный тип LinkedList<T> (для двусвязных списки)
  • или создать собственную реализацию (если вы хотите односвязный) - вот пример