André MarascaEnsino · Pesquisa · Dados

Lista de exercícios

Exercícios resolvidos: listas dinâmicas encadeadas

Exercícios curtos e progressivos sobre ponteiros, memória, lista circular e pool de nós.

Esta lista serve para exercitar os conceitos da aula. Não há entrega, nota ou correção individual.

Resolva um exercício por vez e consulte sua solução logo depois. Nas soluções, “Resposta esperada” significa apenas uma resposta completa para comparação.

Exercício 1: interpretar o typedef

Considere:

typedef struct elemento *Lista;
Lista *li;

Complete:

  1. Lista é outro nome para ______.
  2. li possui o tipo ______.
  3. *li possui o tipo ______.
Solução

Explicação

O typedef dá um nome menor a um tipo existente. Neste caso, Lista representa um ponteiro para struct elemento. Como li adiciona outro asterisco, ele é um ponteiro para ponteiro.

Resposta esperada

  1. Lista é outro nome para struct elemento *.
  2. li possui o tipo struct elemento **.
  3. *li possui o tipo struct elemento *.

Exercício 2: distinguir os estados da lista

Associe cada condição a um estado:

  1. li == NULL
  2. li != NULL && *li == NULL
  3. li != NULL && *li != NULL

Estados:

  • a lista existe e possui elementos;
  • a lista existe, mas está vazia;
  • a lista não existe.
Solução

Explicação

li aponta para o bloco que armazena o ponteiro para o início da lista. Só é permitido consultar *li quando li != NULL.

Resposta esperada

CondiçãoEstado
li == NULLa lista não existe
li != NULL && *li == NULLa lista existe, mas está vazia
li != NULL && *li != NULLa lista existe e possui elementos

Exercício 3: localizar os blocos de memória

Considere:

Lista *li = malloc(sizeof(Lista));
if (li != NULL) {
    *li = NULL;
}

Responda:

  1. O que foi reservado pelo malloc?
  2. *li = NULL libera memória?
  3. Qual tamanho deve ser usado para reservar um novo elemento?
  4. Em uma lista com dois elementos, qual deve ser a ordem dos free?
Solução

Explicação

O primeiro malloc reserva apenas o bloco que guarda o ponteiro para o início da lista. Um elemento é outro bloco, com os dados e a ligação para o próximo elemento.

*li = NULL somente grava um ponteiro nulo. Essa atribuição não chama free.

Resposta esperada

  1. Foi reservado um bloco do tamanho de Lista, capaz de armazenar o ponteiro para o início.
  2. Não.
  3. sizeof(struct elemento).
  4. Primeiro, devem ser liberados os dois elementos. Por último, deve ser liberado o bloco apontado por li.

Exercício 4: rastrear inserções ordenadas

Comece com uma lista vazia e insira, nesta ordem:

30, 10, 20

Após cada inserção, escreva a sequência da lista. Na inserção de 20, identifique o elemento anterior e o elemento atual.

Solução

Explicação

Cada valor deve ocupar a posição que preserva a ordem crescente. Ao inserir 20, o percurso para entre 10 e 30.

Resposta esperada

30 -> NULL
10 -> 30 -> NULL
10 -> 20 -> 30 -> NULL

Antes da religação para inserir 20:

  • o elemento anterior contém 10;
  • o elemento atual contém 30.

Exercício 5: rastrear remoções

Comece com:

10 -> 20 -> 30 -> NULL

Execute, nesta ordem:

  1. remova 10;
  2. remova 30;
  3. tente remover 99.

Após cada operação, escreva a sequência e informe se ocorreu free.

Solução

Explicação

Ao remover 10, muda o ponteiro para o início da lista. Ao remover 30, muda a ligação armazenada no elemento 20. O valor 99 não existe, portanto não há endereço válido para liberar.

Resposta esperada

OperaçãoResultadoMemória
remover 1020 -> 30 -> NULLum free
remover 3020 -> NULLum free
remover 9920 -> NULLnenhum free

Durante a sequência, três elementos existiam, dois foram liberados e um continuou alcançável pela lista.

Exercício 6: corrigir uma inserção no início

O trecho abaixo deveria inserir no no início:

*li = no;
no->prox = *li;

Identifique o erro e escreva as duas linhas na ordem correta.

