Listas em C - O que é e como funciona uma List

Estrutura de dados dinâmica realmente não é o assunto mais fácil da linguagem C, é realmente necessário estudar bastante para entender perfeitamente os conceitos e ideias por trás deste assunto.

Visando clarear mais a mente de nossos estudantes, a apostila C Progressivo vai explicar o conceito de lista apenas com figuras e explicações escritas, nada de código por hora.

Obtenha sua certificação em C e entre no Mercado de Trabalho!

Lista encadeada - O nó

Vamos tentar explicar, sem pressa e com detalhes, cada uma das ideias e elementos necessários para se estudar e trabalhar com estruturas de dados dinâmicas.

O objetivo deste tutorial de nossa apostila é que você entenda, na sua cabeça, como tudo funciona.
E esta é uma dica valiosa: antes de programar e fazer seu aplicativo rodar, ele tem que rodar perfeitamente na sua cabeça.  Ou seja: antes de começar, entenda e faça na mente.

Vamos chamar cada struct, a partir de agora, de .

Por exemplo, criamos uma struct com algumas variáveis e um ponteiro que aponta para o seu próprio tipo. Logo, quando criamos tal nó, é da seguinte forma:
Listas simplesmente encadeadas em C
Pronto. Esse nó está em algum ponto da memória, e seu ponteiro aponta para um endereço de memória qualquer.

Agora vamos declarar outro nó, o Elemento 2. Seu funcionamento e criação (alocando memória de maneira dinâmica) são idênticos ao Elemento 1, e essa estrutura, ou nó, está em um lugar qualquer da memória, bem como seu ponteiro aponta para um local aleatório, chamado de lixo.

Veja:

Dois nós declarados

Conectando os nós de uma lista

Agora temos que 'ligar', 'conectar' ou 'encadear' esses dois nós.

Lembre-se que o ponteiro é para o tipo do nó, então podemos fazer com que o ponteiro do primeiro nó aponte para o segundo nó! E como o nó foi alocado de maneira dinâmica, ele também é representado por um endereço de memória, que será usado pelo ponteiro do elemento 1.

No nó 1, fazemos:
ptr = Elemento2;

Porém, o ponteiro do segundo nó ainda aponta para outro endereço de memória (lixo).

Para podermos identificar que esse elemento é o último da lista, vamos fazer com que o ponteiro do nó 2 aponte para NULL, veja como ficou nossa lista encadeada:

Apostila de C para download
 Pronto! Temos uma lista simples, com duas estruturas conectadas.




Inserindo nó ao final da lista

Vamos colocar outro nó na lista?

Primeiro declaramos o elemento 3.

Apostila de linguagem C para download

Como queremos que ele fique depois do elemento 2, fazemos com que o ponteiro deste segundo elemento aponte para o nó 3. E para identificar o nó 3 como o último da lista, fazemos seu ponteiro apontar para NULL. Veja:

Apostila complete grátis

 Simples, não? Agora raciocine como seria para colocar um quarto nó ao final da lista.
O que você faria? Quem apontaria para quem? E qual ponteiro vai apontar para NULL agora?

Conectando nós no início da lista

Nos exemplos acima, conectamos nós ao final da lista.
Basicamente fazemos com que o nó antigo, que era o último, aponte para o novo nó, e o ponteiro desse novo nó aponte para NULL: é o nosso algoritmo para inserir um nó ao fim da lista.

Agora iremos aprender como inserir o nó no COMEÇO da lista, na primeira posição!
Como antes, primeiro declaramos um novo nó, o Elemento 4.
Ele está em algum lugar na memória, perdido e solitário, assim como o seu ponteiro.

Apostila online gratuita para download de C


Precisamos, agora, conectar esse novo nó na lista.
Porém, ninguém vai apontar para ele desta vez. Agora é ele que vai apontar para o primeiro nó da lista, que é sempre chamado de head (ou cabeça, em português).

Ou seja, no ponteiro do novo nó, fazemos:
ptr = Elemento1 ou ptr=cabeca

Curso de C
E pronto! Adicionamos o nó 4 no início da lista. Simples e óbvio, não?

Inserindo um nó no meio da lista

Vimos que para adicionar um nó no início da lista, basta o novo primeiro nó apontar para o antigo primeiro nó. Já para colocar ao fim da lista, simplesmente apontávamos o ponteiro do último nó para o novo nó.

E para adicionar no meio da lista? Fazemos as duas coisas.
Por exemplo, para colocar o nó na segunda posição: primeiro declaramos o nó 4, que está em um lugar qualquer da memória.
Agora fazemos com que o primeiro ponteiro deixe apontar para o nó 2 e aponte para o novo nó, o nó 4.
E agora fazemos com que o nó 4 aponte para o nó 2.



Tutorial de C completo


Excluindo um nó da lista

Para excluir um nó de uma lista, devemos fazer com que esse nó não aponte para ninguém e que ninguém da lista aponte para ele. Ou seja, ele não pode se relacionar com nenhum nó, deve se isolar.

No exemplo anterior, se quisermos tirar o nó 2, é só fazermos os passos contrários.

Como programar em C

