El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Listas Doblemente Enlazadas

Siguiente ►
►

Introducción

Las listas doblemente enlazadas son una extensión de las listas enlazadas simples. En una lista doblemente enlazada, cada nodo contiene dos punteros: uno que apunta al siguiente nodo en la secuencia y otro que apunta al nodo anterior. Esta estructura permite una navegación bidireccional, lo que facilita ciertas operaciones como la inserción y eliminación de nodos.

Estructura de un Nodo en una Lista Doblemente Enlazada

Cada nodo en una lista doblemente enlazada contiene tres componentes principales:

  1. Dato: El valor almacenado en el nodo.
  2. Puntero al siguiente nodo: Un enlace al siguiente nodo en la lista.
  3. Puntero al nodo anterior: Un enlace al nodo anterior en la lista.

Representación en Python

class Nodo:
    def __init__(self, dato):
        self.dato = dato
        self.siguiente = None
        self.anterior = None

Operaciones Básicas

  1. Inserción

Inserción al Inicio

Para insertar un nodo al inicio de la lista:

  1. Crear un nuevo nodo.
  2. Ajustar el puntero siguiente del nuevo nodo para que apunte al nodo que actualmente es la cabeza.
  3. Ajustar el puntero anterior del nodo que actualmente es la cabeza para que apunte al nuevo nodo.
  4. Actualizar la cabeza de la lista para que sea el nuevo nodo.
class ListaDobleEnlazada:
    def __init__(self):
        self.cabeza = None

    def insertar_inicio(self, dato):
        nuevo_nodo = Nodo(dato)
        if self.cabeza is not None:
            nuevo_nodo.siguiente = self.cabeza
            self.cabeza.anterior = nuevo_nodo
        self.cabeza = nuevo_nodo

Inserción al Final

Para insertar un nodo al final de la lista:

  1. Crear un nuevo nodo.
  2. Recorrer la lista hasta llegar al último nodo.
  3. Ajustar el puntero siguiente del último nodo para que apunte al nuevo nodo.
  4. Ajustar el puntero anterior del nuevo nodo para que apunte al último nodo.
    def insertar_final(self, dato):
        nuevo_nodo = Nodo(dato)
        if self.cabeza is None:
            self.cabeza = nuevo_nodo
            return
        ultimo = self.cabeza
        while ultimo.siguiente:
            ultimo = ultimo.siguiente
        ultimo.siguiente = nuevo_nodo
        nuevo_nodo.anterior = ultimo

  1. Eliminación

Eliminación de un Nodo Específico

Para eliminar un nodo específico:

  1. Encontrar el nodo que contiene el dato a eliminar.
  2. Ajustar el puntero siguiente del nodo anterior para que apunte al nodo siguiente del nodo a eliminar.
  3. Ajustar el puntero anterior del nodo siguiente para que apunte al nodo anterior del nodo a eliminar.
    def eliminar_nodo(self, dato):
        actual = self.cabeza
        while actual:
            if actual.dato == dato:
                if actual.anterior:
                    actual.anterior.siguiente = actual.siguiente
                if actual.siguiente:
                    actual.siguiente.anterior = actual.anterior
                if actual == self.cabeza:
                    self.cabeza = actual.siguiente
                return
            actual = actual.siguiente

  1. Recorrido

Recorrido hacia Adelante

Para recorrer la lista hacia adelante:

  1. Comenzar desde la cabeza.
  2. Continuar moviéndose al siguiente nodo hasta llegar al final de la lista.
    def recorrer_adelante(self):
        actual = self.cabeza
        while actual:
            print(actual.dato, end=' ')
            actual = actual.siguiente
        print()

Recorrido hacia Atrás

Para recorrer la lista hacia atrás:

  1. Comenzar desde el último nodo.
  2. Continuar moviéndose al nodo anterior hasta llegar al inicio de la lista.
    def recorrer_atras(self):
        actual = self.cabeza
        if actual is None:
            return
        while actual.siguiente:
            actual = actual.siguiente
        while actual:
            print(actual.dato, end=' ')
            actual = actual.anterior
        print()

Ejemplo Completo

A continuación, se muestra un ejemplo completo que incluye la creación de una lista doblemente enlazada, la inserción de nodos al inicio y al final, la eliminación de un nodo y el recorrido de la lista en ambas direcciones.

class Nodo:
    def __init__(self, dato):
        self.dato = dato
        self.siguiente = None
        self.anterior = None

class ListaDobleEnlazada:
    def __init__(self):
        self.cabeza = None

    def insertar_inicio(self, dato):
        nuevo_nodo = Nodo(dato)
        if self.cabeza is not None:
            nuevo_nodo.siguiente = self.cabeza
            self.cabeza.anterior = nuevo_nodo
        self.cabeza = nuevo_nodo

    def insertar_final(self, dato):
        nuevo_nodo = Nodo(dato)
        if self.cabeza is None:
            self.cabeza = nuevo_nodo
            return
        ultimo = self.cabeza
        while ultimo.siguiente:
            ultimo = ultimo.siguiente
        ultimo.siguiente = nuevo_nodo
        nuevo_nodo.anterior = ultimo

    def eliminar_nodo(self, dato):
        actual = self.cabeza
        while actual:
            if actual.dato == dato:
                if actual.anterior:
                    actual.anterior.siguiente = actual.siguiente
                if actual.siguiente:
                    actual.siguiente.anterior = actual.anterior
                if actual == self.cabeza:
                    self.cabeza = actual.siguiente
                return
            actual = actual.siguiente

    def recorrer_adelante(self):
        actual = self.cabeza
        while actual:
            print(actual.dato, end=' ')
            actual = actual.siguiente
        print()

    def recorrer_atras(self):
        actual = self.cabeza
        if actual is None:
            return
        while actual.siguiente:
            actual = actual.siguiente
        while actual:
            print(actual.dato, end=' ')
            actual = actual.anterior
        print()

# Ejemplo de uso
lista = ListaDobleEnlazada()
lista.insertar_inicio(10)
lista.insertar_inicio(20)
lista.insertar_final(30)
lista.recorrer_adelante()  # Salida: 20 10 30
lista.recorrer_atras()     # Salida: 30 10 20
lista.eliminar_nodo(10)
lista.recorrer_adelante()  # Salida: 20 30

Conclusión

Las listas doblemente enlazadas son una estructura de datos versátil que permite una navegación bidireccional, facilitando operaciones como la inserción y eliminación de nodos. Aunque son más complejas que las listas enlazadas simples debido a la necesidad de manejar dos punteros por nodo, ofrecen una mayor flexibilidad y eficiencia en ciertas situaciones.

En el próximo tema, exploraremos las listas circulares, una variación interesante de las listas enlazadas.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2024. Todos los derechos reservados