Lista simplesmente ligada

Prévia do material em texto

Lista simplesmente ligada
Podemos implementar ED na linguagem C de pelo menos duas formas: 
Customização Dúvidas ao tutorUnidade 2 / Aula 1
O que são as
Estruturas de Dados
do tipo Lista?
100%
Lista simplesmente ligada
Função para lista vazia
Vídeoaula: Estruturas de Dados
Inserção de elemento em lista
Impressão de elementos em lista
Lista duplamente ligada
Vídeoaula: Operações com Listas
Ligadas – Inserção

Fe
ed
ba
ck
Formas de implementar ED na linguagem C. Fonte: o autor.
Estruturas de dados ligadas alocam espaços na memória do computador à medida
que novos elementos precisam ser adicionados e os desalocam à medida que não
precisamos mais deles. Por isso, é dito que as estruturas de dados ligadas
proporcionam uma melhor utilização da memória.
Observe a ilustração de uma lista simplesmente ligada na figura – Ilustração de uma
lista ligada.
Unidade 2 / Aula 1
O que são as
Estruturas de Dados
do tipo Lista?
100%
Lista simplesmente ligada
Função para lista vazia
Vídeoaula: Estruturas de Dados
Inserção de elemento em lista
Impressão de elementos em lista
Lista duplamente ligada
Vídeoaula: Operações com Listas
Ligadas – Inserção
Fe
ed
ba
ck
Ilustração de uma lista ligada - Fonte: elaborada pelos autores.
Uma lista simplesmente ligada consiste em uma sequência de elementos,
denominados nós (representados por retângulos com uma seta em uma de suas
extremidades na figura - Ilustração de uma lista ligada). 
Cada nó possui uma informação (valor que aparece dentro do retângulo) e um
ponteiro para o próximo nó da lista (seta na extremidade direita do retângulo). O
último nó da lista aponta para NULL, representando que não existe um próximo nó
na lista.
Unidade 2 / Aula 1
O que são as
Estruturas de Dados
do tipo Lista?
100%
Lista simplesmente ligada
Função para lista vazia
Vídeoaula: Estruturas de Dados
Inserção de elemento em lista
Impressão de elementos em lista
Lista duplamente ligada
Vídeoaula: Operações com Listas
Ligadas – Inserção
Fe
ed
ba
ck
A lista propriamente dita é representada apenas por um ponteiro para o primeiro nó
dessa lista, chamado de Início na figura – Ilustração de uma lista ligada. Uma lista
simplesmente ligada tem esse nome porque cada nó da estrutura tem apenas um
ponteiro para o próximo nó da lista. 
Existe também o conceito de lista duplamente ligada, que veremos mais à frente
nesta aula. Em uma lista duplamente ligada, cada nó apresenta dois ponteiros, um
que aponta para o próximo nó e outro que aponta para o nó anterior.
_____
🔁 Assimile
Observando a figura – Ilustração de uma lista ligada –, não é difícil entender que,
em uma lista vazia, o ponteiro “Início” apontará para NULL, uma vez que não há
elementos na lista. 
Assim, já podemos imaginar que a operação “vazia”, que retorna se a lista está vazia
ou não, deve comparar se o ponteiro “Início” é igual a NULL ou não.
_______
Vamos, neste momento, passar à parte prática e implementar nossa primeira ED,
uma lista simplesmente ligada.
Unidade 2 / Aula 1
O que são as
Estruturas de Dados
do tipo Lista?
100%
Lista simplesmente ligada
Função para lista vazia
Vídeoaula: Estruturas de Dados
Inserção de elemento em lista
Impressão de elementos em lista
Lista duplamente ligada
Vídeoaula: Operações com Listas
Ligadas – Inserção
Fe
ed
ba
ck
Começaremos criando algumas structs. O conceito já foi apresentado, mas, para
relembrar, structs permitem ao programador criar variáveis compostas heterogêneas
na linguagem C.
Com structs você consegue criar variáveis que podem armazenar mais de uma
informação, assim como os vetores.
Mas, ao contrário dos vetores, que só permitem armazenar valores de um mesmo
tipo, structs oferecem a possibilidade de armazenarmos valores de tipos diferentes,
tais como números e caracteres, entre outros (por isso são chamadas de variáveis
compostas heterogêneas). 
Na linguagem C, a criação de uma estrutura deve ser feita fora de qualquer função e
deve apresentar a seguinte sintaxe:
Unidade 2 / Aula 1
O que são as
Estruturas de Dados
do tipo Lista?
100%
Lista simplesmente ligada
Função para lista vazia
Vídeoaula: Estruturas de Dados
Inserção de elemento em lista
Impressão de elementos em lista
Lista duplamente ligada
Vídeoaula: Operações com Listas
Ligadas – Inserção
Fe
ed
ba
ck
Sintaxe da criação de uma estrutura na linguagem C. Fonte: elaborado pelo autor.
<nome> é o nome da estrutura, por exemplo, cliente, carro, fornecedor, nó, lista e
outros. As variáveis internas são os campos da struct, nos quais se deseja guardar as
informações.
Agora que revisamos rapidamente o conceito de struct, vamos criar uma struct para
representar cada nó da nossa lista simplesmente ligada.
Como vimos anteriormente, cada nó contém uma informação e um ponteiro para o
próximo nó. Assim, a struct para o nó de lista ficará assim:
Unidade 2 / Aula 1
O que são as
Estruturas de Dados
do tipo Lista?
100%
Lista simplesmente ligada
Função para lista vazia
Vídeoaula: Estruturas de Dados
Inserção de elemento em lista
Impressão de elementos em lista
Lista duplamente ligada
Vídeoaula: Operações com Listas
Ligadas – Inserção
Fe
ed
ba
ck
struct No {
 int info;
 struct No* proximo;
};
 
