Classe Node e Construção de Listas
Defina uma dataclass Node, construa listas conectando nós manualmente e escreva funções auxiliares de inserção, exclusão e impressão para visualizar as mudanças nos ponteiros.
Classe Node e Construção de Listas é uma aula grátis de DSA Interview Prep no CoddyKit. Esta é a aula 1 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de DSA Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de DSA Interview Prep inclui 4 aulas no total.
O Que é uma Lista Encadeada
Uma lista encadeada é uma sequência de nós em que cada nó armazena um valor e um ponteiro para o próximo nó. Ao contrário dos vetores, os nós ficam espalhados na memória — não há acesso O(1) baseado em índice. Em troca, você obtém inserção e remoção O(1) em qualquer posição conhecida, sem deslocar elementos.
Em Python, representamos cada nó com uma classe pequena que contém val e next. Encadear os nós forma a lista; o next do último nó é None para indicar o fim.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Build: 1 -> 2 -> 3 -> None
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
# Traverse and print
curr = head
while curr:
print(curr.val, end=' -> ')
curr = curr.next
print('None')Construindo Listas a partir de Vetores
Em entrevistas, muitas vezes você receberá uma lista e deverá construir sua equivalente em lista encadeada, ou fazer o contrário. Vale a pena memorizar as funções auxiliares build e to_list: build encadeia nós a partir de um vetor, e to_list percorre a lista para coletar valores e facilitar a verificação.
Construir uma lista encadeada a partir de n elementos leva O(n) de tempo e O(n) de espaço. Usar um nó cabeça fictício simplifica os casos-limite em que o primeiro nó pode mudar.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def build(arr):
dummy = ListNode(0)
curr = dummy
for val in arr:
curr.next = ListNode(val)
curr = curr.next
return dummy.next
def to_list(head):
result = []
while head:
result.append(head.val)
head = head.next
return result
head = build([1, 2, 3, 4, 5])
print(to_list(head)) # [1, 2, 3, 4, 5]Inserir no Início e em tail
Inserir um novo nó no início é O(1): crie o nó, faça seu next apontar para o início antigo e retorne o novo nó como início. Inserir em tail exige percorrer a lista até o último nó (O(n)) e então encadear o novo nó.
Usar um nó cabeça fictício elimina o caso especial de uma lista vazia nas duas inserções, pois dummy.next é sempre o início real.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def insert_head(head, val):
return ListNode(val, head) # O(1)
def insert_tail(head, val):
new_node = ListNode(val)
if not head:
return new_node
curr = head
while curr.next:
curr = curr.next
curr.next = new_node
return head
head = None
for v in [1, 2, 3]:
head = insert_tail(head, v)
head = insert_head(head, 0)
curr = head
while curr:
print(curr.val, end=' -> ')
curr = curr.next
print('None') # 0 -> 1 -> 2 -> 3 -> NoneExcluir um Nó por Valor
Para excluir o primeiro nó com um determinado valor, mantenha um ponteiro prev uma posição atrás de curr. Quando curr.val == target, defina prev.next = curr.next para ignorar o nó. Um nó cabeça fictício é especialmente útil aqui, pois elimina o caso especial de excluir o verdadeiro nó inicial — prev pode sempre começar no nó fictício.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def delete_val(head, target):
dummy = ListNode(0)
dummy.next = head
prev, curr = dummy, head
while curr:
if curr.val == target:
prev.next = curr.next
break
prev, curr = curr, curr.next
return dummy.next
def to_list(h):
r = []
while h:
r.append(h.val)
h = h.next
return r
head = None
for v in [1, 2, 3, 2, 4]:
dummy2 = ListNode(v)
dummy2.next = head
head = dummy2 # build in reverse for speed
head = delete_val(head, 2)
print(to_list(head))Visualizando Alterações nos Ponteiros
Um erro comum é perder o controle de um nó ao atualizar ponteiros. Sempre salve next antes de sobrescrevê-lo: saved = curr.next; depois, faça a reatribuição. Desenhe a lista como caixas conectadas por setas e simule cada atualização de ponteiro no papel antes de programar. Essa abordagem visual evita erros acidentais de ponteiro nulo durante as entrevistas.
Lembre-se: em Python, reatribuir curr.next não afeta o próprio curr, mas perder a referência a curr.next antes de salvá-la significa que você não poderá mais percorrer a lista para a frente.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Demonstrate safe pointer update
def swap_first_two(head):
if not head or not head.next:
return head
first = head
second = head.next
# Save third before losing the reference
third = second.next
# Rewire
second.next = first
first.next = third
return second
from functools import reduce
nodes = [ListNode(i) for i in range(1, 5)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = swap_first_two(nodes[0])
curr = head
while curr:
print(curr.val, end=' ')
curr = curr.next
# 2 1 3 4Listas Encadeadas Simples ou Duplas
Uma lista encadeada simples armazena apenas um ponteiro next; o percurso ocorre em uma única direção. Uma lista duplamente encadeada armazena tanto prev quanto next, permitindo percorrer a lista para trás em O(1) e excluir um nó em O(1) quando se tem uma referência direta a ele (sem necessidade do laço que acompanha o ponteiro anterior).
O collections.deque do Python é implementado como uma lista duplamente encadeada, por isso oferece appendleft e popleft em O(1). Em entrevistas, você implementará listas encadeadas simples; listas duplamente encadeadas aparecem no projeto de caches LRU.
class DLNode:
def __init__(self, val=0):
self.val = val
self.prev = None
self.next = None
# Build doubly linked: 1 <-> 2 <-> 3
a, b, c = DLNode(1), DLNode(2), DLNode(3)
a.next = b; b.prev = a
b.next = c; c.prev = b
# Traverse forward
curr = a
while curr:
print(curr.val, end=' <-> ')
curr = curr.next
print('None')
# Traverse backward from c
curr = c
while curr:
print(curr.val, end=' <-> ')
curr = curr.prev
print('None')Comprimento, tail e Funções Auxiliares de Impressão
Três funções utilitárias que você deve ter à disposição durante qualquer entrevista sobre listas encadeadas: length(head) conta os nós em O(n), tail(head) retorna o último nó em O(n), e print_list(head) formata a lista para depuração. Ter essas funções prontas permite que você se concentre no algoritmo principal em vez de reimplementar a lógica auxiliar.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def length(head):
count = 0
while head:
count += 1
head = head.next
return count
def tail(head):
while head and head.next:
head = head.next
return head
def print_list(head):
parts = []
while head:
parts.append(str(head.val))
head = head.next
print(' -> '.join(parts) + ' -> None')
# Build and test
nodes = [ListNode(i) for i in [10, 20, 30, 40]]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = nodes[0]
print('Length:', length(head))
print('Tail:', tail(head).val)
print_list(head)Configuração de Dois Ponteiros em Listas Encadeadas
A técnica de dois ponteiros é tão importante para listas encadeadas quanto para vetores, mas os ponteiros são nós da lista, e não índices. As configurações comuns incluem um ponteiro lento e um rápido (o rápido avança duas vezes mais depressa) para encontrar pontos médios e detectar ciclos, e um par de predecessor e atual para exclusão e reversão.
Inicialize sempre os dois ponteiros de forma explícita e trate com cuidado a verificação de término nulo — fast and fast.next evita erros de ponteiro nulo quando o ponteiro rápido está próximo do fim.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Find middle node using slow-fast pointers
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # for even length, returns second of two middle nodes
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
print(find_middle(nodes[0]).val) # 3 (middle of 1->2->3->4->5)O Padrão do Nó Cabeça Fictício
O padrão do nó cabeça fictício (nó sentinela) é um dos truques mais úteis em problemas de listas encadeadas. Ao colocar no início um nó fictício com valor 0, você nunca precisa tratar separadamente uma lista vazia ou uma alteração no verdadeiro nó inicial. Sua resposta será sempre dummy.next. Esse padrão aparece em problemas de mesclagem de listas ordenadas, remoção do n-ésimo elemento a partir do fim, particionamento de listas e muitos outros.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Remove all nodes with val == target (may include head)
def remove_all(head, target):
dummy = ListNode(0)
dummy.next = head
curr = dummy
while curr.next:
if curr.next.val == target:
curr.next = curr.next.next # skip the node
else:
curr = curr.next
return dummy.next
def to_list(h):
r = []
while h:
r.append(h.val)
h = h.next
return r
nodes = [ListNode(v) for v in [1, 2, 6, 3, 4, 5, 6]]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = remove_all(nodes[0], 6)
print(to_list(head)) # [1, 2, 3, 4, 5]Complexidade de Tempo e Espaço
A maioria das operações em listas encadeadas tem as seguintes complexidades. Acesso por índice: O(n) — é necessário percorrer a lista desde o início. Inserção ou exclusão em um nó conhecido: O(1) — basta religar os ponteiros. Inserção ou exclusão na posição k: O(k) — primeiro, percorra a lista. Busca: O(n) — no pior caso, percorre a lista inteira. O espaço é O(1) para todas as operações realizadas no próprio local (sem contar estruturas de dados adicionais).
Compare com os vetores: eles oferecem acesso O(1), mas inserção e exclusão O(n) devido ao deslocamento dos elementos. Listas encadeadas são melhores quando inserções e exclusões em posições arbitrárias são frequentes.
Dicas para Entrevistas sobre Listas Encadeadas
Antes de escrever qualquer código de lista encadeada, desenhe a lista visualmente com caixas e setas. Confirme os casos-limite em voz alta: lista vazia, nó único, comprimento par ou ímpar. Use um nó cabeça fictício para simplificar as condições de limite. Sempre verifique if not head logo no início. Depois de programar, percorra sua solução com uma lista de três nós para detectar erros de ponteiro antes que o entrevistador os encontre.
A maioria dos erros em listas encadeadas vem de uma destas três fontes: esquecer de salvar next antes de sobrescrevê-lo, cometer um erro de deslocamento de uma posição na condição de término ou não tratar o caso-limite de alteração do nó inicial — o nó fictício elimina completamente o terceiro problema.
Verificação Rápida
Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação desta lição.
Recapitulação da Lição
Nesta lição, você aprendeu: uma lista encadeada é construída a partir de objetos Nó com campos de valor e próximo, o padrão do nó cabeça fictício elimina os casos-limite de alteração do nó inicial, e a configuração de dois ponteiros lento-rápido é a base para encontrar pontos médios e detectar ciclos. A seguir, abordaremos a reversão de uma lista encadeada — um dos problemas de ponteiros mais comuns em entrevistas.
Perguntas Frequentes
A aula “Classe Node e Construção de Listas” é grátis?
Sim — o texto completo de “Classe Node e Construção de Listas” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de DSA Interview Prep, atualize para CoddyKit PRO. O curso de DSA Interview Prep inclui 4 aulas no total.
O que vou aprender em “Classe Node e Construção de Listas”?
Defina uma dataclass Node, construa listas conectando nós manualmente e escreva funções auxiliares de inserção, exclusão e impressão para visualizar as mudanças nos ponteiros. Você pratica DSA Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar DSA Interview Prep?
Nenhuma experiência prévia é necessária. DSA Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 1 de 4.
Quanto tempo leva a aula “Classe Node e Construção de Listas”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de DSA Interview Prep?
Sim. Cada aula de DSA Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Classe Node e Construção de Listas
- Revertendo uma Lista Encadeada
- Detecção de Ciclos com o Algoritmo de Floyd
- Intercalar, Dividir e Encontrar o N-ésimo a Partir do Fim