Listas Enlazadas - Algoritmos y Programación II

Las listas enlazadas son estructuras de datos que permiten almacenar una colección de elementos en posiciones de memoria no necesariamente contiguas. Cada elemento se guarda en un nodo que contiene un campo de dato y uno o dos punteros a otros nodos. Los nodos se enlazan entre sí para formar la secuencia.

Son estructuras dinámicas: pueden crecer a medida que se agregan datos y reducirse cuando se eliminan. A diferencia de los arreglos, no requieren bloques contiguos de memoria ni reasignaciones costosas al cambiar de tamaño.

Algunos usos frecuentes:

Algoritmos de manipulación de texto: Las listas enlazadas son útiles en procesamiento de texto, donde la inserción y eliminación de caracteres o líneas se realizan con frecuencia. Cada línea del documento puede ser un nodo; insertar o borrar una línea solo requiere reenlazar punteros, sin desplazar el resto del contenido.
Undo y redo en aplicaciones: Las listas enlazadas dobles permiten navegar hacia adelante y atrás en el historial de acciones. Cada acción es un nodo; la doble vinculación permite moverse en ambas direcciones en tiempo constante.
Listas de reproducción: Una lista circular permite reproducir canciones en ciclo infinito. Al llegar al final, se vuelve al principio sin necesidad de reiniciar manualmente. Algunas implementaciones combinan listas dobles (para avanzar/retroceder) con comportamiento circular (para repetición continua).

Existen cuatro variantes principales de listas enlazadas, que se diferencian en la cantidad de punteros por nodo, cómo se marcan los extremos y cómo se recorren. Cada variante tiene fortalezas y debilidades según la operación que se quiera optimizar.

1Lista Enlazada Simple¶

1
2
3
4
type node[T any] struct {
    data T
    next *node[T]
}

1
2
3
4
5
type List[T comparable] struct {
    head *node[T]
    tail *node[T]
    size int
}

Notar que el nodo se parametriza con [T any] porque solo almacena y enlaza datos, sin necesidad de compararlos. La lista, en cambio, usa [T comparable], ya que, como veremos a continuación, algunas operaciones necesitan comparar elementos con == para encontrar un dato buscado.

Cuando una operación como Head() o Tail() se ejecuta sobre una lista vacía, debe devolver el valor cero del tipo T (no nil, que solo es válido para punteros, slices, maps y canales). En Go, el valor cero se obtiene con var zero T:

1
2
3
4
5
6
7
8
var zero T
/*
    0       para int
    0.0     para float
    ""      para string
    false   para bool
    nil     para punteros, slices, maps y canales
*/

2Lista Enlazada Doble¶

1
2
3
4
5
type node[T any] struct {
    data T
    next *node[T]
    prev *node[T]
}

1
2
3
4
5
type List[T comparable] struct {
    head *node[T]
    tail *node[T]
    size int
}

3Lista Enlazada Circular¶

Al ser cíclica, basta con mantener un único puntero a la cabeza: la cola se obtiene como head.prev. Esto ahorra un campo en la estructura.

1
2
3
4
type List[T comparable] struct {
    head *node[T]  // único puntero necesario
    size int
}

4Interfaz común¶

Si bien las listas son versátiles y no existe un único comportamiento estándar para todas, vamos a definir una interfaz común para los tipos de lista que veremos a continuación. El objetivo es didáctico: acordar un conjunto de operaciones típicas que nos permita comparar implementaciones.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
type List[T comparable] interface {
    // Consulta
    Size() int
    IsEmpty() bool
    Contains(data T) bool
    Head() (T, bool)
    Tail() (T, bool)

    // Inserción
    Prepend(data T)
    Append(data T)
    InsertAfter(target, data T) bool
    InsertBefore(target, data T) bool

    // Eliminación
    RemoveFirst() bool
    RemoveLast() bool
    Remove(data T) bool

    // Recorrido
    Values() []T

    // Utilidad
    Clear()
    String() string
}

