Notebooks

Lista Encadeada

Atividade Estrutura de Dados - Anhanguera - Unidade 1

Kernel inativo

Estrutura de Dados — Atividade Proposta

Lista Encadeada e a função count_nodes

Enunciado. Implementar uma lista encadeada em Python. A atividade consiste em implementar uma função chamada count_nodes, que recebe uma lista encadeada como parâmetro e retorna o número de nós presentes na lista. A função percorre a lista usando um loop enquanto incrementa um contador; ao final do percurso, o valor do contador é retornado.

Uma lista encadeada deve ser criada, alguns elementos adicionados com o método append, a lista impressa, e então count_nodes chamada passando a lista como argumento — exibindo na tela o número de nós presentes.

Espelho da atividade:

class Node:
    def __init__(self, data):

class LinkedList:
    def __init__(self):
    def append(self, data):
    def print_list(self):

def count_nodes(linked_list):

Sobre a nomenclatura: os nomes de classes, métodos e da função seguem exatamente o espelho fornecido (em inglês). Comentários, docstrings e variáveis internas estão em português.

1. O que é uma lista encadeada?

É uma sequência de nós espalhados pela memória, em que cada nó guarda um dado e uma referência para o próximo nó. A lista em si conhece apenas o primeiro nó — o head.

   head
    |
    v
  +------+------+     +------+------+     +------+------+
  | data | next |---->| data | next |---->| data | next |----> None
  |  10  |      |     |  20  |      |     |  30  |      |
  +------+------+     +------+------+     +------+------+

        no 1                no 2                no 3       fim da lista

O None no último nó é o que marca o fim da lista — é exatamente essa condição que os loops de append, print_list e count_nodes vão usar para saber quando parar.

Por que isso importa?

CaracterísticaLista encadeadalist do Python (vetor)
Memórianós espalhados, ligados por referênciasbloco contíguo
Acessar o i-ésimo elementoO(n) — precisa caminhar até eleO(1) — cálculo direto
Inserir no inícioO(1)O(n) — desloca todos os elementos
Saber o tamanhoO(n) — precisa contarO(1) — o tamanho é armazenado
Crescersem realocaçãopode precisar realocar o bloco

A última linha é o motivo de existir esta atividade: em uma lista encadeada não existe um campo com o tamanho, então descobrir quantos nós há só é possível percorrendo a estrutura de ponta a ponta. É esse percurso que a count_nodes implementa.

2. Preparação

O decorador adicionar_metodo é um recurso didático que permite escrever um método por célula, com a explicação em Markdown logo acima. O resultado é idêntico a declarar todos os métodos dentro do corpo da classe — que é como eles aparecem no arquivo .py de entrega.

import time

def adicionar_metodo(classe):
    '''Decorador didatico: anexa a funcao decorada a classe informada como um metodo.'''
    def decorador(funcao):
        setattr(classe, funcao.__name__, funcao)
        return funcao
    return decorador

print("Ambiente pronto.")

3. A classe Node

Um nó é a peça mais simples da estrutura: dois campos, nada mais.

        +-------------------+
        |  data  |   next   |
        +-------------------+
           |          |
           |          +---> referencia para o proximo no (ou None)
           +--------------> o valor armazenado

O next começa sempre como None: um nó recém-criado ainda não está ligado a ninguém. Quem faz essa ligação é o método append.

class Node:
    '''Representa um no (elemento) da lista encadeada.'''

    def __init__(self, data):
        self.data = data      # o dado armazenado no no
        self.next = None      # referencia para o proximo no (None = ainda nao ligado)

    def __repr__(self):
        return f"Node({self.data!r})"

3.1 Teste: encadeando dois nós na mão

Antes de usar a classe LinkedList, vale ver o encadeamento acontecendo manualmente — é literalmente atribuir o next de um nó apontando para outro.

primeiro = Node(10)
segundo = Node(20)

