Listas
Arranjos são sequências de elementos de um mesmo tipo, armazenados em posições contíguas de memória, e que possuem tamanho fixo. Como vimos na seção anterior, eles são úteis nos mais variados cenários. Entretanto, há situações em que desejamos maior flexibilidade, e as propriedades de arranjos não se adequam às nossas necessidades. Por exemplo, arranjos não são a estrutura de dados ideal se desejamos alguma das características abaixo:
-
Capacidade de inserir elementos no meio da estrutura de dados. Se usarmos um arranjo e precisarmos inserir um elemento no meio da sequência, precisamos mover todos os elementos do arranjo.
-
Capacidade de inserir um número arbitrário de elementos. Em outras palavras, deseja-se que a estrutura de dados possua um tamanho dinâmico, sem valor máximo pré-definido.
Listas encadeadas são a forma mais simples de estrutura de dados dinâmica. Em uma lista, os elementos não são armazenados contiguamente, como acontece em arranjos. Nelas, cada elemento é armazenado separadamente, e possui valor (o dado que desejamos acessar) e um ponteiro para o próximo elemento. Um ponteiro (ou apontador) é uma variável que armazena o endereço de outra variável (eles referenciam outra variável). No caso de listas encadeadas, um ponteiro armazena o endereço do próximo elemento da lista. Para percorrermos a lista, basta seguirmos os ponteiros ao longo dela.
A flexibilidade de listas encadeadas não vem de graça. Listas encadeadas possuem duas desvantagens principais. Primeiro, precisamos de espaço adicional para armazenar os ponteiros. Segundo, se quisermos acessar um elemento em uma dada posição da lista, precisamos percorrer todos os elementos anteriores a ele na lista.
A classe abaixo um nodo de uma lista encadeada de acordo com a descrição acima.
class NodoLista:
"""Esta classe representa um nodo de uma lista encadeada."""
def __init__(self, dado=0, proximo_nodo=None):
self.dado = dado
self.proximo = proximo_nodo
def __repr__(self):
return '%s -> %s' % (self.dado, self.proximo)Agora que já possuímos uma representação para um nodo da lista, nossa definição de lista encadeada está quase pronta. Para facilitar a implementação de alguns métodos importantes, criaremos uma nova classe para armazenar um ponteiro para a cabeça da lista. Essa classe será nossa lista encadeada propriamente dita. Veja:
class ListaEncadeada:
"""Esta classe representa uma lista encadeada."""
def __init__(self):
self.cabeca = None
def __repr__(self):
return "[" + str(self.cabeca) + "]"Observe que nas definições acima criamos duas classes. A classe NodoLista define apenas um nodo (ou nó) da lista. Cada nodo da nossa lista possui um campo dado e um campo próximo. O campo proximo é um apontador para o próximo nodo da lista. Essa cadeia de nodo referenciando outro nodo mostra o caráter encadeado da lista. A classe Lista contém apenas um apontador para o primeiro elemento da lista. O primeiro e o último elementos de uma lista são muito importantes, por isso recebem nomes especiais: cabeça e cauda da lista, respectivamente.
A figura abaixo ilustra a representação de listas encadeadas.
Na figura acima, chamamos atenção para os apontadores da cabeça e da cauda da lista. Observe que no último elemento da lista, o apontador para o próximo possui um desenho diferente, indicando que ele não aponta para nenhum elemento, ou seja, seu ponteiro proximo é None.
As três operações mais importantes de listas encadeadas são a inserção, a remoção, e a busca de elementos. Mostraremos como essas operações funcionam a seguir, implementando cada uma delas como um método da classe ListaEncadeada. Assim, teremos exercitado não somente nossas habilidades em algoritmos, mas também teremos entendido melhor como criar classes e objetos em Python.
Inserção
A forma mais simples e mais rápida de se inserir um elemento em uma lista encadeada é inseri-lo no começo da lista. O código abaixo estende nossa classe Lista definida anteriormente para conter uma função insere_no_inicio.
def insere_no_inicio(lista, novo_dado):
# 1) Cria um novo nodo com o dado a ser armazenado.
novo_nodo = NodoLista(novo_dado)
# 2) Faz com que o novo nodo seja a cabeça da lista.
novo_nodo.proximo = lista.cabeca
# 3) Faz com que a cabeça da lista referencie o novo nodo.
lista.cabeca = novo_nodoA função insere_no_inicio opera em três etapas, mostradas nos comentários no código. A figura abaixo ilustra a implementação dessa função.
O exemplo abaixo cria uma lista encadeada e testa nossa implementação do método insere_no_inicio.
lista = ListaEncadeada()
print("Lista vazia:", lista)
insere_no_inicio(lista, 5)
print("Lista contém um único elemento:", lista)
insere_no_inicio(lista, 10)
print("Inserindo um novo elemento:", lista)Lista vazia: [None] Lista contém um único elemento: [5 -> None] Inserindo um novo elemento: [10 -> 5 -> None]
Inserir um elemento (seja no início seja no meio) de uma lista encadeada é uma tarefa relativamente fácil: basta mudarmos os apontadores dos nodos envolvidos. Já a inserção de um elemento em um arranjo pode ser bem custosa, pois ela pode envolver a mudança de posição de grande parte dos elementos presentes no arranjo.
Por outro lado, referências a elementos arbitrários são muito mais rápidas em arranjos (complexidade $O(1)$), ao passo que em uma lista pode ser necessário percorrer toda a lista para referenciarmos um elemento (complexidade $O(n)$ no tamanho da lista).
Em algumas situações, desejamos controlar a ordem com que os nodos são inseridos na lista. Para isso, precisamos ser capazes de especificar um nodo após (ou antes) o qual desejamos inserir um novo nodo. No código abaixo, implementamos o método insere_depois, que nos permite inserir um nodo após um outro nodo da lista.
def insere_depois(lista, nodo_anterior, novo_dado):
assert nodo_anterior, "Nodo anterior precisa existir na lista."
# Cria um novo nodo com o dado desejado.
novo_nodo = NodoLista(novo_dado)
# Faz o próximo do novo nodo ser o próximo do nodo anterior.
novo_nodo.proximo = nodo_anterior.proximo
# Faz com que o novo nodo seja o próximo do nodo anterior.
nodo_anterior.proximo = novo_nodoO exemplo abaixo ilustra o uso do método insere_depois.
lista = ListaEncadeada()
print("Lista vazia:", lista)
insere_no_inicio(lista, 5)
print("Lista contém um único elemento:", lista)
nodo_anterior = lista.cabeca
insere_depois(lista, nodo_anterior, 10)
print("Inserindo um novo elemento depois de um outro:", lista)Lista vazia: [None] Lista contém um único elemento: [5 -> None] Inserindo um novo elemento depois de um outro: [5 -> 10 -> None]
O método insere_depois assume que o nodo_anterior esteja presente na lista. Caso isto não seja verdade, a asserção no início do método causará um erro na execução do programa, como mostrado a seguir.
lista = ListaEncadeada()
print("Lista vazia:", lista)
# A lista está vazia, então lista.cabeca é None.
# A asserção produzirá um erro indicando isso.
insere_depois(lista, lista.cabeca, 10)
print("Inserindo um novo elemento:", lista)Lista vazia: [None]
---------------------------------------------------------------------------
AssertionError Traceback (most recent call last)
<ipython-input-117-8df10f8f3b5a> in <module>()
3
4 # A lista está vazia, então lista.cabeca é None.
5 # A asserção produzirá um erro indicando isso.
----> 6 insere_depois(lista, lista.cabeca, 10)
7 print("Inserindo um novo elemento:", lista)
<ipython-input-115-1a91d5424534> in insere_depois(lista, nodo_anterior, novo_dado)
1 def insere_depois(lista, nodo_anterior, novo_dado):
----> 2 assert nodo_anterior, "Nodo anterior precisa existir na lista."
3
4 # Cria um novo nodo com o dado desejado.
5 novo_nodo = NodoLista(novo_dado)
AssertionError: Nodo anterior precisa existir na lista.
Busca
A pesquisa por um valor em uma lista é uma tarefa relativamente fácil, se comparada à tarefa de inserção de elementos. O único detalhe a ser observado é o fato de que precisamos percorrer a lista desde o começo para pesquisar por qualquer um dos elementos. Veja o exemplo abaixo.
def busca(lista, valor):
corrente = lista.cabeca
while corrente and corrente.dado != valor:
corrente = corrente.proximo
return correnteVeja abaixo como usar o método busca.
lista = ListaEncadeada()
for i in range(8):
insere_no_inicio(lista, i)
print("Lista:", lista)
for i in range(8, -4, -2):
elemento = busca(lista, i)
if elemento:
print("Elemento {0} presente na lista!".format(i))
else:
print("Elemento {0} não encontrado.".format(i))Lista: [7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 -> None] Elemento 8 não encontrado. Elemento 6 presente na lista! Elemento 4 presente na lista! Elemento 2 presente na lista! Elemento 0 presente na lista! Elemento -2 não encontrado.
Remoção
Outra funcionalidade importante de listas encadeadas é a remoção de elementos. Em linguagens como C e C++, o programador precisa gerenciar a memória do programa manualmente, o que faz com que a inserção e remoção de elementos sejam tarefas mais complexas. Felizmente, em Python não precisamos gerenciar a memória do programa manualmente. Assim, ao remover um elemento, precisamos simplesmente de remover as referências a ele em nosso programa.
A implementação do método remove é mais complicada que a implementação dos métodos de inserção, pois o método remove precisa lidar com algumas situações. Se o elemento a ser removido é o primeiro da lista, simplesmente alteramos a cabeça da lista para apontar para o próximo elemento. Caso o elemento a ser removido não seja a cabeça da lista, precisamos encontrar a posição em que o elemento se encontra e alterar os apontadores correspondentes, tendo em que mente o fato de que a remoção do último elemento da lista precisa ser tratada de modo diferente. O exemplo abaixo mostra a implementação de um método para remover um elemento de uma lista encadeada seguindo este raciocício.
def remove(self, valor):
assert self.cabeca, "Impossível remover valor de lista vazia."
# Nodo a ser removido é a cabeça da lista.
if self.cabeca.dado == valor:
self.cabeca = self.cabeca.proximo
else:
# Encontra a posição do elemento a ser removido.
anterior = None
corrente = self.cabeca
while corrente and corrente.dado != valor:
anterior = corrente
corrente = corrente.proximo
# O nodo corrente é o nodo a ser removido.
if corrente:
anterior.proximo = corrente.proximo
else:
# O nodo corrente é a cauda da lista.
anterior.proximo = NoneO exemplo abaixo ilustra a remoção de elementos de uma lista encadeada.
lista = ListaEncadeada()
for i in range(5):
insere_no_inicio(lista, i)
print("Lista:", lista)
print("Removendo elementos:")
for i in range(5):
remove(lista, i)
print("Removendo o elemento {0}: {1}".format(i, lista))Lista: [4 -> 3 -> 2 -> 1 -> 0 -> None] Removendo elementos: Removendo o elemento 0: [4 -> 3 -> 2 -> 1 -> None] Removendo o elemento 1: [4 -> 3 -> 2 -> None] Removendo o elemento 2: [4 -> 3 -> None] Removendo o elemento 3: [4 -> None] Removendo o elemento 4: [None]
Uma outra alternativa na implementação do algoritmo de remoção de elementos seria a utilização do procedimento de busca para encontrar o elemento a ser removido. Isso reduziria o tamanho da função remove e reusaria uma função já desenvolvida (a função de busca). A prática de reutilização de código deve ser adotada sempre que possível. Em nosso exemplo, por questão de simplicidade, decidimos implementar a função remove sem utilizar a função busca.
Antes de passarmos para o próximo tópico, vejamos um exemplo de algoritmo simples que usa listas encadeadas. Esse exemplo nos permitirá usar alguns dos métodos implementados anteriormente.
Exercícios
-
Remova duplicatas de uma lista ordenada. Suponha que lhe seja fornecida uma lista encadeada armazenando números inteiros em ordem crescente. Sua tarefa é remover todos os elementos duplicados da lista. Por exemplo, dada a lista [0 → 1 → 1 → 5 → 7 → 10 → 10 → None], seu programa deve retornar a lista [0 → 1 → 5 → 7 → 10 → None].
Clique para ver a solução
Assim como nos exemplos da seção anterior, façamos uma análise preliminar. A entrada do algoritmo é uma lista encadeada, ordenada, de números inteiros. A saída do algoritmo é a lista de entrada após removidos os elementos duplicados.
Agora precisamos pensar em como resolver o problema.
def remove_duplicatas(lista):
corrente = lista.cabeca
while corrente:
# Usa proximo_distinto para encontrar o próximo valor distinto na lista.
proximo_distinto = corrente.proximo
while proximo_distinto and proximo_distinto.dado == corrente.dado:
proximo_distinto = proximo_distinto.proximo
# Atualiza o próximo elemento, pulando todos os que forem iguais.
corrente.proximo = proximo_distinto
corrente = proximo_distinto
return listaO exemplo a seguir testa o método remove_duplicatas.
def testa_remove_duplicatas():
# Testa lista vazia.
lista_vazia = ListaEncadeada()
lista_vazia = remove_duplicatas(lista_vazia)
assert str(lista_vazia) == "[None]"
# Testa lista com um único elemento.
lista_um_elemento = ListaEncadeada()
lista_um_elemento.insere_no_inicio(10)
resultado = remove_duplicatas(lista_um_elemento)
assert "[10 -> None]"
# Testa lista com todos os elementos distintos.
lista_elementos_distintos = ListaEncadeada()
for i in range(5, 0, -1):
lista_elementos_distintos.insere_no_inicio(i)
resultado = remove_duplicatas(lista_elementos_distintos)
assert str(resultado) == "[1 -> 2 -> 3 -> 4 -> 5 -> None]"
# Testa remoção de duplicatas.
lista_elementos_repetidos = ListaEncadeada()
lista_elementos_repetidos.insere_no_inicio(10)
lista_elementos_repetidos.insere_no_inicio(10)
lista_elementos_repetidos.insere_no_inicio(7)
lista_elementos_repetidos.insere_no_inicio(5)
lista_elementos_repetidos.insere_no_inicio(1)
lista_elementos_repetidos.insere_no_inicio(1)
lista_elementos_repetidos.insere_no_inicio(0)
lista_elementos_repetidos = remove_duplicatas(lista_elementos_repetidos)
assert str(lista_elementos_repetidos) == "[0 -> 1 -> 5 -> 7 -> 10 -> None]"
print("Sucesso!")
testa_remove_duplicatas()Sucesso!
Nesta seção, implementamos as operações de listas encadeadas fora da classe lista, pois isso facilitou a exposição dos conceitos. Entretanto, poderíamos ter criado essas operações como métodos da classe ListaEncadeada. Clique aqui para ver como isso poderia ser feito.
Playground
# Use este espaço para praticar o que você aprendeu nesta seção.
# Basta digitar o código no espaço abaixo e clicar 'run'.