Share
La primera estructura de datos que veremos es la lista enlazada, y con buena razón. Además de ser una estructura casi ubicua utilizada en todo, desde sistemas operativos hasta videojuegos, también es un bloque de construcción con el que se pueden crear muchas otras estructuras de datos..
En un sentido muy general, el propósito de una lista enlazada es proporcionar un mecanismo consistente para almacenar y acceder a una cantidad arbitraria de datos. Como su nombre lo indica, lo hace al vincular los datos en una lista.
Antes de profundizar en lo que esto significa, comencemos revisando cómo se almacenan los datos en una matriz.
Datos enteros almacenados en una matriz Como muestra la figura, los datos de la matriz se almacenan como una única porción de memoria asignada de forma contigua que está segmentada lógicamente. Los datos almacenados en la matriz se colocan en uno de estos segmentos y se referencian a través de su ubicación, o índice, en la matriz.
Esta es una buena manera de almacenar datos. La mayoría de los lenguajes de programación hacen que sea muy fácil asignar matrices y operar sobre sus contenidos. El almacenamiento de datos contiguos proporciona beneficios de rendimiento (a saber, la localidad de los datos), iterar sobre los datos es simple, y se puede acceder a los datos directamente por índice (acceso aleatorio) en tiempo constante.
Sin embargo, hay ocasiones en que una matriz no es la solución ideal..
Considere un programa con los siguientes requisitos:
Accentsconagua
SiguienteValor Método) hasta que se encuentre el número 0xFFFF.Artículos de proceso método.Dado que los requisitos indican que se deben pasar múltiples valores a la Artículos de proceso En una sola llamada, una solución obvia involucraría el uso de una matriz de enteros. Por ejemplo:
void LoadData () // Suponga que 20 es suficiente para mantener los valores. int [] valores = nuevo int [20]; para (int i = 0; i < values.Length; i++) if (values[i] == 0xFFFF) break; values[i] = NextValue(); ProcessItems(values); void ProcessItems(int[] values) //… Process data.
Esta solución tiene varios problemas, pero lo más evidente se ve cuando se leen más de 20 valores. Como el programa es ahora, los valores de 21 a n simplemente se ignoran. Esto podría mitigarse asignando más de 20 valores, quizás 200 o 2000. Tal vez el usuario podría configurar el tamaño, o tal vez si la matriz se llenara, se podría asignar una matriz más grande y todos los datos existentes se copiarían en ella. En última instancia, estas soluciones crean complejidad y desperdician memoria..
Lo que necesitamos es una colección que nos permita agregar un número arbitrario de valores enteros y luego enumerarlos en el orden en que se agregaron. La colección no debe tener un tamaño máximo fijo y la indexación de acceso aleatorio no es necesaria. Lo que necesitamos es una lista enlazada..
Antes de continuar y aprender cómo se diseña e implementa la estructura de datos de la lista enlazada, veamos cómo será nuestra solución definitiva..
static Void LoadItems () LinkedList list = new LinkedList (); while (true) int value = NextValue (); if (value! = 0xFFFF) list.Add (value); else break; ProcessItems (lista); ProcessItems estáticos no válidos (lista LinkedList) //… Datos de proceso.
Observe que ya no existen todos los problemas con la solución de matriz. Ya no hay problemas con la matriz que no es lo suficientemente grande o asigna más de lo necesario.
También debe notar que esta solución informa algunas de las decisiones de diseño que tomaremos más adelante, a saber, que Lista enlazada clase acepta un argumento de tipo genérico e implementa la Enumerable interfaz.
En el núcleo de la estructura de datos de la lista enlazada se encuentra la clase Node. Un nodo es un contenedor que proporciona la capacidad de almacenar datos y conectarse a otros nodos..
Un nodo de lista enlazada contiene datos y una propiedad que apunta al siguiente nodo. En su forma más simple, una clase de nodo que contiene enteros podría tener este aspecto:
Nodo de clase pública Valor de int público obtener; conjunto; Nodo público Siguiente obtener; conjunto;
Con esto ahora podemos crear una lista enlazada muy primitiva. En el siguiente ejemplo, asignaremos tres nodos (primero, medio y último) y luego los uniremos en una lista.
// + ----- + ------ + // | 3 | nulo + // + ----- + ------ + Nodo primero = Nuevo nodo Valor = 3; // + ----- + ------ + + ----- + ------ + // | 3 | nulo + | 5 | nulo + // + ----- + ------ + + ----- + ------ + Node middle = new Node Value = 5; // + ----- + ------ + + ----- + ------ + // | 3 | * --- + ---> | 5 | nulo + // + ----- + ------ + + ----- + ------ + first.Next = middle; // + ----- + ------ + + ----- + ------ + + ----- + ------ + // | 3 | * --- + ---> | 5 | nulo + | 7 | nulo + // + ----- + ------ + + ----- + ------ + + ----- + ------ + Último nodo = nuevo Nodo Valor = 7; // + ----- + ------ + + ----- + ------ + + ----- + ------ + // | 3 | * --- + ---> | 5 | * --- + -> | 7 | nulo + // + ----- + ------ + + ----- + ------ + + ----- + ------ + middle.Next = último;
Ahora tenemos una lista enlazada que comienza con el nodo primero y termina con el nodo último. los Siguiente La propiedad del último nodo apunta a nulo, que es el indicador de fin de lista. Dada esta lista, podemos realizar algunas operaciones básicas. Por ejemplo, el valor de cada nodo Datos propiedad:
Private Print void PrintList (nodo de nodo) while (node! = null) Console.WriteLine (node.Value); nodo = nodo.Siguiente;
los Lista de impresión El método funciona iterando sobre cada nodo de la lista, imprimiendo el valor del nodo actual y luego moviéndose al nodo al que apunta el Siguiente propiedad.
Ahora que entendemos cómo podría verse un nodo de lista enlazada, veamos la realidad LinkedListNode clase.
public class LinkedListNode /// /// Construye un nuevo nodo con el valor especificado. /// public LinkedListNode (valor T) Valor = valor; /// /// El valor del nodo. /// valor T público obtener; conjunto interno; /// /// El siguiente nodo en la lista vinculada (nulo si es el último nodo). /// public LinkedListNode Next get; conjunto interno;
Antes de implementar nuestro Lista enlazada clase, tenemos que pensar en lo que nos gustaría poder hacer con la lista.
Anteriormente vimos que la recopilación debe admitir datos fuertemente tipados, por lo que sabemos que queremos crear una interfaz genérica.
Ya que estamos utilizando .NET Framework para implementar la lista, tiene sentido que nos gustaría que esta clase pueda actuar como los otros tipos de colección incorporados. La forma más fácil de hacer esto es implementar el ICollection interfaz. Aviso que elijo ICollection y no IList. Esto es porque el IList interfaz agrega la capacidad de acceder a los valores por índice. Si bien la indexación directa es generalmente útil, no se puede implementar de manera eficiente en una lista vinculada.
Con estos requisitos en mente, podemos crear un código auxiliar de clase básico, y luego, a través del resto de la sección, podemos completar estos métodos..
clase pública LinkedList: System.Collections.Generic.ICollection public void Add (elemento T) arrojar nueva System.NotImplementedException (); Public void Clear () lanza el nuevo System.NotImplementedException (); public bool Contiene (elemento T) lanzar una nueva excepción System.NotImplementedException (); public void CopyTo (T [] array, int arrayIndex) lanzar la nueva excepción System.NotImplementedException (); public int Count get; conjunto privado public bool IsReadOnly get throw new System.NotImplementedException (); public bool Quitar (elemento T) lanzar nuevo System.NotImplementedException (); público System.Collections.Generic.IEnumerator GetEnumerator () lanza el nuevo System.NotImplementedException (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator () lanza el nuevo System.NotImplementedException ();
| Comportamiento | Agrega el valor proporcionado al final de la lista enlazada. |
| Actuación | O (1) |
Agregar un elemento a una lista vinculada implica tres pasos:
LinkedListNode ejemplo.Siguiente Propiedad del último nodo al nuevo nodo..La clave es saber qué nodo es el último nodo en la lista. Hay dos maneras en que podemos saber esto. La primera forma es hacer un seguimiento del primer nodo (el nodo "cabeza") y recorrer la lista hasta que hayamos encontrado el último nodo. Este enfoque no requiere que realicemos un seguimiento del último nodo, lo que guarda un valor de referencia de la memoria (sea cual sea el tamaño del puntero de su plataforma), pero requiere que realicemos un recorrido de la lista cada vez que se agregue un nodo. Esto haría Añadir una operación O (n).
El segundo enfoque requiere que mantengamos un registro del último nodo (el nodo "cola") en la lista y cuando agregamos el nuevo nodo, simplemente accedemos directamente a nuestra referencia almacenada. Este es un algoritmo O (1) y por lo tanto el enfoque preferido.
Lo primero que debemos hacer es agregar dos campos privados a la Lista enlazada clase: referencias a los nodos primero (cabeza) y último (cola).
LinkedListNode _head privado; LinkedListNode privado _tail;
A continuación necesitamos agregar el método que realiza los tres pasos..
Public void Add (valor T) LinkedListNode node = new LinkedListNode (value); if (_head == null) _head = node; _tail = nodo; else _tail.Next = nodo; _tail = nodo; Count ++;
En primer lugar, asigna la nueva LinkedListNode ejemplo. A continuación, comprueba si la lista está vacía. Si la lista está vacía, el nuevo nodo se agrega simplemente asignando el _cabeza y _cola Referencias al nuevo nodo. El nuevo nodo es ahora el primer y el último nodo de la lista. Si la lista no está vacía, el nodo se agrega al final de la lista y el _cola La referencia se actualiza para indicar el nuevo final de la lista..
los Contar la propiedad se incrementa cuando se agrega un nodo para asegurar la ICollection. Contar propiedad devuelve el valor exacto.
| Comportamiento | Elimina el primer nodo de la lista cuyo valor es igual al valor proporcionado. El método devuelve true si se eliminó un valor. De lo contrario, devuelve falso.. |
| Actuación | En) |
Antes de hablar de la retirar Algoritmo, echemos un vistazo a lo que está tratando de lograr. En la siguiente figura, hay cuatro nodos en una lista. Queremos eliminar el nodo con el valor tres..
Una lista enlazada con cuatro valores. Cuando se haya completado la eliminación, la lista se modificará de tal manera que la Siguiente propiedad en el nodo con el valor dos puntos al nodo con el valor cuatro.
La lista enlazada con el nodo 3 eliminado El algoritmo básico para la eliminación de nodos es:
Como siempre, el diablo está en los detalles. Hay algunos casos en los que debemos pensar al eliminar un nodo:
_cabeza y _cola campos a nulo._cabeza campo para apuntar al nuevo nodo principal._cola campo para hacer referencia al penúltimo nodo en la lista y establecer su Siguiente propiedad a nulo.public bool Remove (T item) LinkedListNode previous = null; LinkedListNode current = _head; // 1: Lista vacía: No hacer nada. // 2: nodo único: el anterior es nulo. // 3: Muchos nodos: // a: El nodo a eliminar es el primer nodo. // b: El nodo a eliminar es el medio o el último. while (current! = null) if (current.Value.Equals (item)) // Es un nodo en el medio o final. if (anterior! = nulo) // Caso 3b. // Antes: Head -> 3 -> 5 -> null // Después: Head -> 3 ------> null previous.Next = current.Next; // Fue el final, así que actualiza _tail. if (current.Next == null) _tail = previous; else else // Caso 2 o 3a. // Antes: Head -> 3 -> 5 // Después: Head ------> 5 // Head -> 3 -> null // Head ------> null _head = _head.Next; // ¿Está la lista ahora vacía? if (_head == null) _tail = null; Cuenta--; devuelve verdadero anterior = actual; actual = actual.Siguiente; falso retorno;
los Contar la propiedad disminuye cuando se elimina un nodo para garantizar la ICollection. Contar propiedad devuelve el valor exacto.
| Comportamiento | Devuelve un valor booleano que indica si el valor proporcionado existe dentro de la lista vinculada. |
| Actuación | En) |
los Contiene El método es bastante simple. Examina todos los nodos de la lista, de primero a último, y devuelve verdadero tan pronto como se encuentra un nodo que coincide con el parámetro. Si se llega al final de la lista y no se encuentra el nodo, el método devuelve falso.
public bool Contiene (elemento T) LinkedListNode current = _head; while (current! = null) if (current.Value.Equals (item)) return true; actual = actual.Siguiente; falso retorno;
| Comportamiento | Devuelve una instancia de IEnumerator que permite enumerar los valores de la lista enlazada de primero a último. |
| Actuación | Devolver la instancia del enumerador es una operación O (1). Enumerar cada elemento es una operación O (n). |
GetEnumerator se implementa al enumerar la lista desde el primer al último nodo y usa C # rendimiento palabra clave para devolver el valor del nodo actual a la persona que llama.
Observe que LinkedList implementa el comportamiento de iteración en el Enumerable versión del método GetEnumerator y difiere a este comportamiento en la versión IEnumerable.
IEnumerator IEnumerable.GetEnumerator () LinkedListNode current = _head; while (current! = null) rendimiento return current.Value; actual = actual.Siguiente; IEnumerator IEnumerable.GetEnumerator () return ((IEnumerable) this) .GetEnumerator ();
| Comportamiento | Elimina todos los elementos de la lista. |
| Actuación | O (1) |
los Claro método simplemente establece el _cabeza y _cola campos a nulo para borrar la lista. Debido a que .NET es un lenguaje de recolección de basura, los nodos no necesitan ser eliminados explícitamente. Es responsabilidad del llamante, no de la lista enlazada, asegurarse de que si los nodos contienen IDisponible Referencias de las que se disponen adecuadamente..
public void Clear () _head = null; _tail = nulo; Cuenta = 0;
| Comportamiento | Copia el contenido de la lista enlazada de principio a fin en la matriz proporcionada, comenzando en el índice de matriz especificado. |
| Actuación | En) |
los Copiar a el método simplemente itera sobre los elementos de la lista y usa una asignación simple para copiar los elementos a la matriz. Es responsabilidad de la persona que llama asegurarse de que la matriz de destino contenga el espacio libre adecuado para acomodar todos los elementos de la lista.
public void CopyTo (T [] array, int arrayIndex) LinkedListNode current = _head; while (current! = null) array [arrayIndex ++] = current.Value; actual = actual.Siguiente;
| Comportamiento | Devuelve un entero que indica el número de elementos que se encuentran actualmente en la lista. Cuando la lista está vacía, el valor devuelto es 0. |
| Actuación | O (1) |
Contar es simplemente una propiedad implementada automáticamente con un captador público y un configurador privado. El comportamiento real ocurre en el Añadir, retirar, y Claro metodos.
public int Count get; conjunto privado
| Comportamiento | Devuelve false si la lista no es de solo lectura. |
| Actuación | O (1) |
public bool IsReadOnly get return false;
La clase LinkedList que acabamos de crear se conoce como una lista enlazada individualmente. Esto significa que existe un solo enlace unidireccional entre un nodo y el siguiente nodo en la lista. Hay una variación común de la lista enlazada que permite a la persona que llama acceder a la lista desde ambos extremos. Esta variación es conocida como una lista doblemente enlazada..
Para crear una lista doblemente enlazada, primero debemos modificar nuestra clase LinkedListNode para tener una nueva propiedad llamada Previous. Anterior actuará como siguiente, solo que apuntará al nodo anterior en la lista.
Una lista doblemente enlazada usando una propiedad de nodo anterior Las siguientes secciones solo describirán los cambios entre la lista de enlaces individuales y la nueva lista de enlaces dobles.
El único cambio que se hará en el LinkedListNode clase es la adición de una nueva propiedad llamada Anterior lo que apunta a lo anterior LinkedListNode en la lista enlazada, o devuelve nulo Si es el primer nodo de la lista..
public class LinkedListNode /// /// Construye un nuevo nodo con el valor especificado. /// /// public LinkedListNode (valor T) Valor = valor; /// /// El valor del nodo. /// valor T público obtener; conjunto interno; /// /// El siguiente nodo en la lista vinculada (nulo si es el último nodo). /// public LinkedListNode Next get; conjunto interno; /// /// El nodo anterior en la lista enlazada (nulo si es el primer nodo). /// public LinkedListNode Anterior get; conjunto interno;
Mientras que la lista enlazada individualmente solo agregó nodos al final de la lista, la lista doblemente enlazada permitirá agregar nodos al inicio y al final de la lista usando AddFirst y AddLast, respectivamente. los ICollection. Añadir método diferirá a la AddLast Método para mantener la compatibilidad con el enlace individual Lista clase.
| Comportamiento | Agrega el valor provisto al frente de la lista. |
| Actuación | O (1) |
Al agregar un nodo al principio de la lista, las acciones son muy similares a las de agregar a una lista enlazada individualmente.
Siguiente Propiedad del nuevo nodo al antiguo nodo principal..Anterior Propiedad del nodo principal anterior al nuevo nodo.._cola campo (si es necesario) e incremento Contar.public void AddFirst (valor T) LinkedListNode node = new LinkedListNode (value); // Guarda el nodo principal para que no lo perdamos. LinkedListNode temp = _head; // Dirigir la cabeza al nuevo nodo. _head = nodo; // Insertar el resto de la lista detrás de la cabeza. _head.Next = temp; if (Count == 0) // Si la lista estaba vacía, la cabeza y la cola // deberían apuntar al nuevo nodo. _tail = _head; else // Antes: cabeza -------> 5 <-> 7 -> nulo // Después: cabeza -> 3 <-> 5 <-> 7 -> null temp.Previous = _head; Count ++;
| Comportamiento | Agrega el valor provisto al final de la lista.. |
| Actuación | O (1) |
Agregar un nodo al final de la lista es incluso más fácil que agregar uno al inicio.
El nuevo nodo simplemente se agrega al final de la lista, actualizando el estado de _cola y _cabeza como sea apropiado, y Contar se incrementa.
public Void AddLast (valor T) LinkedListNode node = new LinkedListNode (value); if (Count == 0) _head = node; else _tail.Next = nodo; // Antes: Jefe -> 3 <-> 5 -> nulo // Después: Cabeza -> 3 <-> 5 <-> 7 -> null // 7.Previous = 5 node.Previous = _tail; _tail = nodo; Cuenta ++;
Y como se mencionó anteriormente, ICollection.Agregar ahora simplemente llamará AddLast.
Public void Add (valor T) AddLast (value);
Me gusta Añadir, la retirar El método se ampliará para admitir la eliminación de nodos desde el principio o el final de la lista. los ICollection.El método de eliminación continuará eliminando elementos desde el principio, con el único cambio de actualizar el apropiado Anterior propiedad.
| Comportamiento | Elimina el primer valor de la lista. Si la lista está vacía, no se realiza ninguna acción. Devuelve true si se quitó un valor. De lo contrario, devuelve falso.. |
| Actuación | O (1) |
Quitar primero actualiza la lista configurando la lista enlazada cabeza propiedad al segundo nodo en la lista y actualizando su Anterior propiedad a nulo. Esto elimina todas las referencias al nodo principal anterior, eliminándolo de la lista. Si la lista contenía solo un singleton, o estaba vacía, la lista estará vacía (el cabeza y cola propiedades serán nulo).
public void RemoveFirst () if (Count! = 0) // Before: Head -> 3 <-> 5 // Después: Head -------> 5 // Head -> 3 -> null // Head ------> null _head = _head.Next; Contar--; if (Count == 0) _tail = null; else // 5.Previous era 3; ahora es nulo _head.Previous = null;
| Comportamiento | Elimina el último nodo de la lista. Si la lista está vacía, no se realiza ninguna acción. Devuelve true si se quitó un valor. De lo contrario, devuelve falso.. |
| Actuación | O (1) |
EliminarLast funciona estableciendo la lista de cola La propiedad será el nodo que precede al nodo de cola actual. Esto elimina el último nodo de la lista. Si la lista estaba vacía o solo tenía un nodo, cuando el método devuelve el cabeza y cola propiedades, ambos serán nulo.
public void RemoveLast () if (Count! = 0) if (Count == 1) _head = null; _tail = nulo; else // Before: Head -> 3 -> 5 -> 7 // Tail = 7 // After: Head -> 3 -> 5 -> null // Tail = 5 // Null la propiedad siguiente de 5 de. _tail.Previous.Next = null; _tail = _tail.Previous; Cuenta--;
| Comportamiento | Elimina el primer nodo de la lista cuyo valor es igual al valor proporcionado. El método devuelve true si se eliminó un valor. De lo contrario, devuelve falso.. |
| Actuación | En) |
los ICollection. retirar El método es casi idéntico a la versión enlazada individualmente, excepto que la Anterior La propiedad ahora se actualiza durante la operación de eliminación. Para evitar código repetido, el método llama. Quitar primero cuando se determina que el nodo que se está eliminando es el primer nodo de la lista.
public bool Remove (T item) LinkedListNode previous = null; LinkedListNode current = _head; // 1: Lista vacía: No hacer nada. // 2: nodo único: el anterior es nulo. // 3: Muchos nodos: // a: El nodo a eliminar es el primer nodo. // b: El nodo a eliminar es el medio o el último. while (current! = null) // Head -> 3 -> 5 -> 7 -> null // Head -> 3 ------> 7 -> null if (current.Value.Equals (item) ) // Es un nodo en el medio o final. if (anterior! = nulo) // Caso 3b. previous.Next = current.Next; // Fue el final, así que actualiza _tail. if (current.Next == null) _tail = previous; else // Antes: Jefe -> 3 <-> 5 <-> 7 -> nulo // Después: Cabeza -> 3 <-------> 7 -> null // anterior = 3 // actual = 5 // actual.Siguiente = 7 // Entonces… 7.Anterior = 3 actual.Siguiente.Previsto = anterior; Cuenta--; else // Caso 2 o 3a. RemoveFirst (); devuelve true; anterior = actual; actual = actual.Siguiente; falso retorno;
Podemos agregar nodos al principio y al final de la lista, ¿y qué? ¿Por qué nos importa? Tal como está ahora, el doblemente vinculado Lista La clase no es más poderosa que la lista enlazada individualmente. Pero con solo una modificación menor, podemos abrir todo tipo de comportamientos posibles. Al exponer el cabeza y cola propiedades como propiedades públicas de solo lectura, el consumidor de listas vinculadas podrá implementar todo tipo de nuevos comportamientos.
cabeza de LinkedListNode público obtener volver _head; public LinkedListNode Tail get return _tail;
Con este simple cambio podemos enumerar la lista manualmente, lo que nos permite realizar una enumeración inversa (cola a cabeza) y buscar.
Por ejemplo, el siguiente ejemplo de código muestra cómo usar la lista Cola y Anterior Propiedades para enumerar la lista a la inversa y realizar algún procesamiento en cada nodo..
public void ProcessListBackwards () LinkedList list = new LinkedList (); PopulateList (lista); LinkedListNode current = list.Tail; while (actual! = nulo) ProcessNode (actual); actual = actual.Anterior;
Adicionalmente, el doblemente enlazado. Lista clase nos permite crear fácilmente la Deque clase, que es en sí misma un bloque de construcción para otras clases. Discutiremos esta clase más adelante en otra sección..
