Listas, Colas, Pilas y Conjuntos en C# - Parte 2/6: LinkedList(T)

Índice

1. Introducción
2. Palabras Clave
3. Clase LinkedList<T>
3.1 Estructura
3.2 Inserción
3.3 Implementaciones
3.4 Ejemplo de uso
4. Conclusiones
5. Literatura & Enlaces

1. Introducción

Pasamos ahora estudiar otra estructura de datos o colección para la organización de piezas de datos en una lista doblemente enlazada: su característica distintiva es el doble enlace entre nodos -cada nodo conoce su antecesor y sucesor. Como ya veremos, la operación de inserción es mucho más eficiente aunque encontrar el lugar de inserción tome tiempo de procesador y espacio de memoria considerables.

2. Palabras Clave

• Colección
• Estructura de Datos
• Lista
• Lista doblemente enlazada

3. Clase LinkedList<T>

3.1 Estructura

Empecemos por ver una versión gráfica de la organización de un objeto de esta clase:

Figura 1. Organización gráfica clase LinkedList<T> (Albahari, 2012). 

Vemos que el objeto LinkedList está compuesto por dos campos que referencian el primer (First) y último (Last) elemento de la lista. Por otra parte, cada elemento de la lista está representado por un objeto LinkedListNode<T>; éste está integrado por tres partes fundamentales:

• Anterior (Previous)
• Siguiente (Next)
• Valor (Value)

Cada uno de estos campos son referencias a otros objetos LinkedListNode<T>. El valor (value) contiene la información concreta de cada nodo: alguna instancia de objeto que agrupa datos de una entidad del mundo del problema.

3.2 Inserción

La inserción entre nodos no cuenta con un mecanismo basado en índices. En su lugar, es necesario recorrer la estructura hasta encontrar el lugar concreto: esto puede ser indicando el o los valores de las entidades relacionadas con el punto de inserción.

La búsqueda binaria ("Búsqueda binaria", 2017), de acuerdo con Albahari (2012), no es posible llevarla a cabo a razón del argumento anterior: no existen índices para el acceso a elementos, y este tipo de algoritmo requiere ir reduciendo el área o campo de búsqueda por cada iteración o recursión.

3.3 Implementaciones

La clase LinkedList<T> implementa las interfaces para enumeración de elementos -IEnumerable<T>-, y operaciones comunes de colecciones con ICollection≶T> (Interfaces ICollection y IList en C# - Parte 2/2). Debido a que los elementos de un objeto de esta clase no permite manipulaciones a partir de índices, ésta no implementa la interfaz IList<T>.

3.4 Ejemplo de uso

Veamos una demostración de código sencilla de un objeto de esta clase. El código que viene a continuación es adaptado de Albahari (2012):

var notas = new LinkedList<string>();

notas.AddFirst("do");

notas.AddLast("so");

notas.AddAfter(notas.First, "re");

notas.AddAfter(notas.First.Next, "mi");

notas.AddBefore(notas.Last, "fa");

// Contenido: do re mi fa so

notas.RemoveFirst();

notas.RemoveLast();

// Contenido: re mi fa

LinkedListNode<string> nota = notas.Find("mi");

notas.Remove (nota);

notas.AddFirst (nota);

// Contenido: mi re fa

foreach(string n in notas){

    Console.WriteLine(n);

}

4. Conclusiones

Comprendimos el uso esencial de la clase genérica LinkedList<T>. Una estructura de datos que nos permite representar información que mantenga una relación lineal de antecesor/sucesor. Notamos que esta clase es especial: no usa un índice para manipular los elementos integrales.

En la tercera parte de esta serie nos centraremos en el estudio de dos clases de colección: Queue<T> y Queue.

5. Literatura & Enlaces

O