2010-08-27 18 views
23

En C#, la clase LinkedList (T) no implementa la interfaz IList (T). Sin embargo, la clase List (T) implementa IList (T). ¿Por qué hay esta discrepancia? Funcionalmente, ambas son listas, por lo que esta elección de diseño parece extraña. Ahora se vuelve difícil cambiar las implementaciones de List (T) a LinkedList (T).¿Por qué LinkedList (T) no implementa la interfaz IList (T)?

+0

'LinkedList ' ofrece una inserción más rápida y elimina operaciones en comparación con 'List ', al mismo tiempo no ofrece operaciones de índice. Es una transacción de 'LinkedList 'hace para obtener la inserción y eliminar más rápido. Lo mismo vale para 'List ' en la dirección opuesta. – nawfal

Respuesta

26

IList<T> interfaz contiene un indexador, el indizador no es una funcionalidad que se puede esperar en un LinkedList.

List<T> puede asegurar el acceso a los elementos en O (1), LinkedList por definición de la misma es que la estructura no puede proporcionar acceso a los artículos en O (1).

+2

Gracias a todos por sus respuestas. Pasé por alto que la definición de IList es "Representa una colección de objetos a los que se puede acceder individualmente por índice". No coincide con mi idea de una lista, pero bueno, es su lenguaje, pueden elegir las definiciones. Muchas personas han afirmado que las listas vinculadas no pueden admitir la indexación, sin embargo, la lista vinculada del lenguaje Java sí tiene índices (su documentación no reclama su eficacia en el tiempo). –

+0

Me topé con este problema una vez, y terminé creando mi propia clase IndexedLinkedList (sí, suena estúpido, pero era la mejor opción). Es bueno hacer un seguimiento de las diferencias. – NickAldwin

+4

Tenga en cuenta que [garantizar el acceso de un elemento en la lista en el tiempo O (1) es una promesa que hace la * implementación * ('List ')] (http://msdn.microsoft.com/en-us/ library/0ebtbkkc.aspx), [* no * es un requisito del * contrato * ('IList ')] (http://msdn.microsoft.com/en-us/library/ewthkb10.aspx). Su respuesta es incorrecta, ya que el acceso indexado * puede * realizarse al recorrer la lista enlazada. Por supuesto, hacer esto no será tan eficiente para el caso general, tomando O (N) el tiempo. – casperOne

10

Consulte la definición de linked list, y usted comprenderá.

Problema principal, LinkedLists puede contener referencias circulares, y por lo tanto no tiene un índice.

Las listas vinculadas se encuentran entre las más simples y las estructuras de datos más comunes; ellos proporcionan una implementación fácil para varias estructuras de datos abstractos importantes , incluyendo pilas, colas, matrices asociativas y expresiones simbólicas.

El principal beneficio de una lista enlazada sobre una matriz convencional es que el orden de los elementos vinculados puede ser diferente del orden que los datos elementos se almacenan en la memoria o en el disco. Por esa razón, las listas vinculadas permiten la inserción y la eliminación de nodos en cualquier punto de la lista, con un número constante de operaciones .

Por otro lado, las listas enlazadas por mismos no permiten el acceso aleatorio a los datos , o cualquier forma de indexación eficiente . Por lo tanto, muchas de las operaciones básicas - tales como obtener el último nodo de la lista, o la búsqueda de un nodo que contiene un dato determinado, o localizar el lugar donde un nodo nuevo debe ser insertados - puede requerir de escaneo más de la elementos de lista.

+0

No estoy de acuerdo con la idea de que sean las estructuras de datos más simples * o * más comunes. Son una molestia para implementar por su cuenta, y tienen todo tipo de problemas que tiene que tener en cuenta. Y apenas los veo implementados. Las pilas se usan frecuentemente y son muy fáciles de implementar por otro lado. –

+3

Pero eso no impide el acceso por índice. Si define el indexador de modo que cada "salto" sucesivo en la lista disminuya el índice, entonces tendría un indexador. Un indexador muy ineficiente, pero un indexador. Por lo tanto, creo que los indexadores no se implementan en una lista vinculada para evitar que se pegue un tiro en el pie, al igual que no son compatibles directamente con 'IEnumerable '. –

+0

Bueno, la idea es bastante simple, ¿no? Deje que cada nodo se vincule con su neightbor, y usted mismo tiene una lista :). Sobre lo más común estoy de acuerdo: ¡nunca uso LinkedLists! – Arcturus

0

Porque el acceso a una lista vinculada por índice no es O (1).

0

Una lista vinculada no es una estructura de datos diseñada para ser accedida por índice, sin embargo, IList<T> proporciona capacidades de acceso de índice.

Por lo tanto, como no puede acceder a los elementos de una lista vinculada por índice, no puede proporcionar métodos que intenten hacerlo.

0