Solução

Explicação

A primeira linha substitui a referência para o início antigo. Na segunda linha, *li já contém no. Assim, no->prox aponta para o próprio no, e a lista antiga fica inacessível.

Resposta esperada

no->prox = *li;
*li = no;

A ligação para o início antigo precisa ser preservada antes da mudança de *li.

Exercício 7: corrigir uma remoção

Considere:

free(no);
*link = no->prox;

Identifique o erro e escreva as linhas na ordem correta.

Solução

Explicação

Depois de free(no), não se pode consultar no->prox. Isso seria um uso após liberação.

Resposta esperada

*link = no->prox;
free(no);

A lista deve ser religada enquanto no ainda é válido.

Exercício 8: encerrar um percurso circular

Em uma lista circular não vazia, fim->prox aponta para inicio. Corrija o laço:

Elem *no = li->inicio;
while (no != NULL) {
    printf("%d\n", no->dados.matricula);
    no = no->prox;
}
Solução

Explicação

O percurso circular não alcança NULL. Uma volta termina quando o ponteiro retorna ao endereço inicial. O do while também processa corretamente uma lista com um único elemento.

Resposta esperada

Elem *no = li->inicio;
do {
    printf("%d\n", no->dados.matricula);
    no = no->prox;
} while (no != li->inicio);

Exercício 9: classificar custos

Classifique o pior caso como O(1)O(1) ou O(n)O(n):

  1. acessar o índice k em um vetor;
  2. acessar o índice k em uma lista simples;
  3. inserir no início de uma lista simples;
  4. buscar uma matrícula em uma lista sem índice auxiliar;
  5. inserir no final de uma lista circular que possui o ponteiro fim;
  6. remover o último elemento de uma lista simplesmente encadeada.
Solução

Explicação

Uma alteração de ligações custa tempo constante quando o ponto da alteração já é conhecido. Quando é necessário localizar uma posição seguindo os próximos elementos, o custo depende do tamanho da lista.

Resposta esperada

OperaçãoPior caso
acessar índice em vetorO(1)O(1)
acessar índice em listaO(n)O(n)
inserir no início da listaO(1)O(1)
buscar matrículaO(n)O(n)
inserir no final com fimO(1)O(1)
remover o último da lista simplesO(n)O(n)

Exercício 10: escolher uma representação

Escolha vetor ou lista encadeada para cada cenário:

  1. capacidade pequena e fixa, com muitas consultas por índice;
  2. quantidade variável, com muitas inserções no início e remoções por valor.

Justifique cada escolha com as operações predominantes.

Solução

Explicação

A representação deve favorecer as operações mais frequentes. O vetor oferece acesso direto por índice. A lista cresce por elementos separados e permite alterações por religação.

Resposta esperada

  1. Vetor, devido à capacidade fixa e ao acesso por índice em O(1)O(1).
  2. Lista encadeada, devido à quantidade variável e às alterações por ligações.

Exercício 11: criar o descritor circular

Um descritor possui:

Elem *inicio;
Elem *fim;
size_t qtd;

Defina os valores dos três campos:

  1. logo após a criação;
  2. depois da primeira inserção.

Também informe para onde aponta fim->prox depois da primeira inserção.

Solução

Explicação

Uma lista recém-criada não possui elementos. Na primeira inserção, o mesmo elemento ocupa as duas extremidades e aponta para si próprio.

Resposta esperada

Estadoiniciofimqtdfim->prox
após criarNULLNULL0não pode ser acessado
após inserir o primeironovo elementonovo elemento1inicio

Exercício 12: inserir nas extremidades da lista circular

Considere uma lista circular não vazia.

  1. Quais ligações mudam ao inserir no início?
  2. Quais ligações mudam ao inserir no final?
  3. Qual igualdade deve continuar verdadeira nas duas operações?
Solução

Explicação

O novo início aponta para o início antigo. Depois, inicio muda e o último elemento precisa retornar ao novo início.

No final, o último elemento antigo aponta para o novo. O novo elemento se torna fim e retorna ao início.

Resposta esperada

Inserção no início:

no->prox = li->inicio;
li->inicio = no;
li->fim->prox = li->inicio;

Inserção no final:

no->prox = li->inicio;
li->fim->prox = no;
li->fim = no;

Após as duas operações, deve valer:

li->fim->prox == li->inicio

Exercício 13: consultar uma lista circular

Escreva a condição de parada para buscar uma matrícula em uma lista circular não vazia. A busca pode terminar de duas formas:

  1. a matrícula foi encontrada;
  2. o percurso completou uma volta.
Solução

Explicação

Não se pode esperar por NULL. O endereço do primeiro elemento funciona como referência para detectar uma volta completa.

Resposta esperada

Elem *no = li->inicio;
do {
    if (no->dados.matricula == matricula) {
        return no;
    }
    no = no->prox;
} while (no != li->inicio);

return NULL;

Antes desse trecho, a função deve tratar separadamente a lista inexistente ou vazia.

Exercício 14: remover de uma lista circular

Indique o tratamento necessário em cada caso:

  1. remover o único elemento;
  2. remover o primeiro de uma lista com mais de um elemento;
  3. remover o último de uma lista com mais de um elemento.
Solução

Explicação

O caso com um único elemento esvazia o descritor. Nos outros casos, a circularidade precisa ser restaurada depois da mudança de uma extremidade.

Resposta esperada

CasoAtualização necessária
único elementoinicio = NULL, fim = NULL e qtd = 0
primeiroinicio recebe o sucessor e fim->prox recebe o novo inicio
últimoo predecessor se torna fim e fim->prox recebe inicio

Em todos os casos, o elemento removido deve ser liberado exatamente uma vez.

Exercício 15: inserir ordenadamente na lista circular

Uma lista circular está ordenada por matrícula. Ela contém:

18 -> 32 -> 45 -> retorna a 18

Para cada valor, informe a posição de inserção:

  1. 10;
  2. 25;
Solução

Explicação

Os valores menores que o primeiro entram no início. Os maiores que o último entram no final. Os demais exigem a localização do intervalo correto.

Resposta esperada

ValorPosiçãoEstado resultante
10início10, 18, 32, 45
25entre 18 e 3218, 25, 32, 45
50final18, 32, 45, 50

Cada linha representa um teste independente com a lista inicial apresentada no enunciado.

Exercício 16: verificar a implementação circular

Use estes alunos:

18, Carla
32, Ana
45, Bruno
25, Diego

Execute:

  1. insira 18 no início;
  2. insira 32, 45 e 25 no final;
  3. remova o primeiro e o último;
  4. remova 32;
  5. insira 25 ordenadamente.

Registre a sequência após os passos 2, 3 e 5.

Solução

Explicação

Este exercício reúne as operações anteriores somente para verificar se elas preservam a ordem esperada e a ligação circular. Depois de cada operação em uma lista não vazia, confirme fim->prox == inicio.

Resposta esperada

Após o passo 2: 18, 32, 45, 25
Após o passo 3: 32, 45
Após o passo 5: 25, 45

A implementação completa para comparação está em:

Exercício 17: reconhecer a finalidade de um pool de nós

Este é um conceito novo. Não se pressupõe conhecimento anterior sobre pool de nós. Os próximos exercícios ensinam uma parte do mecanismo por vez.

Neste material, um pool de nós é um conjunto fixo de nós reservado antes do processamento. Quando o programa precisa de um nó temporário, ele adquire um nó disponível. Depois do uso, ele devolve esse mesmo nó para que possa ser reutilizado.

Escolha a conclusão correta:

  1. cada aquisição cria um novo nó com malloc;
  2. os mesmos nós podem ser adquiridos, devolvidos e reutilizados.
Solução

Explicação

O pool evita criar e destruir memória durante cada uso. Os nós já existem e apenas mudam entre os estados “disponível” e “em uso”.

Resposta esperada

A conclusão correta é a 2: os mesmos nós podem ser adquiridos, devolvidos e reutilizados.

Exercício 18: distinguir os estados de um nó

Em um pool inicializado, cada nó está em exatamente um destes estados:

  • disponível: pode ser adquirido;
  • em uso: já foi adquirido e ainda não foi devolvido.

Complete:

  1. adquirir move o nó de disponível para ______;
  2. devolver move o nó de em uso para ______.
Solução

Explicação

