Poderia a operação de inserção de elementos ser implementada em uma lista ligada simples com complexidade temporal
? E a remoção?
Passo 1
Vou deixar claro o que está sendo perguntado e quais suposições vou usar (sem resolver ainda). O enunciado faz duas perguntas:
- A operação de inserção em uma lista ligada simples pode ser implementada com complexidade temporal
? - A operação de remoção em uma lista ligada simples pode ser implementada com complexidade temporal
?
Informações / suposições que usarei (padrão para listas ligadas simples):
- Cada nó tem pelo menos dois campos: um campo de dado e um ponteiro para o próximo nó (chamarei esse ponteiro de
). - Há uma referência (ponteiro) para o início da lista, chamada
. - Às vezes existe também uma referência para o fim da lista, chamada
; quando for relevante direi explicitamente se temos ou não. - Quando eu falar de
refiro-me ao número de nós na lista. - A resposta depende do caso: inserir/remover no início, no fim, após um nó conhecido, ou procurar por um valor/índice antes de operar.
Passo 2
Explicando bem o básico: o que é uma lista ligada simples e o que significa
.
- Estrutura do nó: cada nó contém (1) dado e (2)
que aponta para o próximo nó ou para nulo se for o último. Em pseudolinguagem: Nodo { dado; next }. -
aponta para o primeiro nó (ou é nulo se a lista estiver vazia). - Se houver
, ele aponta para o último nó (ou é nulo se a lista estiver vazia). - O que é
? Significa “tempo constante”: o número de passos elementares executados não cresce com . Exemplos de operações típicas que são : atribuição de ponteiro, acessar um campo do nó, atualizar um ponteiro.
Passo 3
Inserção: caso geral e ideia principal.
- “Inserir” é uma operação ambígua sem especificar onde. Precisamos distinguir:
- inserir no início (head),
- inserir no fim (tail),
- inserir logo após um nó cujo ponteiro já conhecemos,
- inserir em uma posição por índice ou “inserir antes de um nó que só conhecemos por valor” (ou seja, precisamos procurar).
- A diferença é que, quando já temos o local (o ponto de ligação), a operação muitas vezes só exige poucas atribuições de ponteiro — então pode ser
. Se for necessário localizar o ponto (percorrer), há custo de busca que costuma ser .
Passo 4
Inserção no início (head): passo a passo e por que é
.
- Operação (passos elementares):
- Alocar novo nó
. - Colocar o dado em
. - Fazer
. - Fazer
. - Se a lista estava vazia e existe
, ajustar .
- Alocar novo nó
- Contagem: são um número fixo de atribuições e testes independentes de
. Logo a complexidade é . - Conclusão: inserir na cabeça da lista ligada simples é sempre
.
Passo 5
Inserção imediatamente após um nó conhecido: também
.
- Situação: já existe um ponteiro para o nó
depois do qual queremos inserir. - Operação:
- Alocar novo nó
. -
. -
. - Se
era o tail, atualizar .
- Alocar novo nó
- Novamente são um número fixo de atribuições; portanto é
. - Observação: para este caso precisa existir o ponteiro para
. Se apenas se dá um índice ou um valor, primeiro é preciso encontrar — aí vem custo de busca.
Passo 6
Inserção no fim (tail): dois cenários diferentes.
- Sem ponteiro
: deve-se percorrer a lista a partir de até encontrar o último nó; essa travessia custa . Depois faz-se operações constantes para ligar o novo nó. Portanto, sem a inserção no fim é . - Com ponteiro
: é possível em : - Alocar
. -
. -
(se a lista não estiver vazia). -
. - Se lista vazia, ajustar também
.
- Alocar
- Conclusão: inserir no fim é
se e somente se a estrutura mantém explicitamente um ponteiro ; caso contrário é .
Passo 7
Inserção em posição arbitrária por índice ou por valor (quando é necessário procurar): custo
.
- Se o enunciado/pedido for "insira o novo elemento na posição
" ou "insira após o nó que contém o valor ", normalmente é preciso percorrer a lista para localizar a posição ou o predecessor. Esse percurso pode inspecionar até nós no pior caso, logo a operação é . - Resumo para inserção:
- Inserir no início:
. - Inserir após nó conhecido:
. - Inserir no fim:
se há , senão . - Inserir em posição por índice/valor:
(por causa da busca).
- Inserir no início:
Passo 8
Remoção: casos análogos e cuidados.
- “Remover” também precisa de especificação: remover o primeiro nó, remover o último, remover um nó cujo predecessor é conhecido, remover por valor/índice, ou remover dado apenas um ponteiro para o próprio nó.
- Remover o primeiro nó (head):
- Guardar
. -
. - Se usar
e lista ficou vazia, ajustar . - Liberar
.
- Guardar
- São etapas constantes → remoção da cabeça é
.
Passo 9
Remoção após nó conhecido e remoção por busca.
- Remover logo após um nó
conhecido (ou seja, temos o predecessor): -
. -
. - Se
era , atualizar . - Liberar
.
-
- Isso é
. - Remover por valor ou por posição quando é necessário localizar o nó ou seu predecessor exige passeio (busca), portanto é
.
Passo 10
Remover quando só se tem o ponteiro para o nó a ser removido (sem o predecessor): o truque do “copiar o próximo”.
- Situação: recebido ponteiro
para o nó a ser removido, mas não temos ponteiro para o predecessor. - Se
existe (ou seja, não é o último nó), podemos fazer: - Copiar o dado de
para . - Fazer
. - Liberar o nó que era
originalmente.
- Copiar o dado de
- Essa operação evita precisar do predecessor e é
. - Limitações importantes:
- Não funciona se
for o último nó (tail), porque não há para copiar. Para remover o último nó sem predecessor é preciso percorrer a lista para achar o predecessor → . - Tem implicações semânticas: o endereço do nó removido permanece (ou seja, objetos que guardavam o ponteiro antigo para
continuam válidos, mas o conteúdo foi substituído). Em algumas situações essa substituição de dados não é aceitável. - Se os dados tiverem recursos complexos (por exemplo, ponteiros internos, identificadores únicos) o “copiar” pode ser problemático.
- Não funciona se
Passo 11
Resumo prático e recomendações (trade-offs).
- Inserção e remoção podem ser
em muitos casos práticos: - inserir/remover na cabeça: sempre
, - inserir após nó conhecido:
, - remover após nó conhecido:
, - inserir no fim:
se mantiver .
- inserir/remover na cabeça: sempre
- Operações que exigem localizar um nó ou seu predecessor são
. - Se o objetivo é permitir remoção em
de qualquer nó dado apenas um ponteiro para ele (inclusive do último), a solução padrão é usar lista duplamente ligada (cada nó tem e ), porque então pode-se ajustar ponteiros do predecessor e sucessor sem busca adicional. - Em provas: sempre especifique qual caso está considerando (head, tail com/sem ponteiro, nó conhecido, busca por valor). A resposta “sim” ou “não” depende do caso.
Resposta
Inserção: depende do caso — pode ser
(inserir na cabeça, inserir após um nó conhecido, ou inserir no fim se existir ponteiro
), mas é
se for necessário localizar a posição por busca (por exemplo inserir por índice ou por valor).
Remoção: também depende — pode ser
(remover a cabeça; remover após predecessor conhecido; ou, com o truque de copiar, remover um nó não final dado o ponteiro para ele), mas é
se for necessário encontrar o predecessor (por exemplo remover o último nó sem
ou remover por valor/index que exige busca).