23. Listas Encadeadas#

Vimos que uma lista em Python permite inserir elementos no final de um objeto do tipo list usando o método append() de forma eficiente mas inserir um elemento no início ou no meio da lista dá mais trabalho (pop() no meio de um objeto do tipo list em Python). De forma geral, manter uma lista que permite inserir e remover elementos em qualquer posição ou até trocar elementos de lugar pode dar muito trabalho.

Listas encadeadas oferecem uma estrutura alternativa que pode dar menos trabalho com movimentações, inserções e remoções em posições aleatórias, se estivermos dispostos a gastar um pouco mais de espaço.

23.1. Objetivos de aprendizagem#

Realize seus estudos para que, ao final dessa aula, você seja capaz de:

Criar listas encadeadas sem cabeça usando o tipo Celula;
Criar listas encadeadas com cabeça usando o tipo LEncadeada;
Percorrer (varrer) para buscar elementos em uma lista encadeada;
Inserir e remover elementos em qualquer posição de uma lista encadeada;
Utilizar listas encadeadas em seus programas.

23.2. Introdução#

Uma lista encadeada (ou linked list ou ainda lista ligada) é uma sequência de células onde cada célula contém um objeto de algum tipo e o endereço da célula seguinte, como mostra a Figura.

Em Python, uma célula pode ser representada por um objeto da seguinte classe Celula.

class Celula:

    def __init__(self, data):
        self.data = data  # conteúdo da célula
        self.prox = None  # ponteiro para a próxima célula.
                        # None indica que é o final da lista.

    def __str__(self):
        if self.prox:                  # mesmo que if self.prox is not None:
            return f"{self.data} -> "
        return f"{self.data} ."        # vamos usar '.' para indicar final.

23.3. Lista encadeada “sem cabeça”#

Para criar uma sequência encadeada de células contendo os nomes ['Renata', 'José', 'Ana', 'Cristina', 'Paulo', 'Eduardo', 'Isabela', 'Fábio'], podemos executar o seguinte trecho de código:

lista = ['Renata', 'José', 'Ana', 'Cristina', 'Paulo', 'Eduardo', 'Isabela', 'Fábio']

encadeada_sc = None   # nada ainda na lista
for item in lista:
    nova_celula = Celula(item)
    nova_celula.prox = encadeada_sc      # prox aponta para a lista
    encadeada_sc = nova_celula           # nova_celula vira o início da lista

Assumindo que a ordem da lista não é importante, o seguinte trecho de código imprime a sequência encadeada:

def imprima_sequencia( encadeada ):
    cel = encadeada
    while cel:
        print(cel)
        cel = cel.prox   # vai para a próxima célula

O seguinte trecho de código ilustra a criação e impressão da lista encadeada.

Observe que a sequência de nomes está invertida com relação a lista original. Você sabe explicar por quê?

23.4. Lista encadeada “com cabeça”#

Uma inconveniência de tratar as listas encadeadas diretamente como células é que o tratamento de uma lista vazia. Observe no código para criação que a variável encadeada_sc recebe o valor None, ao ínves de uma Celula.

Uma solução é tratar a primeira célula como um marcador para o início da lista. Esse marcador é chamado de cabeça (ou head) da lista encadeada. Vamos criar uma classe LEncadeada para representar uma lista encadeada com cabeça.

class LEncadeada:

    def __init__(self):
        self.cabeca = Celula()  # cria célula com prox == None

    def __str__(self):
        s = ''
        cel = self.cabeca.prox
        while cel:
            s += str(cel)
            cel = cel.prox
        return s

Nesse trecho de código, o método __str__() varre a lista encadeada, de forma semelhante a função imprima_sequencia(), mas a partir de cabeca.prox.

23.4.1. Busca em lista encadeada#

O método busque() varre a lista encadeada a procura de uma célula com um determinado valor. Caso encontre, retorna a célula que contém o valor. Caso contrário, retorna None.

def busque(self, x):
    '''(LEncadeada, obj) -> celula ou None'''

    ptr = self.cabeca.prox
    while ptr and ptr.data != x:
        ptr = ptr.prox
    return ptr

Observe que quando ptr for None, a condição do while se torna falsa, interrompendo a varredura da lista. A varredura também para assim que a célula é encontrada, caso exista.

23.4.2. Inserção#

No primeiro exemplo de criação de lista encadeada sem cabeça vimos como inserir elementos sempre no início da lista. Vamos agora considerar o caso onde a nova célula deve ser inserida entre uma célula cel e a próxima (apontada por cel).

def insira(self, x, cel):
    '''(LEncadeada, obj, Celula) -> None
    Recebe um objeto x e uma célula cel, não nula.
    Cria uma nova célula contendo x, e a insere após a célula cel.
    '''
    nova = Celula(x)
    nova.prox = cel.prox
    cel.prox = nova