print("Antes de ligar:")
print("  primeiro:", primeiro, "| primeiro.next:", primeiro.next)

primeiro.next = segundo           # aqui nasce o "encadeamento"

print("\nDepois de ligar:")
print("  primeiro:", primeiro, "| primeiro.next:", primeiro.next)
print("  segundo :", segundo, "| segundo.next :", segundo.next, "(fim da lista)")
print("\nAcessando o dado do segundo no a partir do primeiro:", primeiro.next.data)

4. A classe LinkedList

A lista guarda apenas o head — a referência para o primeiro nó. Todo o resto é alcançado seguindo os next.

self.head = None significa lista vazia, e essa é a condição que os métodos verificam antes de qualquer percurso.

class LinkedList:
    '''Lista simplesmente encadeada: guarda apenas a referencia para o primeiro no.'''

    def __init__(self):
        self.head = None      # inicio da lista; None significa lista vazia

4.1 Método append — adicionar no final

O método precisa tratar dois casos:

Caso 1 — lista vazia. Não há para onde caminhar; o novo nó vira o próprio head.

   antes:   head ----> None

   append(10)

   depois:  head ----> [ 10 | None ]

Caso 2 — lista com elementos. É preciso caminhar até o último nó (aquele cujo next é None) e ligar o novo nó nele.

   antes:   head ----> [ 10 | * ] ----> [ 20 | None ]
                                              ^
                                              |
                          no_atual para aqui: next e None = ultimo no

   append(30)

   depois:  head ----> [ 10 | * ] ----> [ 20 | * ] ----> [ 30 | None ]

Atenção à condição do loop: usamos while no_atual.next is not None (e não while no_atual is not None). A diferença é essencial: precisamos parar no último nó para poder alterá-lo, e não passar direto por ele até o None.

Custo: O(n) — o percurso até o fim cresce com o tamanho da lista.

@adicionar_metodo(LinkedList)
def append(self, data):
    '''Adiciona um novo no com 'data' no FINAL da lista. Custo O(n).'''
    novo_no = Node(data)

    # Caso 1: lista vazia -> o novo no passa a ser o inicio
    if self.head is None:
        self.head = novo_no
        return

    # Caso 2: percorre ate o ULTIMO no (aquele cujo next e None)
    no_atual = self.head
    while no_atual.next is not None:
        no_atual = no_atual.next

    # Liga o ultimo no ao novo no
    no_atual.next = novo_no
# Teste do append
lista_de_teste = LinkedList()
print("Lista recem-criada. head =", lista_de_teste.head, "(lista vazia)")

lista_de_teste.append(10)
print("Apos append(10): head =", lista_de_teste.head)

lista_de_teste.append(20)
lista_de_teste.append(30)
print("Apos append(20) e append(30):")
print("  head            ->", lista_de_teste.head)
print("  head.next       ->", lista_de_teste.head.next)
print("  head.next.next  ->", lista_de_teste.head.next.next)
print("  head.next.next.next ->", lista_de_teste.head.next.next.next, "(fim da lista)")

4.2 Método print_list — imprimir a lista

O padrão de percurso aqui é o que se repetirá em count_nodes:

   no_atual = self.head              # comeca no inicio
   while no_atual is not None:       # enquanto nao chegar ao fim
       ...faz algo com no_atual...   # neste caso: guarda o dado
       no_atual = no_atual.next      # avanca

Note que agora a condição é while no_atual is not None — queremos visitar todos os nós, inclusive o último, então só paramos quando a referência vira None.

Custo: O(n).

@adicionar_metodo(LinkedList)
def print_list(self):
    '''Imprime a lista no formato: 10 -> 20 -> 30 -> None. Custo O(n).'''
    elementos = []
    no_atual = self.head

    while no_atual is not None:
        elementos.append(str(no_atual.data))
        no_atual = no_atual.next

    elementos.append("None")        # marca visualmente o fim da lista
    print(" -> ".join(elementos))