La mayoría de las operaciones de inserción, eliminación y búsqueda dependen de un método interno find que recorre la lista en busca de un elemento. Este método es privado (en Go, minúscula inicial) porque devuelve un puntero a un nodo interno, y no debería exponerse fuera de la lista. A continuación se muestra su implementación en cada variante; las operaciones del resto de la sección lo referencian.

Simple

Doble

Circular

find(buscado):
    actual := head
    mientras actual != nil:
        si actual.dato == buscado:
            retornar actual
        actual = actual.siguiente
    retornar nil

find — Lista Simple

find(buscado):
    si IsEmpty():
        retornar nil
    actual := head
    para i := 0; i < Size(); i++:
        si actual.dato == buscado:
            retornar actual
        actual = actual.siguiente
    retornar nil

find — Lista Circular

4.1Consulta¶

Size(): Devuelve la cantidad de nodos de la lista.

Simple

Doble

Circular

Size():
    retornar size

Size — Lista Simple

IsEmpty(): Devuelve true si la lista no tiene elementos.

Simple

Doble

Circular

IsEmpty():
    retornar size == 0

IsEmpty — Lista Simple

Contains(data T): Devuelve true si el elemento está presente (solo la primera ocurrencia).

Simple

Doble

Circular

Contains(buscado):
    retornar find(buscado) != nil

Contains — Lista Simple

Head(): Devuelve el dato del primer nodo. Si la lista está vacía devuelve el valor cero y false.

Simple

Doble

Circular

Head():
    si IsEmpty():
        retornar zero, falso  // lista vacía: no hay primer dato
    retornar head.dato, verdadero

Head — Lista Simple

Tail(): Devuelve el dato del último nodo. En la lista circular se obtiene desde head.prev.

Simple

Doble

Circular

Tail():
    si IsEmpty():
        retornar zero, falso  // lista vacía: no hay último dato
    retornar tail.dato, verdadero

Tail — Lista Simple

4.2Inserción¶

Prepend(data T): Agrega un nodo con el dato al inicio de la lista.

Simple

Doble

Circular

Prepend(dato):
    nuevo := nuevoNodo(dato)
    nuevo.siguiente = head  // apunta al que era el primer nodo
    head = nuevo            // el nuevo pasa a ser el primer nodo
    si IsEmpty():
        tail = nuevo  // si estaba vacía, el nuevo también es la cola
    tamaño++

Prepend — Lista Simple

Prepend(dato):
    nuevo := nuevoNodo(dato)
    nuevo.siguiente = head  // apunta al que era el primer nodo
    si IsEmpty():
        tail = nuevo  // si estaba vacía, el nuevo también es la cola
    sino:
        head.prev = nuevo  // el nodo anterior enlaza su prev al nuevo
    head = nuevo  // el nuevo pasa a ser el primer nodo
    tamaño++

Prepend — Lista Doble

Prepend(dato):
    nuevo := nuevoNodo(dato)
    si IsEmpty():
        nuevo.siguiente = nuevo  // lista de un solo nodo: se apunta a sí mismo
        nuevo.prev = nuevo
    sino:
        cola := head.prev
        nuevo.siguiente = head
        nuevo.prev = cola
        head.prev = nuevo
        cola.siguiente = nuevo  // cierra el ciclo entre cola y el nuevo head
    head = nuevo
    tamaño++

Prepend — Lista Circular

La lista simple solo actualiza head y tail en caso de lista vacía. La doble además debe enlazar prev del head anterior. La circular requiere mantener el ciclo, enlazando el nuevo nodo con head y con la cola (head.prev).

Append(data T): Agrega un nodo con el dato al final de la lista.

Simple

Doble

Circular

Append(dato):
    nuevo := nuevoNodo(dato)
    si IsEmpty():
        head = nuevo  // el primer nodo de la lista
    sino:
        tail.siguiente = nuevo  // se encadena tras la cola actual
    tail = nuevo  // en ambos casos el nuevo pasa a ser la cola
    tamaño++

