Почему LinkedList (T) не реализует интерфейс IList (T)?

Ответ 1

IList<T> интерфейс содержит указатель, индексатор не является функциональностью, которую вы ожидаете от LinkedList.

List<T> может гарантировать доступ к элементам в O (1), LinkedList по определению, которые она не может обеспечить доступ к элементам в O (1).

Ответ 2

См. определение связанного списка и вы поймете.

Основная проблема, LinkedLists может содержать циклические ссылки и, следовательно, не имеет индекса.

Связанные списки относятся к числу самых простых и наиболее распространенные структуры данных; Oни обеспечивают легкую реализацию для несколько важных абстрактных данных структуры, включая стеки, очереди, ассоциативные массивы и символические выражения.

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

С другой стороны, связанные списки по сами не допускают случайный доступ к данным или любой форме эффективного индексации. Таким образом, многие основные операции - например, получение последнего nodeсписок или найти node, что содержит заданную дату или местоположение место, где должен быть новый nodeвставка - может потребоваться большинство сканирования элементов списка.

Ответ 3

Существует три типа гарантии, предоставляемых интерфейсом, 1 программный и 2 концептуальных.

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

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

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

Люди привыкли работать с индексом IList, работающим достаточно быстро - O (1) или хуже, чем O (log n) - и нарушение этого концептуального обещания приведет к плохому использованию вашего объекта.

Здесь нет конкретного правила. Вы, безусловно, можете реализовать IList как связанный список и пострадать от индексированного get O (n). Вы также можете реализовать связанный список таким образом, чтобы он не сохранял запись своего счета (как это предоставил фреймворк) и имеет свойство O (n) Count. Но тогда люди чаще используют его плохо.

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

Ответ 4

LinkedList на самом деле является широко известной структурой данных списка, которая имеет следующую сложность работы:

Insertion: O(N)

Removal: O(1)

Indexing: O(N)

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

Insertion*: O(1)

Removal*: O(N)

Indexing: O(1)

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

Ответ 5

LinkedList не является списком. Списки представляют собой особые размерные коллекции объектов. LinkedList - это коллекция node, более близкая к словарю. Его потребности не похожи на обычный список, но более специализированы, чтобы допускать обход поведения node и организации.

Ответ 6

Поскольку доступ к связанному списку по индексу не является O (1).

Ответ 7

Связанный список не является структурой данных, которая предназначена для доступа по индексу, однако IList<T> предоставляет возможности доступа к индексу.

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

Ответ 8

"Список" - это термины структуры данных, которые не являются связанным списком; на самом деле массив - элемент списка напрямую доступен с помощью индексатора, который недоступен (не является практическим) в связанном списке.

Ответ 9

Историческая причуда: в .NET 1.1 ArrayList был классом, который действует как массив динамической длины.

В .NET 2+ по-прежнему List упорядочивает массив как массив. Это означает, что IList действительно ожидает семантики Array.

В .NET списки похожи на массивы, а не списки.... (boing)

Истинно связанные списки имеют постоянную вставку, удаление, но медленное перечисление и более медленный случайный доступ.

Массивы имеют быстрый список и произвольный доступ, но имеют дорогостоящую вставку/удаление (O (n) и перераспределение могут вкратце привести к совершенно другому поведению)

Ответ 10

Это тоже меня поразило... Традиционно список - это просто то, что вы можете зависеть от порядка элементов, и связанный список подчиняется этому, и он должен реализовывать IList, а не ICollection (коллекция не скажите что-нибудь о порядке своих элементов).

Не внедрять IList, потому что некоторые операции имеют меньшую сложность, чем то, что ожидали некоторые люди, по моему мнению, ошибочны.