Note como é rápido e simples inserir uma nova célula! Não é preciso abrir espaço movendo os elementos, basta arrumar os ponteiros!

Observe também que a nova célula pode ser inserida antes do primeiro elemento da lista, passando a cabeça da lista como cel, ou mesmo no final da lista, quando cel.prox é None. No entanto, se a lista não tivesse cabeça, não é possível inserir um elemento antes da primeira célula.

23.4.3. Remoção#

Vamos agora estudar como podemos remover uma célula de uma lista encadeada. Podemos imaginar uma situação semelhante a do método insira(), onde o méodo recebe a célula a ser removida. O problema nesse caso é que precisamos receber, na verdade, a célula anterior, aquela que aponta para a célula a ser removida. O seguinte trecho implementa o método remova():

def remova(self, cel_ant):
'''(LEncadeada, Celula) -> None
Recebe uma célula cel_ant, que aponta para uma célula a ser removida.
'''
ant = cel_ant
cel = ant.prox
ant.prox = cel.prox
del cel   # limpa o espaço de memória ocupado por cel

23.4.4. Busca e remoção#

Vamos assumir agora que desejamos remover uma célula que possui o valor x. De novo, uma primeira ideia poderia ser buscar por x na lista mas, uma vez obtendo a célula, como podemos ajustar os ponteiros para que ela possa ser removida? Como no método remova(), para remover a célula contendo x, precisamos obter a célula anterior para atualizar seu ponteiro para pular a célula x, como ilustrado no trecho de código a seguir.

def busque_e_remova(self, x):
    '''(LEncadeada, obj) -> None
    Recebe um objeto x.
    Busca a célula contendo x, e a remove.
    '''

    p = self.cabeca
    q = p.prox

    while q and q.data != x:
        p = q
        q = q.prox

    if q:
        p.prox =  q.prox
        del q   # libera a memória usada por q

23.5. Outros tipos de listas#

Agora que você entendeu como funcionam listas encadeadas usando apenas um ponteiro por célula, há vários tipos de listas encadeadas diferentes (com comportamentos diferentes) que podemos inventar. Por exemplo:

23.5.1. Lista duplamente encadeada#

São listas encadeadas que possuem ponteiros para a próxima célula e também para a anterior. Isso permite a gente percorrer a lista para frente e para trás.

23.5.2. Lista circular#

São listas encadeadas onde o último elemento aponta para o primeiro.

A criação de listas encadeadas com comportamentos diferentes requer alguns cuidados extras na implementação. Por exemplo, em uma lista circular, seria necessário também marcar a célula “rabo” (última célula) além da cabeça? Em que condições uma lista circular estaria vazia? Como inserir e remover elementos nessas listas?

23.6. Aplicações#

Listas encadeadas são estruturas bastante flexíveis, como as próprias listas em Python (tipo list), que permitem, por exemplo, implementar estruturas como Pilhas e Filas, entre outras. Essas ficam como exercícios.

Vamos ilustrar algumas aplicações comuns de listas encadeadas, e aproveitar para introduzir algumas outras estruturas relevantes.

23.6.1. Hashing (ou espalhamento)#

Uma tabela de hassing (ou espalhamento) é usada para armazenar elementos de forma muito eficiente, usada, por exemplo, em dicionários em Python (tipo dict).

Assim, quando usamos uma lista para armarzenar as chaves de um dicionário, o tempo para acessar uma chave depende do número de chaves, ou seja, $O(n)$. Para que o tempo de acesso seja $O(1)$, podemos usar uma função de hashing para espalhar os elementos do conjunto em diferentes entradas de uma tabela.

Se assumirmos que o conjunto de elementos pode assumir valores de um conjunto universo $U$ muito grande, podemos esperar que, para uma tabela com $m$ possíveis entradas, os elementos do conjunto se espalharão de forma uniforme na tabela.

Por exempplo, considere que desejamos armazenar os número de identificação de 100 alunos em uma escola (usando CPF, RG, número de matrícula na escola ou algo assim, representado por um número inteiro). Usando uma tabela com 100 entradas, uma possível função de hash poderia ser:

$h(x) = x \% 100$

Usando essa função de espalhamento, provavelmente a distribuição não seria uniforme (ou seja, essa não é uma boa função de hash!), mas serve para ilustrar que em uma mesma posição da tabela podemos ter mais de um número, ocorrendo portanto uma colisão.

Para tratar colisões podemos usar listas encadeadas. Todos os elementos que compartilham o mesmo valor da função de hashing podem ser colocados em uma lista encadeada, apontada por aquela entrada na tabela.

