Algoritmos y Estructuras de Datos

Lista enlazada

Cuando trabajamos con datos secuenciales, normalmente utilizamos listas o arreglos para almacenarlos y acceder a ellos. Sin embargo, en algunos casos puede ser más rápido usar una lista enlazada. Especialmente cuando en el programa se deben agregar o eliminar elementos al principio de la lista muchas veces, las listas enlazadas pueden ofrecer un mejor rendimiento.
Una lista enlazada es una de las estructuras de datos más básicas. Contiene una lista de elementos, puede actualizar dicha lista agregando elementos y acceder a ellos, de forma muy similar a como lo haríamos con un array o lista ordinaria. Cuando trabajamos con listas enlazadas, a cada elemento se le conoce como un Node, que contiene los datos y un enlace al siguiente Node. En una lista enlazada simple, cada elemento (el Node) tiene una referencia al siguiente nodo, y el último nodo tiene una referencia a nada - null. En la literatura, al primer elemento de una lista enlazada simple se le llama la head, mientras que al último se le llama la tail. Una de las posibles implementaciones de una lista enlazada puede verse así:
class Node:
    def __init__(self, data):
        self.data = data               # Almacena los datos
        self.after = None              # Almacena un enlace al siguiente elemento


class LinkedList:
    def __init__(self):
        self.head = None               # Inicialmente no hay elementos

    def append(self, data):            # Agrega un nuevo elemento a la lista
        new_node = Node(data)          # Crea un nodo que contiene data
        if self.head is None:          # Si no hay elementos en la lista
            self.head = new_node       # Asigna la head al nuevo nodo
            return
        current = self.head            # Empieza a recorrer la lista desde la head
        while current.after:           # Mientras no hayamos llegado a la tail
            current = current.after    # Avanza al siguiente nodo
        current.after = new_node       # Actualiza la tail y la asigna al nuevo nodo

    def print(self):                   # Imprime todos los elementos de la lista
        current = self.head            # Comienza desde la head
        while current:                 # Mientras no hayamos llegado al final
            print(current.data, end='\n' if current.after is None else ' --> ')
            current = current.after    # Avanza al siguiente nodo


names = LinkedList()                   # Crea una lista enlazada vacía
names.append('Anna')                   # Agrega Anna a la lista
names.append('Bob')                    # Agrega Bob a la lista
names.append('Sona')                   # Agrega Sona a la lista
names.print()                          # Anna --> Bob --> Sona
notion image
En esta implementación, tenemos dos clases: Node y LinkedList. La clase Node tiene dos atributos: data y after. El atributo data almacena el valor del nodo, mientras que el atributo after contiene la referencia al siguiente nodo de la lista. La clase LinkedList tiene un solo atributo: head, que mantiene la referencia al primer nodo de la lista. El método append() se utiliza para agregar un nuevo nodo al final de la lista, y el método print() se usa para imprimir los elementos de la lista.

Lista doblemente enlazada

Además, también existen listas doblemente enlazadas donde cada elemento tiene una referencia tanto al siguiente elemento como al elemento anterior. Esto permite recorrer la lista en ambas direcciones.

Análisis de la lista enlazada

Hay varios aspectos importantes a tener en cuenta al trabajar con listas enlazadas:
  • Acceder a un elemento en una lista enlazada requiere tiempo , ya que se necesita recorrer la lista desde la head para encontrarlo.
  • Si conocemos el Node después del cual queremos insertar un nuevo elemento, la inserción solo requiere tiempo , pues basta con actualizar las referencias de los nodos vecinos.
  • Si conocemos el Node que se desea eliminar, su eliminación también requiere tiempo , ya que únicamente se deben actualizar las referencias de los nodos vecinos.
  • Las listas enlazadas utilizan más memoria que los arreglos debido a la referencia adicional que se almacena en cada elemento.

Desafío

Dadas n consultas, debes ejecutarlas. Hay 2 tipos de consultas:
  1. Insertar un número al inicio de la lista.
  1. Imprimir toda la lista.

Entrada

La primera línea de la entrada contiene un único entero n (1 ≤ n ≤ 1000): la cantidad de consultas.
Las siguientes n líneas contienen las consultas: print si se debe imprimir toda la lista, e insert x si es necesario insertar el número x al comienzo de la lista ( ≤ x ≤ ).

Salida

El programa debe ejecutar correctamente todas las consultas e imprimir la lista separando los elementos con espacios.

Ejemplos

Entrada
Salida
6 insert 8 print insert 10 insert -2 insert -6 print
8 -6 -2 10 8
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue