Listas encadeadas, pilhas e filas

No vetor, os elementos ficam colados uns nos outros. Hoje vamos espalhá-los pela memória e ligá-los por referências, e usar essa ideia para construir as duas estruturas mais usadas da computação: a pilha e a fila.

10 → 20 → NoneLista encadeadanós ligados por referências ⇄ ↺Dupla e circularandar para trás e dar a volta LIFOPilhao último a entrar sai primeiro FIFOFilao primeiro a entrar sai primeiro ✓ 6Práticaexercícios com correção automática

Navegação: ← → trocam de etapa · V alterna entre etapas e página única · M sumário · F tela cheia · + − tamanho do texto · dentro do código, Ctrl+Enter executa.

Todo código desta aula pode ser editado e executado aqui mesmo. Altere os exemplos à vontade; o botão ↺ restaura o original. Suas alterações ficam salvas neste navegador; em Progresso você pode baixá-las em um arquivo e continuar em outro computador.

As visualizações mostram cada ligação sendo feita: escolha a operação, use Próximo passo ou Animar. Nos exercícios, o botão ✓ Verificar testa seu código com várias entradas.

Vetor ou corrente de nós?

Na aula passada vimos que, no vetor, inserir ou remover no início desloca todos os elementos: O(n).

A lista encadeada resolve isso guardando cada elemento em um nó separado, que pode estar em qualquer lugar da memória. Cada nó guarda:

o valor;
uma referência (prox) para o próximo nó, ou None se for o último.

Para inserir no meio, basta mudar duas referências. Nada é deslocado.

Em Python, uma variável que guarda um objeto guarda na verdade uma referência para ele. É exatamente isso que o campo prox faz: aponta para outro nó.

Percorrendo a lista

Não há índices: só conhecemos o primeiro nó. Para visitar os outros, uma variável p segue as referências até chegar a None.

Esse laço é o “for” das listas encadeadas e aparece em quase toda operação:

p = iniciowhile p is not None:p = p.prox

Esquecer o p = p.prox deixa o laço preso no mesmo nó para sempre. E nunca ande com o próprio inicio: você perderia a entrada da lista.

A classe `ListaEncadeada`

Uma classe guarda a “entrada” da lista e esconde os detalhes dos nós:

inicio: o primeiro nó (ou None, se vazia);
fim: o último nó. Sem ele, inserir no fim exigiria percorrer tudo;
tamanho: atualizado a cada operação, para len() ser O(1).

Os métodos especiais __len__ e __str__ fazem len(lista) e print(lista) funcionarem.

Todo método precisa tratar a lista vazia: é o caso que mais causa erros como AttributeError: 'NoneType' object has no attribute 'prox'.

class No:
    def __init__(self, valor):
        self.valor = valor
        self.prox = None

class ListaEncadeada:
    def __init__(self):
        self.inicio = None
        self.fim = None
        self.tamanho = 0

def inserir_inicio(self, valor):     # O(1)
        novo = No(valor)
        novo.prox = self.inicio
        self.inicio = novo
        if self.fim is None:             # estava vazia
            self.fim = novo
        self.tamanho += 1

def inserir_fim(self, valor):        # O(1) graças a self.fim
        novo = No(valor)
        if self.fim is None:
            self.inicio = novo
        else:
            self.fim.prox = novo
        self.fim = novo
        self.tamanho += 1

def __len__(self):
        return self.tamanho

def __str__(self):
        partes = []
        p = self.inicio
        while p is not None:
            partes.append(str(p.valor))
            p = p.prox
        return " -> ".join(partes + ["None"])

lista = ListaEncadeada()
lista.inserir_fim(20)
lista.inserir_fim(30)
lista.inserir_inicio(10)
print(lista)
print("tamanho:", len(lista))

Lista encadeada passo a passo

Escolha a operação e acompanhe cada linha de código. As etiquetas mostram para onde apontam início, fim, p e ant. A lista resultante vira o ponto de partida da próxima operação.

Compare as operações: inserir no início e no fim não visitam nenhum nó; inserir na posição, buscar e remover precisam andar pela lista. Quantos nós são visitados para remover o último?