Adquirir não cria o nó. A operação somente retira um nó do conjunto de disponíveis. Devolver também não destrói o nó. A operação o coloca novamente nesse conjunto.

Resposta esperada

  1. Adquirir move o nó de disponível para em uso.
  2. Devolver move o nó de em uso para disponível.

Exercício 19: interpretar a lista de nós disponíveis

O pool usa uma lista encadeada simples para registrar somente os nós disponíveis. O campo next_free só representa uma ligação enquanto o nó está disponível.

free_start
    |
    v
  [0] -> [1] -> [2] -> NULL

Responda:

  1. quais nós estão disponíveis;
  2. para qual nó free_start aponta;
  3. o que NULL indica nesse desenho.
Solução

Explicação

free_start é o ponteiro para o início da lista de nós disponíveis. Cada next_free leva ao próximo nó disponível. NULL marca o fim dessa lista.

Resposta esperada

  1. Os nós 0, 1 e 2 estão disponíveis.
  2. free_start aponta para o nó 0.
  3. NULL indica que não existe outro nó disponível depois do nó 2.

Exercício 20: reconhecer o vetor do pool

No código, PoolItem é o tipo de cada nó. storage é um ponteiro usado para acessar um vetor criado dinamicamente.

pool->storage = (PoolItem *)malloc(capacity * sizeof(PoolItem));

Com capacity == 3, essa única chamada cria três posições contíguas:

storage[0]   storage[1]   storage[2]

Indique os índices válidos desse vetor.

Solução

Explicação

A multiplicação calcula o espaço de três elementos do tipo PoolItem. Embora storage seja declarado como ponteiro, a região reservada pode ser acessada com a notação de vetor.

Resposta esperada

Os índices válidos são 0, 1 e 2. O pool realizou uma única chamada a malloc para criar esse vetor.

Exercício 21: formar a lista inicial de disponíveis

storage é o vetor criado no exercício anterior. Agora, cada posição disponível aponta para sua sucessora no mesmo vetor. A última posição aponta para NULL porque não existe outra posição depois dela.

Complete as duas lacunas:

pool->storage[0].next_free = &pool->storage[1];
pool->storage[1].next_free = &pool->storage[2];
pool->storage[2].next_free = __________;
pool->free_start = __________;
Solução

Explicação

As posições são vizinhas no vetor, mas a disponibilidade será percorrida pelas ligações next_free. O ponteiro free_start indica onde essa lista começa.

Resposta esperada

pool->storage[2].next_free = NULL;
pool->free_start = &pool->storage[0];

O estado formado é 0 -> 1 -> 2 -> NULL.

Exercício 22: distinguir o vetor da lista de disponíveis

O pool usa duas formas de organização ao mesmo tempo:

  • storage permite alcançar todas as posições reservadas;
  • free_start permite alcançar somente as posições disponíveis.

Escolha a explicação correta:

  1. a lista encadeada substitui o vetor;
  2. o vetor guarda os nós, e a lista encadeada registra quais nós estão disponíveis.
Solução

Explicação

O vetor é o armazenamento físico. A lista encadeada é uma organização lógica construída sobre algumas posições desse vetor. Uma posição em uso continua em storage, mas deixa de aparecer no percurso iniciado em free_start.

Depois de algumas aquisições e devoluções, as posições livres podem aparecer em uma ordem como 2 -> 0. Sem a lista, seria necessário procurar uma posição livre no vetor ou manter outra estrutura de controle. A lista de disponíveis permite retirar e devolver um nó pelo início sem percorrer o vetor.

Resposta esperada

A explicação correta é a 2: o vetor guarda todos os nós, e a lista encadeada registra somente os nós disponíveis.

Usar apenas o vetor seria suficiente se o problema exigisse somente acesso por índice. O pool acrescenta a lista porque precisa localizar rapidamente um nó disponível.

Exercício 23: entender o limite do pool

Um pool com capacidade 3 permite que a lista da aplicação varie entre zero e três nós sem chamar malloc durante as operações.

Responda:

  1. a lista pode possuir dois nós?
  2. a lista pode possuir quatro nós usando somente esse pool?
Solução

Explicação

A quantidade em uso pode variar, mas o pool impõe um limite máximo. Portanto, ele preserva a flexibilidade de uma lista encadeada dentro de uma capacidade conhecida.