Una "Lista" es términos de estructura de datos es no una lista vinculada; en realidad es una matriz. Se puede acceder directamente a la lista de elementos, utilizando el indexador, que no está disponible (no es práctico) en una lista vinculada.

1

LinkedList no es una lista. Las listas son colecciones dimensionales singulares de objetos. Una LinkedList es una colección de nodos, más estrechamente alineada con un Diccionario.Sus necesidades no son similares a las de una lista común, sino que son más especializadas para permitir el cruce de nodos y los comportamientos de organización.

2

LinkedList es en realidad una estructura de datos de la lista ampliamente conocido que tiene después de la complejidad de la operación:

Insertion: O(N) 

Removal: O(1) 

Indexing: O(N) 

Mientras que la lista es una matriz continua, que tiene las siguientes complejidad del algoritmo:

Insertion*: O(1) 

Removal*: O(N) 

Indexing: O(1) 

Ellos no lo hacen proporciona la interfaz común, ya que desviará a los usuarios de la interfaz y hará que la eficacia de los programas sea impredecible. Para obtener más información, consulte libros sobre algoritmos y estructuras de datos.

+2

La inserción es O (N) para listas. – Jason

+0

sí, @Jason tiene razón, la inserción es O (N) - de hecho se amortiza O (N). Anexar se amortiza O (1). Curiosamente, la inserción en el índice es O (N) para una lista vinculada pero O (N) amortizado para List. –

+0

Empiezo preguntando que "misma interfaz" significa la misma función Y la misma complejidad de cómputo? – Gqqnbig

3

Existen tres tipos de garantía otorgadas por una interfaz, 1 programática y 2 conceptual.

La garantía programática es que puede llamar a un método o propiedad que exista. .NET hace cumplir esta garantía.

La primera garantía conceptual es que funcionará. Esto a menudo se rompe (existen NotImplementedException y NotSupportedException precisamente para romper esto) pero debería haber una buena razón para hacer esto. Aún así, es más una promesa que una garantía.

La segunda garantía conceptual es también más una promesa que una garantía, que el método o la propiedad funcionarán de manera muy similar a otros casos.

La gente está acostumbrada a que el indexador de IList trabaje a un ritmo razonablemente rápido - O (1) o peor con O (log n) - y romper esa promesa conceptual hará que las personas usen mal su objeto.

No hay una regla concreta aquí. Ciertamente puede implementar IList como una lista enlazada, y sufrir el O (n) indexado get. También puede implementar una lista vinculada de tal manera que no conserve un registro de su recuento (como la que proporciona el marco) y que tenga una propiedad O (n) Count. Pero entonces es más probable que las personas lo usen mal.

Parte del diseño de componentes no es solo asegurarse de que las cosas funcionen y funcionen bien, sino guiar su uso. Una lista enlazada que implemente IList fallaría en el último punto, y por lo tanto uno podría argumentar fuertemente que no sería un diseño tan bueno como el ofrecido.

+0

Gracias por su respuesta detallada. Podría hablar de diseño todo el día. Hice una comparación con Java anteriormente y mencioné que las listas enlazadas de Java admiten índices. Parece que la diferencia clave es que el indexador en .NET es una propiedad y, en general, no se espera que las propiedades hagan cálculos largos. Java no tiene propiedades ni obedece sus convenciones, por lo que su indexador de lista enlazado probablemente se ejecute en O (n). Lástima ... sería bueno cambiar la implementación de mi lista según lo que pensé que era más eficiente para el trabajo; más fácil de hacer si comparten la interfaz IList. –

+0

No hay nada que te impida incluir una lista enlazada en algo que sea compatible con IList, aunque no estaría de acuerdo porque estoy de acuerdo con el razonamiento que lo respalda y no con el respaldo de manera predeterminada. Del mismo modo, si LinkedList realmente es más eficiente para un trabajo, es probable que sea un trabajo que se realiza mejor sin el uso de IList. –

0

peculiaridad histórica: en .NET 1.1 una ArrayList era la clase que actúa como una matriz de longitud dinámica.

En .NET 2+ aún, la lista se organiza internamente como una matriz. Esto significa que IList espera la semántica Array, realmente.

En .NET, las listas son como arrays, no listas .... (boing)

listas enlazadas verdaderos tienen inserción constante de tiempo, eliminación, pero enumeración lento y más lento el acceso aleatorio.

matrices tienen la enumeración rápida y de acceso aleatorio, pero tienen costosa inserción/deleción (O (n) y la reasignación puede conducir rapidamente a un comportamiento completamente diferente)

-1

Esto me tomó por sorpresa, así .. Tradicionalmente, una lista es solo algo en lo que puedes depender del orden de los elementos, y una lista enlazada obedece a esto, y debe implementar IList en lugar de ICollection (una colección no dice nada sobre el orden de sus elementos).

No implementando IList porque algunas operaciones tienen una complejidad menor de lo que algunas personas esperarían, está mal en mi opinión.

Cuestiones relacionadas