Mas o que seria uma boa função de hashing?

Idealmente, cada elemento da tabela deveria guarda apenas um elemento do conjunto. Para escolher uma função mais adequada, podemos usar o método de divisão ou de multiplicação.

Pelo método de divisão, para armazenar um elemento $x$ em uma tabela com $m$ elemnetos, podemos usar

$h(x) = x \% m$

onde $m$ é um número primo próximo do número de elementos que serão armazenados na tabela.

Pelo método de multiplicação, para armazenar um elemento $x$ em uma tabela com $m$ elemnetos, podemos usar, podemos usar uma constante $0 < A < 1$ tal que:

$h(x) = \lfloor m \frac{A}{x}\rfloor$

23.7. Matrizes esparsas#

Matrizes são objetos que consomem muita memória. Algumas matrizes no entanto são esparsas, no sentido que a maioria de seus elemento tem um valor único como zero, e apenas alguns elementos são distintos. Matrizes esparsas grandes costumam aparecer em aplicações científicas ou de engenharia envolvendo equações diferenciais particiais. Veja mais aplicações na Wikipedia.

O exemplo abaixo ilustra uma matriz esparsa em Python:

Matrix = [
    [0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0],
    [0, 0, 0, 2, 0],
    [0, 5, 0, 0, 3],
    [0, 0, 4, 0, 0]]

Usando listas encadeadas, podemos representar de forma mais compacta apenas os 5 elementos da matriz $5\times5$ contendo valores diferentes de zero, como:

$((1,2), 1) -> ((2,3), 2) -> ((3,4), 3) -> ((3,1), 5) -> ((4,2), 4) .$

onde o conteúdo de uma célula poderia ser algo como:

class Celula:

    def __init__(self, pos, data):
        self.pos = pos      # tupla com a posição de um elemento
        self.data = data    # conteúdo do elemento
        self.prox = None    # ponteiro para a próxima célula

    def __str__(self):
        if self.prox is None:
            return f"({self.pos}, {self.data}) ."
        else:
            return  f"({self.pos}, {self.data}) -> "

23.8. Exercícios#

Escreva uma função recursiva busqueR que recebe uma lista encadeada sem cabeça e um objeto X. A função deve retornar a célula da lista que contém X, caso exista, ou None, caso contrário.
Altura. A altura de uma célula c em uma lista encadeada é a distância entre c e o fim da lista. Mais exatamente, a altura de c é o número de passos do caminho que leva de c até a última célula da lista. Escreva uma função que calcule a altura de uma dada célula.
Profundidade. A profundidade de uma célula c em uma lista encadeada é o número de passos do único caminho que vai da primeira célula da lista até c. Escreva uma função que calcule a profundidade de uma dada célula.
Escreva uma classe Pilha usando lista encadeada.
Escreva uma classe Fila usando lista encadeada.

DICA: você pode usar uma outra célula “rabo”, para marcar o final da fila.
Escreva uma classe LDE, Lista Duplamente Encadeada com os métodos insira(), busque(), e remova().
Modifique a classe LEncadeada para que o método insira() mantenha a lista ordenada em ordem crescente.

23.9. Onde estamos e para onde vamos?#

Apesar de consumir mais espaço para armazenar ponteiros, listas encadeadas são bastante eficientes para realizar movimentações, inserções e remoções de elementos em qualquer parte da lista.

O uso de listas encadeadas é também um excelente exercício para aprender a manipular ponteiros, apontando para outras células ou percorrendo listas para buscar elementos ou imprimir seu conteúdo.

Continuaremos a ver outras estruturas e aplicações das estruturas vistas ao longo curso em problemas práticos.

23.10. Para saber mais#

Continue sua leitura lendo as seguintes seções do livro [Resolução de Problemas com Algoritmos e Estruturas de Dados usando Python](https://panda.ime.usp.br/panda/static/pythonds_pt/index.html):

[3.19 - Listas](https://panda.ime.usp.br/panda/static/pythonds_pt/03-EDBasicos/19-Listas.html) [3.20 - Lista desordenada](https://panda.ime.usp.br/panda/static/pythonds_pt/03-EDBasicos/20-ListaADT.html) [3.21 - Listas Ligadas](https://panda.ime.usp.br/panda/static/pythonds_pt/03-EDBasicos/21-ListaImplementacao.html)

Recomendamos também a leitura e exercícios da página de [Algoritmos em C](https://www.ime.usp.br/~pf/algoritmos/) do [Professor Paulo Feofiloff](https://www.ime.usp.br/~pf/) sobre [Listas Encadeadas](https://www.ime.usp.br/~pf/algoritmos/aulas/lista.html).

Listas Encadeadas

Contents