Essa escolha é útil quando o sistema conhece um limite seguro e quer evitar alocações repetidas. Quando não existe um limite aceitável, um pool fixo pode não ser a representação adequada.

Resposta esperada

  1. Sim. A lista pode possuir dois nós, deixando uma posição disponível.
  2. Não. Uma quarta posição não existe nesse pool.

O pool não torna o crescimento ilimitado. Ele troca crescimento ilimitado por memória previsível e reutilização.

Exercício 24: tratar o esgotamento do pool

Neste material, pool_acquire não usa malloc como alternativa. Quando todos os nós estão em uso:

pool->free_start == NULL

Indique o que a função deve retornar e o que deve acontecer com a lista da aplicação.

Solução

Explicação

Sem nó disponível, a inserção não pode continuar. A função informa essa condição com NULL. O código que pediu o nó deve detectar o resultado antes de alterar qualquer ligação.

Outros sistemas poderiam rejeitar, adiar ou registrar a operação. Usar malloc como alternativa também seria possível em outro projeto, mas eliminaria a garantia de que não haverá alocação durante o processamento.

Resposta esperada

pool_acquire deve retornar NULL. A lista da aplicação deve permanecer inalterada.

Exercício 25: interpretar quando o pool de nós vale a pena

O pool de nós não é melhor em todos os casos. Ele realmente combina duas limitações:

  • possui uma capacidade máxima, como um vetor;
  • não oferece acesso direto por índice, como uma lista encadeada.

O ganho aparece quando o programa precisa de previsibilidade. Todos os nós são reservados uma única vez. Durante o uso, o programa adquire e devolve esses nós sem chamar malloc ou free. Além disso, uma inserção ou remoção pode mudar somente as ligações, sem deslocar os outros nós.

Compare as escolhas:

  • use um vetor simples quando o acesso por índice for importante;
  • use uma lista com malloc quando a quantidade de nós precisar crescer sem um limite definido previamente;
  • use um pool de nós quando existir um limite seguro e for importante saber quanta memória será usada e evitar alocações repetidas durante o processamento.

Responda:

  1. Qual é a principal vantagem do pool de nós?
  2. Qual é a principal desvantagem do pool de nós?
Solução

Explicação

A vantagem não está no acesso aos elementos nem no crescimento da lista. Ela está no comportamento previsível: a memória é reservada uma vez, e os mesmos nós são reutilizados. Isso pode ser importante em sistemas que precisam evitar o tempo variável e as possíveis falhas de uma nova alocação durante cada inserção.

A desvantagem é aceitar uma capacidade máxima e manter a complexidade das ligações. Se o programa precisa principalmente de acesso por índice, um vetor simples costuma ser melhor. Se precisa crescer sem um limite definido previamente, uma lista que usa malloc para cada novo nó costuma ser mais adequada.

Resposta esperada

  1. Vantagem: o pool torna o uso de memória previsível e evita chamadas repetidas a malloc e free durante o processamento. A lista encadeada ainda permite inserir e remover nós por meio das ligações, sem deslocar os outros nós.
  2. Desvantagem: a quantidade máxima de nós precisa ser definida previamente. Além disso, a lista continua sem acesso direto por índice e exige mais código do que um vetor simples.

O pool de nós só compensa quando essa previsibilidade vale mais do que o crescimento livre e o acesso por índice.

Exercício 26: consultar a implementação pronta em C

Este exercício é opcional e serve somente para consulta. A implementação não será exigida em prova nem em outra avaliação. Não é necessário copiar o código nem entender cada linha.

Os três arquivos mostram a versão completa:

Ao consultar o código, responda somente: durante o uso normal, pool_acquire e pool_release chamam malloc ou free?

Solução

Explicação

pool_init reserva todos os nós no início. Depois, pool_acquire entrega um nó disponível e pool_release devolve esse nó ao pool. pool_destroy libera a memória no encerramento.

Resposta esperada

Não. Durante o uso normal, pool_acquire e pool_release apenas reutilizam os nós já reservados. A alocação ocorre em pool_init, e a liberação ocorre em pool_destroy.

O aprofundamento termina aqui. O objetivo desta consulta é apenas mostrar como as ideias dos exercícios 17 a 25 aparecem em uma implementação completa.