Append — Lista Simple

Append(dato):
    nuevo := nuevoNodo(dato)
    nuevo.prev = tail  // apunta al que era la cola
    si IsEmpty():
        head = nuevo  // el primer nodo de la lista
    sino:
        tail.siguiente = nuevo  // se encadena tras la cola actual
    tail = nuevo  // en ambos casos el nuevo pasa a ser la cola
    tamaño++

Append — Lista Doble

Append(dato):
    si IsEmpty():
        Prepend(dato)  // reutiliza el caso de lista con un solo nodo
        retornar
    cola := head.prev
    nuevo := nuevoNodo(dato)
    nuevo.prev = cola  // el nuevo va entre la cola y head
    nuevo.siguiente = head
    cola.siguiente = nuevo
    head.prev = nuevo  // queda enlazado en ambos extremos del ciclo
    tamaño++

Append — Lista Circular

InsertAfter(target, data T): Busca target e inserta un nodo con data a continuación. Devuelve false si no encuentra target.

Simple

Doble

Circular

InsertAfter(buscado, dato):
    actual := find(buscado)
    si actual == nil:
        retornar falso  // target no encontrado
    nuevo := nuevoNodo(dato)
    nuevo.siguiente = actual.siguiente  // el nuevo apunta al sucesor de actual
    actual.siguiente = nuevo  // actual pasa a apuntar al nuevo
    si actual == tail:
        tail = nuevo  // si inserté al final, el nuevo es la nueva cola
    tamaño++
    retornar verdadero

InsertAfter — Lista Simple

InsertAfter(buscado, dato):
    actual := find(buscado)
    si actual == nil:
        retornar falso  // target no encontrado
    nuevo := nuevoNodo(dato)
    nuevo.siguiente = actual.siguiente
    nuevo.prev = actual
    si actual == tail:
        tail = nuevo  // si inserté al final, el nuevo es la nueva cola
    sino:
        nuevo.siguiente.prev = nuevo  // el sucesor enlaza su prev al nuevo
    actual.siguiente = nuevo  // actual pasa a apuntar al nuevo
    tamaño++
    retornar verdadero

InsertAfter — Lista Doble

InsertAfter(buscado, dato):
    actual := find(buscado)
    si actual == nil:
        retornar falso  // target no encontrado
    nuevo := nuevoNodo(dato)
    nuevo.siguiente = actual.siguiente
    nuevo.prev = actual
    actual.siguiente.prev = nuevo  // el sucesor enlaza su prev al nuevo
    actual.siguiente = nuevo  // actual pasa a apuntar al nuevo
    tamaño++
    retornar verdadero

InsertAfter — Lista Circular

InsertBefore(target, data T): Busca target e inserta un nodo con data antes. Devuelve false si no encuentra target.

Simple

Doble

Circular

InsertBefore(buscado, dato):
    si IsEmpty():
        retornar falso  // no hay nada ante qué insertar
    si head.dato == buscado:
        Prepend(dato)  // insertar antes del primer nodo es un prepend
        retornar verdadero
    actual := head
    mientras actual.siguiente != nil:
        si actual.siguiente.dato == buscado:
            nuevo := nuevoNodo(dato)
            nuevo.siguiente = actual.siguiente  // el nuevo apunta al target
            actual.siguiente = nuevo  // actual pasa a apuntar al nuevo
            tamaño++
            retornar verdadero
        actual = actual.siguiente  // recorre buscando al predecesor del target
    retornar falso

InsertBefore — Lista Simple

InsertBefore(buscado, dato):
    actual := find(buscado)
    si actual == nil:
        retornar falso  // target no encontrado
    nuevo := nuevoNodo(dato)
    nuevo.prev = actual.prev
    nuevo.siguiente = actual
    si actual == head:
        head = nuevo  // si inserté antes del primer nodo, el nuevo es head
    sino:
        // el predecesor enlaza su siguiente al nuevo
        nuevo.prev.siguiente = nuevo
    actual.prev = nuevo  // target pasa a apuntar al nuevo
    tamaño++
    retornar verdadero