Por questão de simplicidade, estamos considerando que a informação presente em
um nó (definida pela variável “info”) é um número inteiro. Contudo, você pode
armazenar qualquer tipo de informação que desejar, como strings, números reais, ou
até mesmo uma variável de outro tipo struct.
É possível ver que o campo “proximo” é um ponteiro que aponta para outro nó da
estrutura. Para declarar um ponteiro, utilizamos o operador * após o tipo da variável.
Uma vez criada a struct que representa um nó da lista, precisamos de uma struct
para representar a lista propriamente dita. Essa struct deve conter, como campos, um
ponteiro para o primeiro nó da lista e a quantidade de elementos presentes nessa
lista. O código dessa struct é o seguinte:
Unidade 2 / Aula 1
O que são as
Estruturas de Dados
do tipo Lista?
100%
Lista simplesmente ligada
Função para lista vazia
Vídeoaula: Estruturas de Dados
Inserção de elemento em lista
Impressão de elementos em lista
Lista duplamente ligada
Vídeoaula: Operações com Listas
Ligadas – Inserção
Fe
ed
ba
ck
Código da struct. Fonte: elaborado pelo autor.
Partiremos agora para a implementação do comportamento que “dará vida” a nossa
ED, isto é, as funções que nos permitirão criar uma lista, inserir, remover e consultar
elementos nela, entre outras coisas.
Avalie este conteúdo Escolha de 1 a 5 estrelas
Unidade 2 / Aula 1
O que são as
Estruturas de Dados
do tipo Lista?
100%
Lista simplesmente ligada
Função para lista vazia
Vídeoaula: Estruturas de Dados
Inserção de elemento em lista
Impressão de elementos em lista
Lista duplamente ligada
Vídeoaula: Operações com Listas
Ligadas – Inserção
Fe
ed
ba
ck
Conteúdo anterior Próximo conteúdoUnidade 2 / Aula 1
O que são as
Estruturas de Dados
do tipo Lista?
100%
Lista simplesmente ligada
Função para lista vazia
Vídeoaula: Estruturas de Dados
Inserção de elemento em lista
Impressão de elementos em lista
Lista duplamente ligada
Vídeoaula: Operações com Listas
Ligadas – Inserção
Fe
ed
ba
ck