O nó 4 apontava para o 2. Vamos cortar essa relação: agora o nó 4 não vai mais apontar par ao nó 2, e sim para o nó 3. Podemos ainda fazer com que o nó 2 que apontava para o nó 3, aponte para outro lugar.

Pronto. Ninguém aponta para o nó 2, e ele não aponta para ninguém.
O nó 1 aponta para o 4, que aponta para o 3, que aponta para NULL. Cadê o nó 2? Não faz mais parte, vai ficar lá perdido na memória, pois não vai se relacionar com ninguém da lista.


Como ser programador C

E para excluir o primeiro nó?
Ora, o nó 1 só faz apontar para o nó 2. Se fizermos ele apontar para NULL, ele sai da lista, já que ele é o primeiro e ninguém aponta para ele.

E para excluir o último nó ?
Basta fazer com que o penúltimo nó, que apontava para o último, deixe de apontar para ele e aponte para NULL. Pronto, agora ninguém aponta pro último e ele ficou apontando para NULL, logo, não tem mais nenhuma relação com a lista encadeada.

Simples, bonitinho, com desenhos e tudo fazendo sentido.
Se não entender, leia, releia até entender. Só podemos ir para o próximo passo depois de entendido perfeitamente este tutorial de nosso curso.

Caso tenha entendido, é hora de partir para os códigos em C.
No próximo tutorial vamos ensinar como programar uma lista encadeada em C. Até lá.

4 comentários:

steniovm disse...

em "Inserindo um nó no meio da lista" voce escreveu:
Agora fazemos com que o primeiro ponteiro deixe apontar para o nó 2 e aponte para o novo nó, o nó 4.
E agora fazemos com que o nó 4 aponte para o nó 2.

não seria ao contrário? primeiro fazer o nó 4 apontar para 2 e depois o nó 1 apontar para 4, porque se fizermos o nó 1 apontar para o 4 de cara não vamos ter ninguem apontando para o 2 e ele ficará perdido sem termos acesso a ele.

outra coisa, quando excluimos um nó temos que fazer quem está apontando pra ele deixar de apontar pra ele, até ai blz, mas e o contrário? queria saber se realmente é necessario fazer ele apontar pra null? qual o problema de excluir um nó que aponta pra outro?

Apostila C Progressivo disse...

Bem notado steniovm,

Porém a gente tá falando aqui só por cima. Mas na hora de implementar mesmo, nós vamos usar ponteiros auxiliares para ficarem armazenando endereços para que não se percam, e outros para ficarem percorrendo a lista.

Por exemplo, para tirar um nó da lista vamos usar dois ponteiros que vão percorrer a lista até acharmos o elemento que vamos retirar. Fazemos um deles apontar para esse elemento que vai sair da lista, e o outro ponteiro aponta para o elemento anterior.

Então, à rigor, não é exatamente como está exibido aqui. Não que esteja errado, apenas tentamos dar uma simplificado pois o assunto não é dos mais simples (dá um baita trabalho tentar explicar essas coisas também).

Sobre o nó que vai ser excluído, bem notado novamente. Mas não, não é obrigado ele apontar para null. Tanto que nem fizemos isso na implementação da lista.

Mas pode ser importante por motivos de segurança. Imagina que esse nó que excluímos sejam os dados de um cliente de um banco ou outra coisa interna de uma empresa. Alguém mal intencionado pode pegar as informações desse nó retornado e descobrir que ele tem um ponteiro apontando pros outros elementos da lista.
E esses elementos da lista podem ser dados privados, que o invasor vai passar a ter acesso.

Para um programa simples como o nosso, não vai importar muita coisa. Mas imagine fazendo isso em um sistema web, com PHP por exemplo, seria uma grande falha que facilmente seria explorada.

O ideal é, antes de retornar o nó, você fazer com que ninguém aponte para o nó e que o nó não aponte para ninguém da lista. Assim as coisas vão ficar mais seguras e privadas, pois ninguém fora da lista vai ter acesso a ela.

Grato pelos comentários, acabamos adicionando informações interessantes sobre o assunto.

Ricardo Brusch disse...

Obrigado pelo tempo dedicado em escrever este tutorial. Estou com dificuldades nesta matéria na faculdade, e como faço por EAD fica ainda mais difícil assimilar as "dicas" e "ajudas" dos tutores e colegas.

Seu texto foi muito bem construído e bem explicativo, me ajudou bastante! Vou continuar olhando outros tutoriais para captar bem a matéria.

Obrigado mais uma vez!

Gabriella Lopes disse...

Boa tarde!
Notei que algumas imagens estão faltando nesse e em alguns outros tópicos do "Tutorial de Estrutura de dados III: Estruturas Dinâmicas". Se puder, atualize as páginas!

Além disso, gostaria de agradecer por todo o conteúdo do C Progressivo, já aprendi muito com ele! Obrigada!

Gostou desse tutorial de C?
Sabia que o acervo do portal C Progressivo é o mesmo, ou maior que, de um livro ou curso presencial?
E o melhor: totalmente gratuito.

Mas para nosso projeto se manter é preciso divulgação.
Para isso, basta curtir nossa página no Facebook e/ou clicar no botão +1 do Google.
Contamos e precisamos de seu apoio.