Inserir na posição, buscar e remover

Inserir na posição `pos`

Ande até o nó anterior (posição pos − 1) e faça duas ligações, nesta ordem: o novo aponta para o sucessor; o anterior aponta para o novo.

Remover um valor

Ande com dois ponteiros: p procura o valor e ant fica um passo atrás. Achou? ant.prox = p.prox: o anterior “pula” o nó removido.

Casos especiais: remover o primeiro (não há anterior: muda inicio) e remover o último (atualize fim).

inserir na posição → O(n)buscar → O(n)remover → O(n)

class No:
    def __init__(self, valor):
        self.valor = valor
        self.prox = None

class ListaEncadeada:
    def __init__(self):
        self.inicio = None
        self.fim = None
        self.tamanho = 0

def inserir_fim(self, valor):
        novo = No(valor)
        if self.fim is None:
            self.inicio = novo
        else:
            self.fim.prox = novo
        self.fim = novo
        self.tamanho += 1

def inserir_posicao(self, pos, valor):
        if pos <= 0 or self.inicio is None:
            novo = No(valor)
            novo.prox = self.inicio
            self.inicio = novo
            if self.fim is None:
                self.fim = novo
            self.tamanho += 1
        elif pos >= self.tamanho:
            self.inserir_fim(valor)
        else:
            ant = self.inicio
            for _ in range(pos - 1):     # anda até o nó anterior
                ant = ant.prox
            novo = No(valor)
            novo.prox = ant.prox         # 1º: o novo aponta para o sucessor
            ant.prox = novo              # 2º: o anterior aponta para o novo
            self.tamanho += 1

def buscar(self, valor):             # devolve a posição ou -1
        p, i = self.inicio, 0
        while p is not None:
            if p.valor == valor:
                return i
            p, i = p.prox, i + 1
        return -1

def remover(self, valor):
        ant, p = None, self.inicio
        while p is not None and p.valor != valor:
            ant, p = p, p.prox
        if p is None:
            return False                 # não estava na lista
        if ant is None:
            self.inicio = p.prox         # removendo o primeiro
        else:
            ant.prox = p.prox            # o anterior "pula" p
        if p is self.fim:
            self.fim = ant               # removendo o último
        self.tamanho -= 1
        return True

def __str__(self):
        partes, p = [], self.inicio
        while p is not None:
            partes.append(str(p.valor))
            p = p.prox
        return " -> ".join(partes + ["None"])

lista = ListaEncadeada()
for x in [10, 20, 30, 40]:
    lista.inserir_fim(x)
lista.inserir_posicao(2, 25)
print(lista)
print("posição do 30:", lista.buscar(30))
print("remove 10:", lista.remover(10), "|", lista)
print("remove 40:", lista.remover(40), "|", lista, "| fim =", lista.fim.valor)
print("remove 99:", lista.remover(99))

Cuidado com a ordem das ligações

Um nó só continua acessível enquanto alguém aponta para ele. Se você sobrescrever a única referência para o resto da lista, ela se perde.

No exemplo errado, a.prox = novo acontece antes de guardar quem vinha depois de a. Resultado: o 20 e o 30 saem da lista, e novo.prox = a.prox faz o novo nó apontar para ele mesmo, um laço sem fim.

Regra prática: ao inserir, primeiro ligue o nó novo ao resto da lista; depois ligue a lista ao nó novo. Na dúvida, desenhe as setas no papel antes de programar.

Vetor × lista encadeada: quanto custa cada operação

Operação	Vetor (`list`)	Lista encadeada simples (com `fim`)
acessar a posição i	O(1)	O(n): é preciso andar i nós
inserir ou remover no início	O(n): desloca todos	O(1)
inserir no fim	O(1) amortizado	O(1)
remover do fim	O(1)	O(n): precisa achar o penúltimo (O(1) na dupla)
inserir ou remover no meio, já estando no lugar	O(n) deslocamentos	O(1): só troca referências
buscar um valor	O(n), ou O(log n) se ordenado	O(n): busca binária não funciona sem acesso direto
memória extra	pouca (algum espaço reservado)	uma referência por nó (duas na dupla)