InsertBefore — Lista Doble

InsertBefore(buscado, dato):
    actual := find(buscado)
    si actual == nil:
        retornar falso  // target no encontrado
    nuevo := nuevoNodo(dato)
    nuevo.prev = actual.prev
    nuevo.siguiente = actual
    actual.prev.siguiente = nuevo  // el predecesor enlaza su siguiente al nuevo
    actual.prev = nuevo  // target pasa a apuntar al nuevo
    si actual == head:
        head = nuevo  // si inserté antes del primer nodo, el nuevo es head
    tamaño++
    retornar verdadero

InsertBefore — Lista Circular

En la lista simple InsertBefore requiere recorrer la lista buscando al predecesor porque no hay puntero prev. En la lista doble y circular, una vez encontrado el nodo, el reenlace es $O(1)$ gracias al puntero prev.

4.3Eliminación¶

RemoveFirst(): Elimina el primer nodo. Devuelve false si la lista está vacía.

Simple

Doble

Circular

RemoveFirst():
    si IsEmpty():
        retornar falso  // nada que eliminar
    si Size() == 1:
        Clear()  // el único nodo: se vacía toda la lista
        retornar verdadero
    head = head.siguiente  // salta el primer nodo
    tamaño--
    retornar verdadero

RemoveFirst — Lista Simple

RemoveFirst():
    si IsEmpty():
        retornar falso  // nada que eliminar
    si Size() == 1:
        Clear()  // el único nodo: se vacía toda la lista
        retornar verdadero
    head = head.siguiente  // salta el primer nodo
    head.prev = nil  // el nuevo head ya no tiene predecesor
    tamaño--
    retornar verdadero

RemoveFirst — Lista Doble

RemoveFirst():
    si IsEmpty():
        retornar falso  // nada que eliminar
    si Size() == 1:
        Clear()  // el único nodo: se vacía toda la lista
        retornar verdadero
    cola := head.prev  // guarda la cola antes de mover head
    head = head.siguiente  // salta el primer nodo
    head.prev = cola
    cola.siguiente = head  // vuelve a cerrar el ciclo
    tamaño--
    retornar verdadero

RemoveFirst — Lista Circular

RemoveLast(): Elimina el último nodo. Devuelve false si la lista está vacía.

Simple

Doble

Circular

RemoveLast():
    si IsEmpty():
        retornar falso  // nada que eliminar
    si Size() == 1:
        Clear()  // el único nodo: se vacía toda la lista
        retornar verdadero
    actual := head
    mientras actual.siguiente != tail:
        actual = actual.siguiente  // avanza hasta el anteúltimo nodo
    actual.siguiente = nil  // desconecta el último nodo
    tail = actual  // el anteúltimo pasa a ser la cola
    tamaño--
    retornar verdadero

RemoveLast — Lista Simple

RemoveLast():
    si IsEmpty():
        retornar falso  // nada que eliminar
    si Size() == 1:
        Clear()  // el único nodo: se vacía toda la lista
        retornar verdadero
    tail = tail.prev  // retrocede al anteúltimo nodo
    tail.siguiente = nil  // desconecta el último nodo
    tamaño--
    retornar verdadero

RemoveLast — Lista Doble

RemoveLast():
    si IsEmpty():
        retornar falso  // nada que eliminar
    si Size() == 1:
        Clear()  // el único nodo: se vacía toda la lista
        retornar verdadero
    cola := head.prev  // cola actual
    anteultimo := cola.prev
    anteultimo.siguiente = head  // la nueva cola apunta a head
    head.prev = anteultimo  // head queda enlazado con la nueva cola
    tamaño--
    retornar verdadero

RemoveLast — Lista Circular

RemoveLast es $O(n)$ en la lista simple porque debe recorrer hasta el anteúltimo nodo, mientras que en doble y circular es $O(1)$ gracias al puntero prev.

