<Direto ao Ponto 49> As listas
- #Informática Básica
Artigos desta série: ( < ) Anterior | Índice | Seguinte ( > )
Olá, dev!
Este é mais um artigo da série DIRETO AO PONTO, que eu estou escrevendo para a DIO. Ele vai tratar das listas, estrutura de dados fundamental para a programação.
Sumário
1. Introdução
2. Os vetores e as listas
3. As listas encadeadas
4. Exemplos de aplicações implementadas com listas
5. Considerações finais
6. Referências
1 – Introdução
Eu criei a série de artigos DIRETO AO PONTO com o objetivo de apresentar, de forma simples e direta, conhecimentos básicos da programação e de computação, principalmente, para os iniciantes.
Aqui, são tratados de temas como lógica de programação, linguagens, hardware dos computadores, história da computação e assuntos relacionados à plataforma da DIO, como a escrita de artigos e os desafios de código.
Neste artigo, eu vou falar sobre as listas, listas encadeadas e as aplicações que as usam na implementação. Dentre estas aplicações, estão o armazenamento de coleções de dados, como itens em uma lista de contatos, e manipulação de sequências de dados, como strings, para facilitar operações de busca e ordenação.
2 – Os vetores e as listas
Em um dos últimos artigos, eu falei sobre os vetores. Um vetor é uma estrutura que oferece uma quantidade determinada de posições para armazenar elementos e acessar seus valores. Este é um vetor estático.
No caso do vetor dinâmico, o número de posições pode aumentar, automaticamente, gerenciada pela linguagem, quando o vetor está cheio. O armazenamento e recuperação de elementos em um vetor, por meio de índices, é muito rápido e prático.
O vetor não permite remover itens ou adicionar novos elementos. Além disso, ume operação de ordenação exige que todos os elementos mudem de posição, para dar lugar a outros elementos, se tornando uma operação muito custosa.
Para superar estas limitações do vetor, foi criada a estrutura de lista. Ela permite adição e remoção de elementos, além de crescimento ilimitado.
No início, as linguagens de programação só ofereciam a estrutura vetor (array), como o FORTRAN. Mesmo assim, era possível simular a operação de uma lista por meio dos vetores. Veja um exemplo:
Imagine um vetor de inteiros, de 8 posições, com índices de 1 a 8 (na época do FORTRAN, os índices iniciavam em 1).
vetor_original = [4, 8, 1, 10, -1, 9, 0, 3]
Agora vamos criar outro vetor para definir a ordenação dos elementos do vetor acima. Este novo vetor armazena o índice dos elementos do vetor acima, quando ordenados crescentemente.
vetor_crescente = [5, 7, 3, 8, 1, 2, 6, 4]
Ou seja, neste vetor ordenado, o primeiro elemento é 5, índice do elemento de menor valor do vetor original (-1), e assim por diante.
Resumindo, as listas foram criadas para oferecer características que o vetor não possui.
OBS: eu já falei para vocês o dia em que eu INVENTEI as listas encadeadas? Não? Um dia eu conto essa história! :-)
3 - As listas encadeadas
Uma lista encadeada apresenta as seguintes características:
· Uma variável armazena o primeiro elemento da lista;
· Cada elemento aponta para o elemento seguinte da lista;
· O último elemento não aponta para nada (usa um valor nulo);
· Ela permite adição e exclusão de elementos;
· A lista só pode ser percorrida em uma direção;
· As inserções de novos elementos podem ser feitas em qualquer posição da lista;
Este é o comportamento conceitual para uma lista simplesmente encadeada. A figura a seguir ilustra esta lista (a seta para baixo no último elemento indica o final da lista, como um ponteiro nulo).
Existem 3 casos diferentes para a inserção de um elemento novo, pois ele pode ser inserido:
· Na primeira posição da lista;
· Em uma posição intermediária;
· Na última posição.
Considere a lista encadeada ordenada seguinte (figura lista-base):
I - Exemplo de inserção de elemento intermediário ( D ) em uma lista simplesmente encadeada, ordenada, partindo da lista acima:
O novo elemento ( D ) deverá ser inserido entre os elementos ( C ) e ( F ), então o link prox de ( C ) apontará para o novo elemento ( D ) e o link prox do novo elemento ( D ) apontará para o elemento ( F ), que era o seguinte de ( C ) e que passará a ser o elemento seguinte de ( D ). Esta operação é vista na figura a seguir:
Após a inserção, a lista ficará assim:
II - Agora veja um exemplo de inserção de um elemento inicial ( A ) em uma lista simplesmente encadeada, ordenada, a partir da mesma lista inicial da figura lista-base.
O novo elemento ( A ) deverá ser inserido antes do primeiro elemento ( B ), então o link prox do novo elemento ( A ) apontará para o atual primeiro elemento ( B ) da lista; o indicador de início da lista apontará para o novo elemento ( A ), que passará a ser o primeiro elemento da lista.
Após a inserção, a lista ficará assim:
III - Finalmente, para inserir um elemento no final de uma lista ( H ) simplesmente encadeada, ordenada, a partir da mesma lista da figura lista-base, temos:
O novo elemento ( H ) deverá ser inserido após o atual último elemento da lista ( F ), então o link prox do atual último elemento ( F ) apontará para o novo elemento ( H ); o link prox do novo elemento ( H ) apontará para nulo, pois ele será o último elemento da lista, não existindo nenhum elemento após ele.
Após a inserção, a lista ficará assim:
Para exclusão de um elemento, temos os seguintes casos:
· Excluir o primeiro elemento da lista;
· Excluir o último elemento.
· Excluir um elemento de uma posição intermediária;
Veja um exemplo de exclusão do primeiro elemento da lista:
Com base na lista da figura lista-base, para excluir o elemento inicial ( B ):
Basta apontar o início da lista para o elemento seguinte ao atual primeiro elemento ( B ), que é o elemento ( C ). E só!
Ainda com base na lista da figura lista-base, para excluir o último elemento da lista ( H ):
Basta apontar o link prox do elemento anterior a ele ( C ) para o elemento seguinte ao elemento excluído ( F ), indicado pelo link prox do elemento excluído ( F ), que é o link nulo, indicando que não haveria nenhum elemento seguinte ao novo elemento, que passaria a ser agora o último elemento da lista. E só!
Ainda com base na lista da figura lista-base, para excluir o elemento intermediário da lista ( C ):
Basta apontar o link prox do elemento anterior ( B ) a ele para o elemento seguinte ao elemento excluído (C ), que é o elemento ( F ). E só!
Existe um caso geral para a lista, simplesmente encadeada, que é a lista duplamente encadeada. Ela provê apontadores para o elemento anterior e o seguinte para cada elemento da lista, além de ter um indicador de último elemento da lista.
Uma lista duplamente encadeada apresenta as seguintes características:
· Uma variável armazena o primeiro elemento da lista;
· Outra variável aponta para o último elemento da lista;
· Cada elemento aponta para o elemento seguinte da lista e também para o elemento que o antecede;
· O último elemento não aponta para nenhum elemento seguinte (usa um valor nulo), assim como o primeiro elemento não aponta para o elemento que o antecede (também usando um valor nulo);
· Ela permite adição e exclusão de elementos;
· A lista pode ser percorrida nas duas direções;
· As inserções de novos elementos podem ser feitas em qualquer posição da lista;
Os casos de inclusão de um elemento são os mesmos que a lista simplesmente encadeada, com as seguintes operações ADICIONAIS:
· Atualizar o link para o elemento anterior ao que foi incluído e para o elemento seguinte ao que foi inserido;
· Atualizar o link para o último elemento da lista, caso seja incluído um elemento no final da lista;
· Atualizar o link para nulo do primeiro elemento da lista, caso seja incluído o primeiro elemento o último elemento da lista, caso seja incluído um elemento no início da lista;
Veja o exemplo de inserção de um elemento inicial na lista duplamente encadeada inicial da figura lista-base.
A figura abaixo mostra a lista com o novo elemento ( A ) já inserido e os círculos indicam os links que foram atualizados:
Um raciocínio semelhante se aplica ao caso de exclusão de um elemento da lista duplamente encadeada. Veja um exemplo:
As listas e listas encadeadas são muito usadas em várias aplicações de programação devido à sua flexibilidade e eficiência na gestão de dados. As mais comuns são:
· Armazenamento de coleções de dados, como itens em um carrinho de compras ou uma lista de contatos, por exemplo;
· Implementação de pilhas e filas;
· Manipulação de sequências de dados (como strings ou números), facilitando operações como busca e ordenação
· Representação de grafos, em listas de adjacência, por exemplo;
· Gerenciamento de memória, em sistemas operacionais, para alocação dinâmica de memória.
As operações básicas que podem ser realizadas com uma lista são:
Criação (ou declaração) – nomeia a variável, informa o tipo e reserva espaço para os elementos:
List<Integer> integerList = new ArrayList<>( ); ( Em Java )
Inicialização – ao declarar a lista, já informa os seus elementos:
let lista2 = [“Digital”, “Innovation”, “One”]; ( Em Javascript )
Acesso – acessar o valor armazenado em uma posição da lista (em Javascript):
item = lista2[2]; (em Javascript, acessa “One”, terceiro item da lista2 anterior).
console.log(lista2[0]) // imprime o valor “Digital” (primeiro item de lista2)
Atribuição – O comando básico para inclusão de um novo elemento na lista o insere no final da lista (em Python, método append() ); para exclusão do último item da lista (em Python, método pop() ).
No entanto, as linguagens oferecem métodos para inserir e excluir um item em uma posição específica (em Python, para incluir, o método insert(); para excluir, o método remove() )
Em Python, para lista3 = [ 30, 50, 10 ]:
list3.insert(1, 80) insere 80 na posição 1, resultando [ 30, 80, 50, 10 ]
Em Python, para a lista3 = [ 30, 50, 10 ]:
list3.pop(0) exclui o item na posição 0 (exclui o item 30, resultando [ 50, 10 ]
As linguagens atuais oferecem o tipo lista, que inclui diversos métodos adicionais para sua manipulação, como ordenação, reversão da ordem, esvaziamento da lista, contagem de itens, fatiamento, modificação do valor de um item, concatenação de listas, filtragem etc.
Uma lista encadeada pode ser implementada usando vetores, no caso de tamanho definido (com vetores estáticos) ou usando ponteiros (na linguagem C), com alocação de memória e tamanhos dinâmicos.
EXEMPLO DE UMA IMPLEMENTAÇÃO DE LISTA ENCADEADA USANDO VETOR:
Considerando o vetor = [ 50, 10, 40, 80, 70, 60, 20, 30 ], para ordenar estes valores, seria preciso reorganizar todos os valores dele, que ficaria assim: crescente = [ 10, 20, 30, 40, 50, 60, 70, 80 ]
No entanto, a cada novo valor inserido (15, por exemplo), seria preciso realizar uma nova ordenação, alterando novamente os valores do vetor.
Então, uma solução é a criação de uma lista que apresente uma ordenação do vetor inicial acima, em ordem crescente:
Considere o vetor inicial = [ 50, 10, 40, 80, 70, 60, 20, 30 ]
Índices 0 1 2 3 4 5 6 7
Primeiro, vamos identificar qual é o menor valor do vetor (10) e qual é o seu índice no vetor (1), com os índices começando em zero.
inicio_lista = 1 (índice do menor elemento do vetor, primeiro da lista ordenada)
Agora vamos indicar qual é o índice do elemento do vetor subsequente (em valor) a cada elemento da lista ordenada, representado por seu índice no vetor original:
O elemento do vetor subsequente a 10 é 20, , que tem o índice 6. Logo:
seguinte [1] = 6
E assim por diante:
seguinte [6] = 7 (índice do elemento subsequente a 20 - elemento de índice 6 do vetor)
seguinte [7] = 2
seguinte [2] = 0
seguinte [0] = 5
seguinte [5] = 4
seguinte [4] = 3
seguinte [3] = -1 (o valor nulo de final de lista é negativo, pois é um índice inválido para o vetor)
Em forma de lista, teríamos:
inicio_lista = 1
lista_crescente = [ 1, 6, 7, 2, 0, 5, 4, 3 ]
Ou início -> 1 -> 6 -> 7 -> 2 -> 0 -> 5 -> 4 -> 3 -> -1 (final da lista)
Não seria mais fácil fazer a ordenação no próprio vetor original? Sim, claro! Mas a cada novo elemento inserido, o vetor precisaria ser reorganizado e ordenado novamente. Imagine para um vetor de milhares de elementos, como esta operação ficaria custosa.
No caso da lista criada, vamos supor que precisamos fazer a inserção do elemento novo, de valor 25. Para isso, basta:
· Armazenar o novo valor no final do vetor original, na última posição (índice 8);
· Identificar em qual posição ele seria inserido (entre os elementos 20 (índice 6) e 30 (índice 7));
· Varrer a lista ordenada a partir do início até encontrar o índice 6 (do elemento 20);
· Atualizar o índice seguinte do novo elemento (índice 8) para o índice seguinte ao elemento 20 (7);
· Atualizar o valor seguinte deste elemento para o índice do novo elemento (8);
A lista ordenada ficaria assim, após estas atualizações (note o novo índice 8):
inicio_lista = 1
lista_crescente = [ 1, 6, 8, 7, 2, 0, 5, 4, 3 ]
Ou início -> 1 -> 6 -> 8 -> 7 -> 2 -> 0 -> 5 -> 4 -> 3 -> -1 (final da lista)
Para excluir um elemento, a lógica é semelhante. Tente excluir o elemento 50 da lista. Veja que ele permanecerá armazenado no vetor inicial, na mesma posição, só será removido da lista.
Bem, era assim que a fazia para criar listas encadeadas com linguagens como FORTRAN, e Pascal também.
Da mesma forma que criamos uma lista com a ordenação crescente do vetor original, poderia ser criada outra lista com a ordenação decrescente, ou uma lista de pares, ímpares, positivos, negativos etc.
Pode parecer trabalhoso, mas essa é a mesma lógica que se usa para criar os índices de tabelas de bancos de dados, sem precisar alterar a disposição original dos dados.
Atualmente, as linguagens de programação modernas já oferecem uma estrutura do tipo lista (list), com uma gama de operações que para a manipulação dela, tornando seu uso muito mais simples e direto.
4 – Exemplos de aplicações implementadas com listas
Seguem alguns programas básicos que implementam listas, em linguagens diferentes:
Linguagem Pascal – lista usando vetores
program ListaUsandoVetores;
{ Implementa um alista usando vetor }
const
MAX = 100; { Tamanho máximo da lista }
type
TLista = record
elementos: array[1..MAX] of Integer;
tamanho: Integer;
end;
{ Inicializa a lista }
procedure InicializarLista(var lista: TLista);
begin
lista.tamanho := 0;
end;
{ Adiciona um elemento no final da lista }
procedure AdicionarElemento(var lista: TLista; elemento: Integer);
begin
if lista.tamanho < MAX then
begin
lista.tamanho := lista.tamanho + 1;
lista.elementos[lista.tamanho] := elemento;
end
else
writeln('Erro: Lista cheia.');
end;
{ Remove um elemento da lista }
procedure RemoverElemento(var lista: TLista; indice: Integer);
var
i: Integer;
begin
if (indice >= 1) and (indice <= lista.tamanho) then
begin
for i := indice to lista.tamanho - 1 do
lista.elementos[i] := lista.elementos[i + 1];
lista.tamanho := lista.tamanho - 1;
end
else
writeln('Erro: Índice inválido.');
end;
{ Mostra os elementos da lista }
procedure ExibirLista(lista: TLista);
var
i: Integer;
begin
for i := 1 to lista.tamanho do
write(lista.elementos[i], ' ');
writeln;
end;
var
minhaLista: TLista;
begin
InicializarLista(minhaLista);
AdicionarElemento(minhaLista, 10);
AdicionarElemento(minhaLista, 20);
AdicionarElemento(minhaLista, 30);
writeln('Lista após adicionar elementos:');
ExibirLista(minhaLista);
RemoverElemento(minhaLista, 2);
writeln('Lista após remover o segundo elemento:');
ExibirLista(minhaLista);
end.
Saída
Lista após adicionar elementos:
10 20 30
Lista após remover o segundo elemento:
10 30
Na linguagem Python – implementa uma lista usando list
# Inicializa uma lista vazia
minha_lista = [ ]
# Adicionar um elemento à lista
def adicionar_elemento(lista, elemento):
lista.append(elemento)
# Remover um elemento da lista
def remover_elemento(lista, elemento):
if elemento in lista:
lista.remove(elemento)
print(f'Elemento {elemento} removido da lista.')
else:
print(f'Elemento {elemento} não encontrado na lista.')
# Ordenar a lista
def ordenar_lista(lista):
lista.sort()
print('Lista ordenada.')
# Exibir a lista
def exibir_lista(lista):
print('Conteúdo da lista:', lista)
# Adicionando elementos à lista
adicionar_elemento(minha_lista, 10)
adicionar_elemento(minha_lista, 5)
adicionar_elemento(minha_lista, 30)
adicionar_elemento(minha_lista, 20)
# Exibindo a lista
exibir_lista(minha_lista)
# Removendo um elemento da lista
remover_elemento(minha_lista, 10)
# Exibindo a lista após a remoção
exibir_lista(minha_lista)
# Ordenando a lista
ordenar_lista(minha_lista)
# Exibindo a lista ordenada
exibir_lista(minha_lista)
Saída
Conteúdo da lista: [10, 5, 30, 20]
Elemento 10 removido da lista.
Conteúdo da lista: [5, 30, 20]
Lista ordenada.
Conteúdo da lista: [5, 20, 30]
Na linguagem C – lista simplesmente encadeada usando ponteiros
Inicialmente, é criada a estrutura Node, representada na figura abaixo. Ela tem duas variáveis: info representa o valor a ser armazenado na lista e prox é um ponteiro para o próximo elemento da lista. A lista é composta de nós que têm essa mesma estrutura.
Esta lista segue o exemplo da figura abaixo, com a variável inic apontando para o primeiro elemento da lista, a variável info representando o valor armazenado e a variável prox sendo o ponteiro para o próximo elemento da lista.
#include <stdio.h>
#include <stdlib.h>
// Definição da estrutura do nó
struct Node {
int info;
struct Node* prox;
};
// Criar um novo nó
struct Node* createNode(int info) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode-> info = info;
newNode->prox = NULL;
return newNode;
}
// Adicionar um nó no início da lista
void addNode(struct Node** inic, int info) {
struct Node* newNode = createNode(info);
newNode->prox = *inic;
*inic = newNode;
}
// Remover um nó da lista
void removeNode(struct Node** inic, int chave) {
struct Node* temp = *inic;
struct Node* ant = NULL;
// Se o nó a ser removido é o primeiro nó
if (temp != NULL && temp-> info == chave) {
*inic = temp->prox;
free(temp);
return;
}
// Procura pelo nó a ser removido
while (temp != NULL && temp-> info != chave) {
ant = temp;
temp = temp->prox;
}
// Se o nó não foi encontrado
if (temp == NULL) return;
// Desconecta o nó da lista
ant->prox = temp->prox;
free(temp);
}
// Exibir a lista
void displayList(struct Node* node) {
while (node != NULL) {
printf("%d -> ", node-> info);
node = node->prox;
}
printf("NULL\n");
}
int main() {
struct Node* inic = NULL;
addNode(&inic, 10);
addNode(&inic, 20);
addNode(&inic, 30);
printf("Lista após adicionar elementos:\n");
displayList(inic);
removeNode(&inic, 20);
printf("Lista após remover o elemento 20:\n");
displayList(inic);
return 0;
}
Saída
Lista após adicionar elementos:
30 -> 20 -> 10 -> NULL
Lista após remover o elemento 20:
30 -> 10 -> NULL
5 – Considerações finais
Este é mais um artigo da série DIRETO AO PONTO, que eu estou escrevendo para a DIO. Neste artigo eu tratei das listas.
As primeiras linguagens de programação não ofereciam o tipo lista, e era preciso simular uma lista usando o tipo vetor (array), como eu usava em FORTRAN para implementar listas encadeadas.
Depois, as linguagens passaram a oferecer novas formas de se implementar uma lista, como o tipo record em Pascal e o tipo struct em C. A linguagem C passou a oferecer o tipo ponteiro (pointer), que permitiu a implementação de listas dinâmicas, com alocação de memória (Pascal usa a palavra-chave var para indicar que está passando o endereço de uma variável, não o seu valor, para uma função).
Atualmente, as linguagens de programação modernas oferecem o tipo lista, como um vetor dinâmico, gerenciado pela própria linguagem. Além disso, elas oferecem diversos métodos e funções para a manipulação adequada de listas.
No próximo artigo, vamos falar das filas, muito usadas na programação.
6 – Referências
Praticamente todo o conteúdo deste artigo foi tirado do que eu aprendi (e me lembro) sobre o assunto desde o início da minha carreira como programador, desde os anos 80 até agora.
Artigos desta série: ( < ) Anterior | Índice | Seguinte ( > )