# Teste do print_list
lista_de_teste.print_list()

lista_vazia_de_teste = LinkedList()
print("Lista vazia:", end=" ")
lista_vazia_de_teste.print_list()

5. A função count_nodes — o objetivo da atividade

Conforme o enunciado, ela percorre a lista com um loop enquanto incrementa um contador e devolve o contador ao final.

Três detalhes fazem a função funcionar:

  1. contador = 0 — começa do zero, o que já resolve o caso da lista vazia automaticamente;
  2. no_atual = linked_list.head — o ponto de partida é o início da lista;
  3. no_atual = no_atual.next — avançar dentro do loop. Esquecer esta linha é o erro mais comum e produz um loop infinito, já que a condição nunca deixaria de ser verdadeira.

Rastreio do percurso para a lista 10 -> 20 -> 30

Iteraçãono_atual antescontador depoisno_atual depoisContinua?
1Node(10)1Node(20)sim
2Node(20)2Node(30)sim
3Node(30)3Nonenão — loop encerra

Resultado: 3 nós.

A função é definida fora da classe, como uma função independente que recebe a lista por parâmetro — exatamente como pede o espelho da atividade.

def count_nodes(linked_list):
    '''Percorre a lista encadeada com um loop e devolve o numero de nos. Custo O(n).'''
    contador = 0                        # inicializa o contador
    no_atual = linked_list.head         # comeca pelo primeiro no

    while no_atual is not None:         # enquanto nao chegar ao fim da lista
        contador += 1                   # incrementa o contador
        no_atual = no_atual.next        # avanca para o proximo no

    return contador                     # devolve o total contado

5.1 Acompanhando o percurso passo a passo

Versão instrumentada da mesma função, apenas para visualizar o rastreio da tabela acima (não faz parte da entrega).

def count_nodes_com_rastreio(linked_list):
    '''Mesma logica de count_nodes, imprimindo o estado a cada iteracao.'''
    contador = 0
    no_atual = linked_list.head
    iteracao = 0

    print(f"{'iteracao':<10}{'no_atual':<16}{'contador':<10}proximo")
    print("-" * 48)

    while no_atual is not None:
        iteracao += 1
        contador += 1
        proximo = no_atual.next
        print(f"{iteracao:<10}{str(no_atual):<16}{contador:<10}{proximo}")
        no_atual = proximo

    print("-" * 48)
    print(f"Loop encerrado: no_atual e None. Contador final = {contador}")
    return contador


count_nodes_com_rastreio(lista_de_teste)

6. Programa principal da atividade

Exatamente o roteiro pedido: criar a lista, adicionar elementos com append, imprimir a lista, chamar count_nodes passando a lista como argumento e exibir o resultado.

# Cria a lista encadeada
lista = LinkedList()

# Adiciona alguns elementos usando o metodo append
for valor in [10, 20, 30, 40, 50]:
    lista.append(valor)

# Imprime a lista
print("Lista encadeada:")
lista.print_list()

# Chama a funcao count_nodes passando a lista encadeada como argumento
quantidade_de_nos = count_nodes(lista)

# Exibe o resultado na tela
print(f"Numero de nos presentes na lista: {quantidade_de_nos}")

7. Testes

7.1 Casos de borda

Os dois casos que costumam quebrar implementações de lista encadeada: a lista vazia e a lista com um único elemento.

lista_vazia = LinkedList()
print("Lista vazia .............:", end=" ")
lista_vazia.print_list()
print("  count_nodes ->", count_nodes(lista_vazia), "(deve ser 0)")

lista_de_um = LinkedList()
lista_de_um.append("Pikachu")
print("\nLista com um elemento ...:", end=" ")
lista_de_um.print_list()
print("  count_nodes ->", count_nodes(lista_de_um), "(deve ser 1)")

7.2 A lista aceita qualquer tipo de dado