Remove(data T): Busca y elimina la primera ocurrencia del elemento. Si hay elementos duplicados, solo se elimina el primero que se encuentra. Devuelve false si no lo encuentra.

Simple

Doble

Circular

Remove(dato):
    si IsEmpty():
        retornar falso  // nada que eliminar
    si head.dato == dato:
        RemoveFirst()  // el target es la cabeza: reutiliza el caso simple
        retornar verdadero
    actual := head
    mientras actual.siguiente != nil:
        si actual.siguiente.dato == dato:
            // salta el nodo a eliminar
            actual.siguiente = actual.siguiente.siguiente
            si actual.siguiente == nil:
                // si eliminé el último, actual pasa a ser la cola
                tail = actual
            tamaño--
            retornar verdadero
        actual = actual.siguiente
    retornar falso

Remove — Lista Simple

Remove(dato):
    actual := find(dato)
    si actual == nil:
        retornar falso  // dato no encontrado
    si actual == head:
        head = actual.siguiente  // el target era la cabeza
    sino:
        // salta hacia adelante desde el predecesor
        actual.prev.siguiente = actual.siguiente
    si actual == tail:
        tail = actual.prev  // el target era la cola
    sino:
        // salta hacia atrás desde el sucesor
        actual.siguiente.prev = actual.prev
    tamaño--
    retornar verdadero

Remove — Lista Doble

Remove(dato):
    si IsEmpty():
        retornar falso  // nada que eliminar
    si Size() == 1:
        si head.dato == dato:
            Clear()  // era el único nodo
            retornar verdadero
        retornar falso
    actual := head
    para i := 0; i < Size(); i++:
        si actual.dato == dato:
            // salta el nodo en el ciclo
            actual.prev.siguiente = actual.siguiente
            actual.siguiente.prev = actual.prev
            si actual == head:
                head = actual.siguiente  // si eliminé la cabeza, avanza
            tamaño--
            retornar verdadero
        actual = actual.siguiente
    retornar falso

Remove — Lista Circular

La lista simple debe tratar como caso especial la eliminación de la cabeza (no hay predecesor) y la actualización de tail. En doble y circular, el puntero prev permite reenlazar simétricamente, aunque en doble aún se verifican extremos.

4.4Recorrido¶

Values(): Devuelve un slice con los datos en el orden de la lista.

Simple

Doble

Circular

Values():
    resultado := []
    actual := head
    mientras actual != nil:
        resultado.agregar(actual.dato)
        actual = actual.siguiente  // avanza al siguiente nodo
    retornar resultado

Values — Lista Simple

Values():
    resultado := []
    actual := head
    mientras actual != nil:
        resultado.agregar(actual.dato)
        actual = actual.siguiente  // avanza al siguiente nodo
    retornar resultado

Values — Lista Doble

Values():
    si IsEmpty():
        retornar []  // sin nodos, no hay nada que recorrer
    resultado := []
    actual := head
    // nunca llega a nil: recorre una vuelta completa
    para i := 0; i < Size(); i++:
        resultado.agregar(actual.dato)
        actual = actual.siguiente
    retornar resultado

Values — Lista Circular

4.5Utilidad¶

Clear(): Elimina todos los nodos y deja la lista vacía.

Simple

Doble

Circular

Clear():
    head = nil
    tail = nil
    tamaño = 0

Clear — Lista Simple

String(): Devuelve una representación textual de la lista.

Simple

Doble

Circular

String():
    elementos := Values()
    retornar "[" + elementos.join(", ") + "]"

String — Lista Simple

5Lista con Centinelas¶

Figure 7:Lista Enlazada Doble con Centinelas

1
2
3
4
5
type List[T comparable] struct {
    head *node[T]  // centinela frontal
    tail *node[T]  // centinela trasero
    size int
}