Não existe vencedor absoluto. A lista encadeada brilha quando há muitas inserções e remoções nas pontas ou em lugares que já conhecemos; o vetor, quando precisamos de acesso por posição.

Listas encadeadas são a base de pilhas, filas, tabelas hash com encadeamento e listas de adjacência de grafos, que veremos nas próximas aulas.

Lista duplamente encadeada

Cada nó guarda duas referências: prox (para frente) e ant (para trás).

Dá para percorrer nos dois sentidos.
Com um nó em mãos, removê-lo é O(1): ele mesmo sabe quem é o anterior.
Remover do fim também fica O(1): fim.ant é o novo último.

O custo: mais memória por nó e o dobro de ligações para manter corretas em cada operação.

Exemplos: a lista de músicas de um player (anterior/próxima), o histórico do navegador e o collections.deque do Python, que usa uma lista dupla de blocos.

class NoD:
    def __init__(self, valor):
        self.valor = valor
        self.ant = None
        self.prox = None

class ListaDupla:
    def __init__(self):
        self.inicio = None
        self.fim = None

def inserir_fim(self, valor):
        novo = NoD(valor)
        if self.fim is None:
            self.inicio = self.fim = novo
        else:
            novo.ant = self.fim
            self.fim.prox = novo
            self.fim = novo
        return novo

def remover_no(self, no):           # O(1): o nó conhece o anterior
        if no.ant is None:
            self.inicio = no.prox
        else:
            no.ant.prox = no.prox
        if no.prox is None:
            self.fim = no.ant
        else:
            no.prox.ant = no.ant

def frente_para_tras(self):
        p, r = self.inicio, []
        while p is not None:
            r.append(p.valor)
            p = p.prox
        return r

def tras_para_frente(self):
        p, r = self.fim, []
        while p is not None:
            r.append(p.valor)
            p = p.ant
        return r

playlist = ListaDupla()
playlist.inserir_fim("Intro")
faixa2 = playlist.inserir_fim("Faixa 2")
playlist.inserir_fim("Faixa 3")
playlist.inserir_fim("Final")
print(playlist.frente_para_tras())
print(playlist.tras_para_frente())
playlist.remover_no(faixa2)             # sem percorrer nada
print(playlist.frente_para_tras())

Lista dupla passo a passo

As setas ⇄ representam o par prox/ant. Repare que cada inserção no meio mexe em quatro referências, não em duas (e a remoção, em duas, não em uma).

Na remoção, compare com a lista simples (troque o tipo no seletor): a dupla não precisa do ponteiro ant andando atrás de p, porque cada nó já sabe quem vem antes.

Lista circular: o rodízio

Na lista circular, o último nó aponta de volta para o primeiro. Não existe None no fim: andando sempre para frente, damos voltas.

Útil para tudo que funciona em rodízio: a vez dos jogadores, o escalonador de processos de um sistema operacional (cada processo usa a CPU um pouco e passa a vez), playlists em repetição.

Para percorrer uma volta, a condição de parada não é mais p is None (isso nunca acontece!), e sim voltar ao nó inicial.

Pilha: o último a entrar é o primeiro a sair

Uma pilha (stack) só permite mexer no topo, como uma pilha de pratos. Política LIFO: last in, first out.

Operação	Em Python (`list`)	Custo
empilhar (push)	`p.append(x)`	O(1)
desempilhar (pop)	`p.pop()`	O(1)
ver o topo (peek)	`p[-1]`	O(1)
está vazia?	`not p` ou `len(p) == 0`	O(1)

O topo é o fim da list: lá, inserir e remover não deslocam ninguém.

Pilha com nós

Também dá para montar a pilha sobre uma lista encadeada: o topo é o início da lista. Empilhar é inserir no início e desempilhar é remover do início, ambos O(1).

Desempilhar de uma pilha vazia é um erro de quem usa a estrutura. A classe avisa lançando uma exceção com raise, como a list faz em [].pop().

Execute: a última linha tenta desempilhar de uma pilha vazia. Leia a mensagem de erro. Como evitar? Teste p.vazia() antes.

