Algoritmos e Estruturas de Dados

Lista Ligada

Ao trabalhar com dados sequenciais, costumamos utilizar listas/arrays para armazenar e aceder a esses dados. No entanto, em alguns casos, pode ser mais rápido utilizar uma lista ligada. Isto torna-se especialmente útil quando o programa precisa de adicionar ou remover elementos no início da lista muitas vezes, pois nesse cenário as listas ligadas podem ser mais eficientes.
A lista ligada é uma das estruturas de dados mais elementares. Ela guarda uma sequência de elementos, permite adicionar novos elementos e aceder aos já existentes – tudo de forma parecida com uma lista/array convencional. Quando trabalhamos com listas ligadas, chamamos cada elemento de Node, que contém dados e um link para o próximo Node. Numa lista ligada simples, cada elemento (Node) tem uma referência para o próximo nó, e o último nó tem uma referência para nada – null. Na literatura, o primeiro elemento de uma lista ligada simples é chamado de cabeça (head), enquanto o último é chamado de cauda (tail). Uma das formas de implementar uma lista ligada pode ser:
class Node:
    def __init__(self, data):
        self.data = data               # Armazena o dado
        self.after = None              # Armazena uma referência para o próximo elemento


class LinkedList:
    def __init__(self):
        self.head = None               # Inicialmente não há elementos

    def append(self, data):            # Adiciona um novo elemento à lista
        new_node = Node(data)          # Cria um nó que contém data
        if self.head is None:          # Se não existirem elementos na lista
            self.head = new_node       # Define a cabeça (head) como o novo nó
            return
        current = self.head            # Inicia a travessia da lista a partir da cabeça
        while current.after:           # Enquanto não chegamos à cauda
            current = current.after    # Avança para o próximo nó
        current.after = new_node       # Atualiza a cauda definindo-a como o novo nó

    def print(self):                   # Imprime todos os elementos da lista
        current = self.head            # Começa a partir da cabeça
        while current:                 # Enquanto não chegamos ao fim
            print(current.data, end='\n' if current.after is None else ' --> ')
            current = current.after    # Avança para o próximo nó


names = LinkedList()                   # Cria uma lista ligada vazia
names.append('Anna')                   # Adiciona Anna à lista
names.append('Bob')                    # Adiciona Bob à lista
names.append('Sona')                   # Adiciona Sona à lista
names.print()                          # Anna --> Bob --> Sona
notion image
Nesta implementação, temos duas classes: Node e LinkedList. A classe Node possui dois atributos: data e after. O atributo data guarda o valor do nó, enquanto after guarda a referência para o próximo nó na lista. A classe LinkedList tem um atributo: head, que guarda a referência para o primeiro nó da lista. O método append() serve para adicionar um novo nó no final da lista, e o método print() permite imprimir todos os elementos da lista.

Lista Duplamente Ligada

Adicionalmente, também existem listas duplamente ligadas, nas quais cada elemento tem uma referência para o próximo e para o anterior. Isso permite percorrer a lista em ambas as direções.

Análise da Lista Ligada

Alguns pontos importantes a ter em conta quando se trabalha com listas ligadas:
  • Aceder a um elemento numa lista ligada demora , pois é necessário percorrer a lista desde a cabeça para encontrar o elemento.
  • Se soubermos qual é o Node após o qual precisamos inserir um novo elemento, a inserção demora , porque basta atualizar as referências dos nós vizinhos.
  • Se soubermos qual é o Node que precisamos remover, a remoção demora , pois novamente basta atualizar as referências dos nós vizinhos.
  • Listas ligadas usam mais memória do que arrays devido ao armazenamento de uma referência adicional em cada elemento.

Desafio

Dadas n instruções (queries), tens de as executar. Existem 2 tipos de instruções:
  1. Inserir um número no início da lista.
  1. Imprimir a lista completa.

Entrada

A primeira linha da entrada contém um único inteiro n (1 ≤ n ≤ 1000), o número de instruções.
As n linhas seguintes contêm as instruções – print se for para imprimir a lista completa, e insert x se for para inserir o número x no início da lista ( ≤ x ≤ ).

Saída

O programa deve executar corretamente todas as instruções e imprimir a lista, separando os elementos por espaços.

Exemplos

Entrada
Saída
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