Implementación de lista enlazada individualmente de Python

Aprenda cómo implementar una lista enlazada individualmente en Python. Explore la asignación de memoria dinámica, operaciones de nodos, inserción, recorrido y eliminación.

Pruébelo en el editor

Descripción general

Una lista vinculada es una estructura de datos lineal donde los elementos no se almacenan en ubicaciones de memoria contiguas. En cambio, cada elemento (llamado nodo) es un objeto separado que contiene una referencia al siguiente nodo de la secuencia.

El principal beneficio de una lista vinculada sobre una matriz tradicional es su tamaño dinámico y la capacidad de insertar o eliminar elementos en tiempo constante O(1) al principio. Sin embargo, acceder a elementos por índice requiere un recorrido lineal, lo que lleva O(n) tiempo.

En Python, implementamos una lista vinculada definiendo una clase Node para almacenar los datos y el puntero de referencia, y una clase LinkedList para administrar el nodo principal, las inserciones al principio o al final y las eliminaciones.

Código y salida de ejecución

Implementación de listas enlazadas individualmente en Python, que muestra la creación, adición y recorrido de listas de nodos.

linked_list.py

Pruébelo en el editor

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

class LinkedList:
    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 delete(self, key):
        curr = self.head
        if curr and curr.data == key:
            self.head = curr.next
            curr = None
            return
        prev = None
        while curr and curr.data != key:
            prev = curr
            curr = curr.next
        if not curr:
            return
        prev.next = curr.next
        curr = None
        
    def display(self):
        elements = []
        curr = self.head
        while curr:
            elements.append(str(curr.data))
            curr = curr.next
        print(" -> ".join(elements) + " -> None")

# Instantiate and build the linked list
llist = LinkedList()
llist.append("Node A")
llist.append("Node B")
llist.append("Node C")
print("Initial Linked List:")
llist.display()

print("Deleting 'Node B':")
llist.delete("Node B")
llist.display()

Salida terminal

Initial Linked List:
Node A -> Node B -> Node C -> None
Deleting 'Node B':
Node A -> Node C -> None

Implementación paso a paso

Implementación de la funcionalidad deshacer y rehacer en editores de texto
Construir estructuras de datos complejas como gráficos, pilas y colas
Administrar listas donde las frecuencias de inserción y eliminación superan en número a las acciones de búsqueda

Preguntas frecuentes

¿Cuál es la diferencia entre listas simple y doblemente enlazadas?

En una lista enlazada individualmente, cada nodo apunta sólo al siguiente nodo. En una lista doblemente enlazada, cada nodo contiene referencias tanto al nodo siguiente como al anterior, lo que permite el recorrido bidireccional a costa de memoria adicional.

¿Por qué Python no tiene una clase LinkedList incorporada?

Las matrices (listas) de Python se implementan como matrices dinámicas. Debido a la administración de memoria de Python y las optimizacionesCPython, las listas estándar son extremadamente rápidas y eficientes para la mayoría de las tareas, lo que reduce la necesidad práctica de una lista vinculada incorporada.

Temas relacionados

Tutorial de estructura de datos de pila de Python

Implemente una pila LIFO en Python. Ejecute nuestro ejemplo de código de pila interactivo para dominar los límites de inserción, extracción, visualización y capacidad.

Tutorial de estructura de datos de cola de Python

Domine las operaciones de cola FIFO en Python. Ejecute y ejecute nuestro ejemplo de cola interactiva que muestra los métodos de poner y quitar la cola.