O campo data não impõe tipo algum — cada nó pode guardar coisas diferentes.

Repare na saída: o último None é o marcador de fim de lista, mas o penúltimo é um dado de verdade armazenado em um nó. Visualmente ficam iguais, e ainda assim count_nodes conta 5 nós corretamente — porque ela olha as referências, não os dados.

lista_mista = LinkedList()
for valor in ["texto", 42, 3.14, True, None]:
    lista_mista.append(valor)

lista_mista.print_list()
print("count_nodes ->", count_nodes(lista_mista), "(deve ser 5)")

7.3 Listas maiores

for tamanho in [10, 100, 1000, 5000]:
    lista_grande = LinkedList()
    for numero in range(tamanho):
        lista_grande.append(numero)
    print(f"  {tamanho:>5} elementos adicionados -> count_nodes = {count_nodes(lista_grande)}")

7.4 Bateria de verificações automáticas

verificacoes = {
    "lista vazia devolve 0": count_nodes(LinkedList()) == 0,
    "lista com 1 elemento devolve 1": count_nodes(lista_de_um) == 1,
    "lista com 5 elementos devolve 5": count_nodes(lista) == 5,
    "lista com tipos variados devolve 5": count_nodes(lista_mista) == 5,
    "count_nodes nao altera a lista": (count_nodes(lista), count_nodes(lista)) == (5, 5),
    "head da lista vazia e None": LinkedList().head is None,
    "append mantem a ordem de insercao": [no.data for no in [lista.head, lista.head.next]] == [10, 20],
}

for descricao, resultado in verificacoes.items():
    print(f"  [{'OK ' if resultado else 'FALHOU'}] {descricao}")

print("\nTodos os testes passaram!" if all(verificacoes.values()) else "\nHa testes falhando.")

8. Análise de complexidade

OperaçãoCustoPor quê
Node.__init__O(1)duas atribuições
appendO(n)percorre até o último nó
print_listO(n)visita todos os nós
count_nodesO(n)visita todos os nós, gastando O(1) de memória

Consequência prática: construir uma lista com n chamadas de append custa 1 + 2 + ... + n = O(n²), e não O(n). Isso é visível no teste abaixo — dobrar o tamanho multiplica o tempo de construção por cerca de 4, enquanto o tempo de count_nodes apenas dobra.

print(f"{'n':>7} {'construcao (ms)':>18} {'count_nodes (ms)':>18}")
print("-" * 45)

for tamanho in [1000, 2000, 4000, 8000]:
    inicio = time.perf_counter()
    lista_medida = LinkedList()
    for numero in range(tamanho):
        lista_medida.append(numero)
    tempo_construcao = (time.perf_counter() - inicio) * 1000

    inicio = time.perf_counter()
    total = count_nodes(lista_medida)
    tempo_contagem = (time.perf_counter() - inicio) * 1000

    print(f"{tamanho:>7} {tempo_construcao:>18.2f} {tempo_contagem:>18.2f}")

9. Extensões (além do exigido)

As três variações abaixo não fazem parte da entrega — servem para comparar abordagens e entender melhor as escolhas da implementação principal.

9.1 append em O(1) guardando a cauda

Se a lista também guardar uma referência para o último nó (tail), o append deixa de percorrer a lista e passa a custar O(1). Construir a lista vira O(n) em vez de O(n²).

class LinkedListComCauda(LinkedList):
    '''Variacao que guarda tambem o ultimo no, tornando o append O(1).'''

    def __init__(self):
        super().__init__()
        self.tail = None                 # referencia para o ULTIMO no

    def append(self, data):
        novo_no = Node(data)
        if self.head is None:
            self.head = novo_no
        else:
            self.tail.next = novo_no     # liga direto, sem percorrer nada
        self.tail = novo_no


inicio = time.perf_counter()
lista_com_cauda = LinkedListComCauda()
for numero in range(8000):
    lista_com_cauda.append(numero)