Los centinelas eliminan los casos borde de lista vacía, cabeza y cola. Al inicializar la lista, head.siguiente = tail y tail.prev = head. Como los centinelas nunca son nil, toda inserción o eliminación ocurre siempre entre dos nodos reales o ficticios, y las operaciones se vuelven uniformes.

find: Al no haber nil, el recorrido va desde head.siguiente hasta llegar al centinela tail.

find(buscado):
    // el primer nodo real está tras el centinela frontal
    actual := head.siguiente
    // el centinela trasero marca el fin: nunca se llega a nil
    mientras actual != tail:
        si actual.dato == buscado:
            retornar actual
        actual = actual.siguiente
    retornar nil

find — Lista con Centinelas

IsEmpty: La lista vacía se detecta cuando size == 0 o los centinelas se apuntan entre sí.

IsEmpty():
    // vacía cuando los centinelas se apuntan entre sí
    retornar head.siguiente == tail

IsEmpty — Lista con Centinelas

Head / Tail: El primer dato está en head.siguiente y el último en tail.prev.

Head():
    si IsEmpty():
        retornar zero, falso  // lista vacía
    // el primer nodo real está tras el centinela frontal
    retornar head.siguiente.dato, verdadero

Tail():
    si IsEmpty():
        retornar zero, falso  // lista vacía
    // el último nodo real está antes del centinela trasero
    retornar tail.prev.dato, verdadero

Head / Tail — Lista con Centinelas

InsertBefore: No necesita verificar si actual es la cabeza real porque el centinela head garantiza que actual.prev nunca es nil.

InsertBefore(buscado, dato):
    actual := find(buscado)
    si actual == nil:
        retornar falso  // buscado no encontrado
    nuevo := nuevoNodo(dato)
    // si actual es el primer nodo real, su prev es el centinela head
    nuevo.prev = actual.prev
    nuevo.siguiente = actual
    actual.prev.siguiente = nuevo  // el predecesor enlaza su siguiente al nuevo
    actual.prev = nuevo  // actual pasa a apuntar al nuevo
    tamaño++
    retornar verdadero

InsertBefore — Lista con Centinelas

InsertAfter: Como actual.siguiente nunca es nil (puede ser tail), no hay caso especial de cola.

InsertAfter(buscado, dato):
    actual := find(buscado)
    si actual == nil:
        retornar falso  // buscado no encontrado
    nuevo := nuevoNodo(dato)
    // el sucesor puede ser el centinela tail: nunca es nil
    nuevo.siguiente = actual.siguiente
    nuevo.prev = actual
    actual.siguiente.prev = nuevo  // el sucesor enlaza su prev al nuevo
    actual.siguiente = nuevo  // actual pasa a apuntar al nuevo
    tamaño++
    retornar verdadero

InsertAfter — Lista con Centinelas

Prepend: Inserta entre el centinela head y el primer nodo real. No puede delegar en InsertBefore porque busca por valor y fallaría con datos duplicados.

Prepend(dato):
    nuevo := nuevoNodo(dato)
    // si la lista está vacía, head.siguiente es tail: igual funciona
    nuevo.siguiente = head.siguiente
    nuevo.prev = head
    // el primer nodo real (o el centinela tail) enlaza su prev al nuevo
    head.siguiente.prev = nuevo
    head.siguiente = nuevo  // el centinela head apunta al nuevo
    tamaño++

Prepend — Lista con Centinelas

Append: Inserta entre el último nodo real y el centinela tail.

Append(dato):
    nuevo := nuevoNodo(dato)
    nuevo.siguiente = tail  // apunta al centinela final
    // si la lista está vacía, tail.prev es head: igual funciona
    nuevo.prev = tail.prev
    // el último nodo real (o el centinela head) enlaza su siguiente al nuevo
    tail.prev.siguiente = nuevo
    tail.prev = nuevo  // el centinela tail apunta al nuevo
    tamaño++

Append — Lista con Centinelas

Remove: No necesita verificar si el nodo es head o tail real. Los centinelas aseguran que actual.prev y actual.siguiente siempre existen.

Remove(dato):
    actual := find(dato)
    si actual == nil:
        retornar falso  // dato no encontrado
    // sin casos de cabeza o cola: si actual es el primer o último nodo real,
    // el vecino del otro lado es un centinela y se reenlaza igual
    actual.prev.siguiente = actual.siguiente  // el predecesor salta al sucesor
    actual.siguiente.prev = actual.prev  // el sucesor salta al predecesor
    tamaño--
    retornar verdadero

Remove — Lista con Centinelas

RemoveFirst: Reenlaza el centinela head con el segundo nodo real. No puede delegar en Remove por el mismo problema de los duplicados.

RemoveFirst():
    si IsEmpty():
        retornar falso  // nada que eliminar
    head.siguiente = head.siguiente.siguiente  // salta el primer nodo real
    // el nuevo head.siguiente apunta al centinela
    // (puede ser tail si era el único nodo)
    head.siguiente.prev = head
    tamaño--
    retornar verdadero

RemoveFirst — Lista con Centinelas

RemoveLast: Reenlaza el centinela tail con el anteúltimo nodo real.

RemoveLast():
    si IsEmpty():
        retornar falso  // nada que eliminar
    tail.prev = tail.prev.prev  // retrocede al anteúltimo nodo real
    // el nuevo tail.prev apunta al centinela
    // (puede ser head si era el único nodo)
    tail.prev.siguiente = tail
    tamaño--
    retornar verdadero

RemoveLast — Lista con Centinelas

Clear: Solo reenlaza los centinelas entre sí.

Clear():
    head.siguiente = tail  // reenlaza los centinelas entre sí
    tail.prev = head
    tamaño = 0

Clear — Lista con Centinelas

Ventajas frente a las versiones sin centinelas:

InsertBefore e InsertAfter sin verificar extremos.
Prepend y Append con código simétrico, sin casos de lista vacía.
Remove sin verificar head/tail.
RemoveFirst y RemoveLast con código simétrico.
Clear solo reenlaza los centinelas.
IsEmpty es simplemente comparar punteros.

La principal desventaja es el costo de memoria de dos nodos adicionales, que es despreciable en la mayoría de los escenarios.

Comparación de algunas de las operaciones según la variante

Operación	Simple	Doble	Circular	Centinelas
`Head`	$O(1)$	$O(1)$	$O(1)$	$O(1)$
`Tail`	$O(1)$	$O(1)$	$O(1)$	$O(1)$
`Prepend`	$O(1)$	$O(1)$	$O(1)$	$O(1)$
`Append`	$O(1)$	$O(1)$	$O(1)$	$O(1)$
`InsertAfter`	$O(n)$	$O(n)$	$O(n)$	$O(n)$
`InsertBefore`	$O(n)$	$O(n)$	$O(n)$	$O(n)$
`RemoveFirst`	$O(1)$	$O(1)$	$O(1)$	$O(1)$
`RemoveLast`	$O(n)$	$O(1)$	$O(1)$	$O(1)$
`Remove`	$O(n)$	$O(n)$	$O(n)$	$O(n)$
`find`	$O(n)$	$O(n)$	$O(n)$	$O(n)$
`Clear`	$O(1)$	$O(1)$	$O(1)$	$O(1)$

La complejidad asintótica de las operaciones que requieren búsqueda es $O(n)$ en todas las variantes. La diferencia está en las constantes y en la cantidad de casos especiales que debe manejar el código: la lista simple requiere verificaciones constantes de nil en los extremos, mientras que los centinelas las eliminan por completo.

6Ejercicios¶

Los ejercicios de este capítulo están en 03-listas/ejercicios/ del repositorio taller-tad.

Antes de comenzar, asegurate de tener implementadas las estructuras necesarias en data-structures, que está dentro del repositorio taller-tad. Ambas tareas se trabajan en paralelo: primero completás las implementaciones en data-structures y después las usás acá.