Listas: listas enlazadas simples y dobles

5.1 Definición de lista y sus tipos

Lista — es una estructura de datos dinámica que consiste en elementos (nodos), donde cada nodo contiene datos y enlaces a otros nodos. A diferencia de los arrays, las listas pueden cambiar su tamaño durante la ejecución del programa.

¡Importante! En este caso no estamos hablando de la clase list de Python, sino de la estructura de datos de la teoría de algoritmos.

Tipos de listas:

• Lista enlazada simple (Singly Linked List): Cada nodo contiene datos y un enlace al siguiente nodo.
• Lista doblemente enlazada (Doubly Linked List): Cada nodo contiene datos, un enlace al siguiente nodo y un enlace al nodo anterior.

5.2 Cómo funciona una lista enlazada simple

Estructura de una lista enlazada simple:

• Nodo (Node): Consta de dos partes: datos y un enlace al siguiente nodo.
• Cabecera (Head): Puntero al primer nodo de la lista.

Cómo funciona:

• Añadir un nodo: Se realiza creando un nuevo nodo y actualizando el enlace del último nodo al nuevo nodo.
• Eliminar un nodo: Requiere actualizar el enlace del nodo anterior al nodo siguiente del nodo que se va a eliminar.

Ejemplo de implementación:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Ejemplo de uso:
sll = SinglyLinkedList()
sll.append(1)
sll.append(2)
sll.append(3)
sll.display()  # Salida: 1 -> 2 -> 3 -> None

5.3 Cómo funciona una lista doblemente enlazada

Estructura de una lista doblemente enlazada:

• Nodo (Node): Consta de tres partes: datos, un enlace al siguiente nodo y un enlace al nodo anterior.
• Cabecera (Head): Puntero al primer nodo de la lista.
• Cola (Tail): Puntero al último nodo de la lista (no es obligatorio, pero se usa frecuentemente).

Cómo funciona:

• Añadir un nodo: Se realiza creando un nuevo nodo y actualizando los enlaces del último nodo y el nuevo nodo.
• Eliminar un nodo: Requiere actualizar los enlaces de los nodos anterior y siguiente al nodo que se va a eliminar.

Ejemplo de implementación:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        new_node.prev = last

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" <-> ")
            current = current.next
        print("None")

# Ejemplo de uso:
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.display()  # Salida: 1 <-> 2 <-> 3 <-> None

5.4 Operaciones básicas

Operaciones básicas: inserción, eliminación, búsqueda

Inserción:

• Lista enlazada simple: Insertar un nuevo nodo al final de la lista requiere pasar por todos los nodos hasta el último y actualizar el enlace del último nodo.
• Lista doblemente enlazada: Insertar un nuevo nodo al final de la lista es similar a la lista enlazada simple, pero también requiere actualizar el enlace prev del nuevo nodo al nodo anterior.

Eliminación:

• Lista enlazada simple: Eliminar un nodo requiere pasar por la lista hasta el nodo que se debe eliminar y actualizar el enlace del nodo anterior al nodo siguiente del nodo que se va a eliminar.
• Lista doblemente enlazada: Eliminar un nodo requiere actualizar los enlaces next y prev de los nodos vecinos del nodo que se va a eliminar.

Búsqueda: Recorrer la lista desde la cabecera hasta la cola y comparar los datos de cada nodo con el valor buscado. La complejidad temporal es O(n).

5.5 Ejemplo de uso de listas

Vamos a implementar como ejemplo una pila basada en una lista enlazada simple.

La pila se puede implementar fácilmente utilizando una lista enlazada simple, usando los métodos de adición push y eliminación pop de elementos. Debe tener 2 métodos:

• push — agregar un nuevo elemento al final de la lista
• pop — sacar el último elemento del final de la lista

Ejemplo de implementación:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Stack:
    def __init__(self):
        self.top = None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.top
        self.top = new_node

    def pop(self):
        if not self.top:
            return None
        data = self.top.data
        self.top = self.top.next
        return data

    def display(self):
        current = self.top
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Ejemplo de uso:
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.display()  # Salida: 3 -> 2 -> 1 -> None
print(stack.pop())  # Salida: 3
stack.display()  # Salida: 2 -> 1 -> None