tempo_com_cauda = (time.perf_counter() - inicio) * 1000

print(f"Construcao de 8000 nos com cauda: {tempo_com_cauda:.2f} ms")
print(f"count_nodes -> {count_nodes(lista_com_cauda)}")
print("(compare com o tempo de construcao da versao O(n) na tabela anterior)")

9.2 Versão recursiva da contagem

Elegante, mas pior na prática: gasta O(n) de memória na pilha de chamadas e estoura o limite de recursão do Python (padrão: 1000) em listas grandes. A versão iterativa do enunciado gasta O(1).

def count_nodes_recursivo(no):
    '''Conta os nos recursivamente a partir de um no. Custo O(n) de tempo E de memoria.'''
    if no is None:
        return 0
    return 1 + count_nodes_recursivo(no.next)


print("Recursivo  ->", count_nodes_recursivo(lista.head))
print("Iterativo  ->", count_nodes(lista))

try:
    lista_profunda = LinkedList()
    for numero in range(5000):
        lista_profunda.append(numero)
    count_nodes_recursivo(lista_profunda.head)
except RecursionError:
    print("\nRecursionError com 5000 nos - a versao iterativa lida com isso sem problema:",
          count_nodes(lista_profunda))

9.3 Por que não guardar um atributo size?

Bastaria incrementar um contador dentro do append para que o tamanho fosse conhecido em O(1) — é o que faz o list do Python. Mas isso anularia o objetivo da atividade, que é justamente exercitar o percurso da estrutura com um loop.

Vale saber que existe o trade-off: O(1) na consulta, ao custo de manter o contador sincronizado em toda inserção e remoção — e é aí que aparecem os bugs quando a estrutura cresce.

10. Exercícios propostos

  1. prepend(data) — insira um nó no início da lista. Por que essa operação é O(1), enquanto o append é O(n)?
  2. search(data) — devolva True se o valor existir na lista. Qual o custo no pior caso?
  3. delete(data) — remova o primeiro nó com aquele valor (cuidado com o caso em que o nó removido é o head).
  4. reverse() — inverta a lista alterando apenas os ponteiros next, sem criar nós novos.
  5. Nó do meio — encontre o elemento central percorrendo a lista uma única vez (dica: dois ponteiros, um avançando o dobro do outro).
  6. Detectar ciclo — se o next do último nó apontar para um nó anterior, count_nodes entra em loop infinito. Implemente uma versão que detecte isso (algoritmo de Floyd).
# Espaco para os exercicios
# Exercicio 1 - prepend

@adicionar_metodo(LinkedList)
def prepend(self, data):
    '''Insere um no no INICIO da lista. Custo O(1).'''
    # Insira aqui seu codigo
    pass


lista_exercicio = LinkedList()
for valor in [20, 30]:
    lista_exercicio.append(valor)

lista_exercicio.prepend(10)
lista_exercicio.print_list()
print("Esperado: 10 -> 20 -> 30 -> None | count_nodes =", count_nodes(lista_exercicio))

11. Conclusão

A atividade foi cumprida com as classes Node e LinkedList (com os métodos append e print_list) e a função independente count_nodes, que percorre a lista com um loop while enquanto incrementa um contador e devolve o total ao final.

O ponto conceitual: em uma lista encadeada o tamanho não é armazenado — os nós só conhecem seus vizinhos imediatos. Descobrir quantos são exige caminhar do head até o None final, o que torna a contagem O(n) de tempo e O(1) de memória.

Referências

  • Material da disciplina de Estrutura de Dados — listas encadeadas.
  • CORMEN, T. H. et al. Introduction to Algorithms, capítulo sobre estruturas de dados elementares.

Execução em Python roda no seu navegador via Pyodide (WebAssembly). Pacotes como numpy, pandas e matplotlib são suportados; outros exigem wheels puro-Python via micropip.