Algoritmi e Strutture Dati

Lista Collegata

Quando si lavora con dati sequenziali, di solito si utilizzano liste/array per memorizzare e accedere ai dati. Tuttavia, in alcuni casi, potrebbe essere più efficiente usare una lista collegata (linked list). In particolare, quando un programma deve aggiungere o rimuovere più volte un elemento all’inizio di una lista, le liste collegate possono rivelarsi più veloci.
Una lista collegata è una delle strutture dati più basilari. Consente di memorizzare una lista di elementi, aggiornarla aggiungendo nuovi elementi e accedere a questi ultimi — proprio come una normale lista o un array. Quando si lavora con liste collegate, ogni elemento viene chiamato Node, che contiene i dati e un collegamento al Node successivo. In una lista collegata semplice (singly linked list), ogni elemento (il Node) ha un riferimento al nodo successivo, mentre l’ultimo nodo punta a null. In letteratura, il primo elemento di una lista collegata semplice è chiamato testa (head), mentre l’ultimo elemento è la coda (tail). Una possibile implementazione di una lista collegata può essere la seguente:
class Node:
    def __init__(self, data):
        self.data = data               # Contiene i dati
        self.after = None              # Tiene un collegamento all'elemento successivo


class LinkedList:
    def __init__(self):
        self.head = None               # Inizialmente non ci sono elementi

    def append(self, data):            # Aggiunge un nuovo elemento alla lista
        new_node = Node(data)          # Crea un nodo che memorizza 'data'
        if self.head is None:          # Se la lista è vuota
            self.head = new_node       # Imposta la testa sul nuovo nodo
            return
        current = self.head            # Inizia a percorrere la lista dalla testa
        while current.after:           # Finché non si arriva all'ultimo nodo
            current = current.after    # Passa al nodo successivo
        current.after = new_node       # Aggiorna l'ultimo nodo collegandolo al nuovo nodo

    def print(self):                   # Stampa tutti gli elementi della lista
        current = self.head            # Parte dalla testa
        while current:                 # Finché non si arriva alla fine
            print(current.data, end='\n' if current.after is None else ' --> ')
            current = current.after    # Passa al nodo successivo


names = LinkedList()                   # Crea una lista collegata vuota
names.append('Anna')                   # Aggiunge Anna alla lista
names.append('Bob')                    # Aggiunge Bob alla lista
names.append('Sona')                   # Aggiunge Sona alla lista
names.print()                          # Anna --> Bob --> Sona
notion image
In questa implementazione, abbiamo due classi: Node e LinkedList. La classe Node ha due attributi: data e after. L’attributo data contiene il valore del nodo, mentre after contiene il riferimento al nodo successivo nella lista. La classe LinkedList ha un attributo chiamato head, che memorizza il riferimento al primo nodo. Il metodo append() serve a inserire un nuovo nodo in fondo alla lista, mentre il metodo print() permette di stampare gli elementi della lista.

Lista collegata doppia

Esistono anche liste collegate doppie (doubly linked lists), in cui ciascun elemento ha un riferimento sia al nodo successivo sia al nodo precedente. Questo permette di percorrere la lista in entrambe le direzioni.

Analisi di una Lista Collegata

Ecco alcuni punti importanti da considerare quando si lavora con le liste collegate:
  • Accedere a un elemento in una lista collegata richiede tempo , poiché è necessario attraversare la lista a partire dalla testa per arrivare all’elemento.
  • Se si conosce il Node dopo il quale si vuole inserire il nuovo elemento, l’inserimento richiede tempo , poiché basta aggiornare i riferimenti dei nodi vicini.
  • Se si conosce il Node da rimuovere, la rimozione richiede tempo , poiché basta aggiornare i riferimenti dei nodi vicini.
  • Le liste collegate occupano più memoria rispetto agli array, a causa del riferimento extra memorizzato in ogni elemento.

Sfida

Dato un insieme di n interrogazioni (queries), bisogna eseguirle. Ci sono 2 tipi di interrogazioni:
  1. Inserire un numero all'inizio della lista.
  1. Stampare l'intera lista.

Input

La prima riga di input contiene un singolo intero n (1 ≤ n ≤ 1000), che rappresenta il numero di interrogazioni.
Le successive n righe contengono le interrogazioni — print se bisogna stampare l’intera lista, oppure insert x se è necessario inserire il numero x all’inizio della lista ( ≤ x ≤ ).

Output

Il programma deve eseguire correttamente tutte le interrogazioni e stampare la lista separando gli elementi da spazi.

Esempi

Input
Output
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