Repare: quem usa a classe só enxerga empilhar, desempilhar, espiar e vazia. Isso é um tipo abstrato de dados: o “o quê” separado do “como”. Trocar a implementação (list ou nós) não muda o resto do programa.

Aplicação: parênteses balanceados

Todo compilador verifica se ( ), [ ] e { } estão bem aninhados. O último que abriu tem de ser o primeiro a fechar: é uma pilha.

Três jeitos de errar, três testes:

fecha com a pilha vazia: (a+b));
fecha com o par errado no topo: ([)];
termina com a pilha não vazia: ((x).

Aplicação: expressões pós-fixas

Na notação pós-fixa (polonesa reversa), o operador vem depois dos operandos: 3 4 + significa 3 + 4. Não precisa de parênteses nem de regras de precedência, e uma pilha avalia tudo em uma passada.

(2 + 3) * 4 → 2 3 + 4 *2 + 3 * 4 → 2 3 4 * +5 + (1 + 2) * 4 − 3 → 5 1 2 + 4 * + 3 −

Calculadoras HP, a máquina virtual do Java e o próprio Python (que compila seu código para instruções de uma pilha) usam essa ideia.

O primeiro valor desempilhado é o segundo operando. Em 8 2 -, desempilhamos 2 e depois 8, e calculamos 8 − 2.

Aplicação: desfazer e refazer

O Ctrl+Z de qualquer editor usa duas pilhas:

cada ação empilha o estado anterior em desfazer;
desfazer tira o topo de desfazer e guarda o estado atual em refazer;
refazer faz o caminho inverso;
uma ação nova esvazia refazer: o futuro alternativo se perde.

O botão “voltar” do navegador funciona do mesmo jeito, com páginas no lugar de textos. E a pilha de chamadas de funções, que veremos em recursão, também.

Fila: o primeiro a entrar é o primeiro a sair

Na fila (queue), quem chega entra no fim e quem é atendido sai da frente. Política FIFO: first in, first out.

Exemplos: fila de impressão, requisições a um servidor, mensagens entre programas, a ordem de visita em um grafo (busca em largura, mais adiante).

Com list, append é O(1), mas tirar da frente com pop(0) desloca todos os outros: O(n). Para filas, use collections.deque, que faz as duas pontas em O(1).

Fila com nós

Sobre uma lista encadeada simples com inicio e fim:

enfileirar = inserir no fim: O(1);
desenfileirar = remover do início: O(1).

Por que não o contrário (entrar no início e sair pelo fim)? Porque remover do fim de uma lista simples exige achar o penúltimo: O(n).

Detalhe fácil de esquecer: quando a fila fica vazia, fim também precisa voltar a None. Senão, o próximo enfileirar liga o nó novo a um nó que já saiu.

class No:
    def __init__(self, valor):
        self.valor = valor
        self.prox = None

class Fila:
    def __init__(self):
        self.inicio = None    # frente: de onde sai
        self.fim = None       # trás: onde entra
        self.tamanho = 0

def enfileirar(self, valor):      # O(1): insere no fim
        novo = No(valor)
        if self.fim is None:
            self.inicio = novo
        else:
            self.fim.prox = novo
        self.fim = novo
        self.tamanho += 1

def desenfileirar(self):          # O(1): remove do início
        if self.inicio is None:
            raise IndexError("fila vazia")
        valor = self.inicio.valor
        self.inicio = self.inicio.prox
        if self.inicio is None:       # esvaziou: fim também
            self.fim = None
        self.tamanho -= 1
        return valor

f = Fila()
for doc in ["relatorio.pdf", "foto.png", "notas.txt"]:
    f.enfileirar(doc)
    print("na fila:", doc)
while f.tamanho > 0:
    print("imprimindo", f.desenfileirar())

Fila circular em vetor

Dá para fazer uma fila O(1) em um vetor de tamanho fixo sem deslocar ninguém: em vez de mover os elementos, movemos o índice da frente. Quando um índice passa do fim do vetor, volta ao 0 com o operador %.

trás = (frente + tamanho) % capacidadefrente = (frente + 1) % capacidade

Enfileire até encher, desenfileire alguns e enfileire de novo: veja os novos elementos ocupando o início do vetor.

Esse é o buffer circular usado em teclados, placas de rede e players de áudio: memória fixa, sem alocação, tudo O(1). A desvantagem é a capacidade limitada.

`collections.deque`: pilha e fila prontas

deque (double-ended queue, “fila de duas pontas”) permite inserir e remover nas duas pontas em O(1). Serve como pilha, como fila ou como os dois.

Método	O que faz
`append(x)` / `pop()`	direita (fim)
`appendleft(x)` / `popleft()`	esquerda (frente)
`d[0]`, `d[-1]`	espia as pontas
`rotate(k)`	gira k posições (circular!)
`deque(maxlen=n)`	guarda só os n últimos

Acessar o meio, d[i], é O(n) em um deque. Ele é feito para as pontas.

Desafio: inverter uma lista encadeada

Inverta a lista sem criar nós novos e sem usar listas do Python: apenas mude os campos prox, para que cada nó aponte para o anterior.

Dica: ande com três referências. p é o nó atual, ant é o que ficou para trás e prox guarda o resto da lista antes de você mudar p.prox.

Depois de resolver: qual é a complexidade? Quanta memória extra ela usa?

1 → 2 → 3 → 4 → None→ 4 → 3 → 2 → 1 → None

Mostrar uma solução

Qual estrutura usar?

Leia a situação para a turma, colete as respostas e só então clique.

Qual será a saída?

Leia o código, escreva sua resposta e só então clique. Errou? Copie o código para o laboratório e execute.

Prática 1: listas encadeadas

Escreva sua solução no editor. ▶ Executar roda com a entrada que você quiser; ✓ Verificar roda os testes automáticos e mostra o que falta. Tente antes de abrir a solução!

1. Tamanho, soma e maior básico

O código já lê os números e monta uma lista encadeada com eles. Percorrendo os nós (sem usar a lista numeros), mostre o tamanho, a soma e o maior valor.

Entrada	Saída esperada
4 8 1	Tamanho: 3 Soma: 13 Maior: 8

Mostrar uma solução

2. Remover todas as ocorrências médio

Complete o método remover_todos(x): ele remove todos os nós com valor x e devolve quantos removeu. Cuidado com os casos em que o removido é o primeiro, o último ou todos. O programa principal já está pronto e testa também se fim ficou certo, inserindo um 0 no fim.

Entrada	Saída esperada
1 2 3 2 4 2	Removidos: 2 Lista: 1 -> 3 -> 4 -> None Com 0 no fim: 1 -> 3 -> 4 -> 0 -> None

class No:
    def __init__(self, valor):
        self.valor = valor
        self.prox = None

class ListaEncadeada:
    def __init__(self):
        self.inicio = None
        self.fim = None

def inserir_fim(self, valor):
        novo = No(valor)
        if self.fim is None:
            self.inicio = novo
        else:
            self.fim.prox = novo
        self.fim = novo

def remover_todos(self, x):
        # remova todos os nós com valor x e devolva quantos foram removidos
        # não esqueça de atualizar self.inicio e self.fim quando preciso
        return 0

def __str__(self):
        partes, p = [], self.inicio
        while p is not None:
            partes.append(str(p.valor))
            p = p.prox
        return " -> ".join(partes + ["None"])

lista = ListaEncadeada()
for v in input("Números: ").split():
    lista.inserir_fim(int(v))
x = int(input("Remover: "))
print("Removidos:", lista.remover_todos(x))
print("Lista:", lista)
lista.inserir_fim(0)
print("Com 0 no fim:", lista)

Mostrar uma solução

class No:
    def __init__(self, valor):
        self.valor = valor
        self.prox = None

class ListaEncadeada:
    def __init__(self):
        self.inicio = None
        self.fim = None

def inserir_fim(self, valor):
        novo = No(valor)
        if self.fim is None:
            self.inicio = novo
        else:
            self.fim.prox = novo
        self.fim = novo

def remover_todos(self, x):
        cont = 0
        ant, p = None, self.inicio
        while p is not None:
            if p.valor == x:
                if ant is None:
                    self.inicio = p.prox     # era o primeiro
                else:
                    ant.prox = p.prox        # ant continua no lugar
                cont += 1
            else:
                ant = p                      # só avança ant se p ficou
            p = p.prox
        self.fim = ant                       # o último que sobrou (ou None)
        return cont

def __str__(self):
        partes, p = [], self.inicio
        while p is not None:
            partes.append(str(p.valor))
            p = p.prox
        return " -> ".join(partes + ["None"])

lista = ListaEncadeada()
for v in input("Números: ").split():
    lista.inserir_fim(int(v))
x = int(input("Remover: "))
print("Removidos:", lista.remover_todos(x))
print("Lista:", lista)
lista.inserir_fim(0)
print("Com 0 no fim:", lista)

Prática 2: pilhas

Use uma list como pilha: só append, pop e [-1].

3. Delimitadores balanceados básico

Leia uma linha de texto e verifique se ( ), [ ] e { } estão balanceados e bem aninhados. Outros caracteres são ignorados. Mostre Balanceada ou Não balanceada.

Entrada	Saída esperada
{[a+(b*c)]-d}	Balanceada
([)]	Não balanceada

Mostrar uma solução

4. Calculadora pós-fixa médio

Leia uma expressão pós-fixa com inteiros não negativos e os operadores + - * / separados por espaço (/ é a divisão inteira, //). Mostre Resultado: R. Se faltarem operandos para algum operador, ou sobrar mais de um valor no fim, mostre Expressão inválida.

Entrada	Saída esperada
3 4 + 2 *	Resultado: 14
2 3	Expressão inválida

Mostrar uma solução

Prática 3: filas

Use collections.deque (ou a sua classe Fila): nada de pop(0) em list.

5. Fila de atendimento médio

Leia comandos, um por linha, até fim:

chega NOME: a pessoa entra na fila (o nome pode ter espaços);
atende: mostra Atendendo: NOME para quem está na frente, ou Fila vazia;
fim: mostra Restam na fila: K e termina.

Mostrar uma solução

6. A roda da eliminação desafio

Há n pessoas numeradas de 1 a n em roda. Começando pela pessoa 1, conta-se k pessoas (a primeira contada é a 1) e a k-ésima sai; a contagem recomeça pela pessoa seguinte. Leia n k e mostre a ordem de eliminação e o sobrevivente (problema de Josephus).

Entrada	Saída esperada
7 3	Eliminados: 3 6 2 7 5 1 Sobrevivente: 4

Dica: em um deque, passar as k − 1 primeiras pessoas da frente para o fim simula a roda.

Mostrar uma solução

Laboratório livre

Espaço para testar ideias durante a aula. Sugestões: acrescente à ListaEncadeada um método remover_fim() e conte quantos nós ele visita; implemente uma pilha com dois métodos e use-a para inverter uma palavra; simule uma fila de impressão em que cada documento leva um tempo diferente.

Listas encadeadas, pilhas e filas

Vetor ou corrente de nós?

Percorrendo a lista

A classe ListaEncadeada

Lista encadeada passo a passo

Inserir na posição, buscar e remover

Inserir na posição pos

Remover um valor

Cuidado com a ordem das ligações

Vetor × lista encadeada: quanto custa cada operação

Lista duplamente encadeada

Lista dupla passo a passo

Lista circular: o rodízio

Pilha: o último a entrar é o primeiro a sair

Pilha com nós

Aplicação: parênteses balanceados

Aplicação: expressões pós-fixas

Aplicação: desfazer e refazer

Fila: o primeiro a entrar é o primeiro a sair

Fila com nós

Fila circular em vetor

collections.deque: pilha e fila prontas

Desafio: inverter uma lista encadeada

Qual estrutura usar?

Qual será a saída?

Prática 1: listas encadeadas

1. Tamanho, soma e maior básico

2. Remover todas as ocorrências médio

Prática 2: pilhas

3. Delimitadores balanceados básico

4. Calculadora pós-fixa médio

Prática 3: filas

5. Fila de atendimento médio

6. A roda da eliminação desafio

Laboratório livre

A classe `ListaEncadeada`

Inserir na posição `pos`

`collections.deque`: pilha e fila prontas