Estrutura de dados Listas

Fala, meus consagrados! Tudo beleza com vocês?

Neste artigo, iremos revisar os principais pontos sobre a estrutura de dados listas e responder algumas questões.

Teoria

São conjuntos de elementos, objetos, variáveis, tarefas ou qualquer coisa que se possa enumerar ou formar um conjunto. São estruturas de dados nas quais elementos de um mesmo tipo de dado estão organizados de maneira sequencial, não necessariamente estão fisicamente em sequência, mas a ideia é a existência de uma ordem lógica entre eles.

São exemplos de listas:

• Pessoas na fila de um banco;
• Letras em uma palavra;
• Relação de notas dos alunos de uma turma;
• Itens em estoque em uma empresa;
• Dias da semana;
• Vagões de um trem;
• Pilha de pratos;
• Cartas de baralho.

Nas listas, podemos aplicar as seguintes operações:

• Criar uma lista;
• Remover uma lista;
• Inserir um elemento na lista;
• Remover um elemento da lista;
• Acessar um elemento da lista;
• Alterar um elemento da lista;
• Combinar duas ou mais listas;
• Classificar uma lista;
• Copiar uma lista;
• Localizar elemento através de informação.

As lists podem ser alocadas de duas formas:

• Listas sequenciais (contíguas):
  • São implementadas em arrays;
  • Os elementos estão armazenados sequencialmente na memória
• Listas encadeadas:
  • Os elementos não estão necessariamente armazenados sequencialmente na memória, porém a ordem lógica entre os elementos que compõem a lista deve ser mantida.

As listas sequenciais, também chamadas de arrays, arranjos ou vetores, são estruturas com posições fixas, onde cada elemento da lista deve ser colocado em uma posição no array. Ao utilizá-las para armazenamento de informações, é necessário definir em tempo de compilação qual o tamanho ou quantidade de bytes a ser alocados para o array.

As listas sequenciais possuem como vantagens:

• A criação de um array de qualquer tamanho é simples; e
• Não há necessidade de compreender ponteiros ou referências.

Como desvantagens, temos:

• Limitações quanto ao tamanho de memória;
• Custo computacional maior;
• Alocação de memória exagerada.

As listas encadeadas não possuem restrição de tamanho, indicando que as células que as compõem devem estar alocadas sequencialmente na memória, consequentemente, não há definição de um tamanho fixo em tempo de compilação.

Figura 1: Lista encadeada.

As listas encadeadas têm as seguitens vantagens:

• Extremamente eficiente no custo:
  • De memória; e
  • De processamento;
• Nunca acarreta em movimentar todos os elementos.

A desvantagem é que envolve conceitos mais avançados de programação, tais como ponteiros ou referências.

As listas encadeadas podem ser subdivididas em:

• Listas simplesmente encadeadas:
  • Cada elemento possui:
    • Espaço para armazenamento da informação; e
    • Espaço para armazenamento da referência do próximo elemento da lista;
• Listas duplamente encadeadas:
  • Cada elemento possui:
    • Espaço para armazenamento da informação;
    • Espaço para armazenamento da referência do próximo elemento da lista; e
    • Espaço para armazenamento da referência do elemento anterior da lista.

Figura 2: Lista simplesmente encadeada.

Figura 3: Lista duplamente encadeada.

Temos também as listas circulares. Essas listas possuem o último elemento ligado ao primeiro elemento. Elas podem ser simplesmente encadeadas ou duplamente encadeadas.

Figura 4: Lista circular.

Finalmente, podemos ter os seguintes tipos de listas especiais:

• Pilhas:
  • São listas lineareas do tipo LIFO:
    • Last In First Out;
    • O último elemento que entrou, é o primeiro a sair;
  • Possuem apenas uma entrada (topo) a partir da qual os dados entram e saem dela;
• Filas:
  • São lista linear do tipo FIFO:
    • First In First Out;
    • O primeiro elemento a entrar será o primeiro a sair;
  • Os elementos:
    • Entram pelo final; e
    • Saem pelo início;
• Deques:
  • Double-Ended QUEue;
  • São listas lineares nas quais os elementos entram e saem:
    • Tanto pelo início;
    • Quanto pelo final; e
  • Podem ser consideradas uma generalização da fila.

Essas estruturas serão abordadas em artigos mais na frente.

Questões de concursos

[VUNESP 2019 UFABC – Técnico de Tecnologia da Informação] Uma estrutura de dados definida como uma sequência de células em que cada célula contém um elemento e o endereço da célula seguinte recebe o nome de

(A) grafo.

(B) vetor.

(C) matriz.

(D) árvore.

(E) lista encadeada.

Cometários:

O enunciado cita as listas encadeadas.

Gabarito: letra E.

[VUNESP 2014 TJ/PA – Analista Judiciário – Análise de Sistema – Desenvolvimento] Em uma estrutura de dados do tipo Lista Duplamente Ligada (ou Lista Duplamente Encadeada), cada elemento contém três componentes, sendo um referente à informação propriamente dita e os outros dois são ponteiros para outros elementos da estrutura. Genericamente, tais ponteiros apontam, nessa estrutura de dados, para a

(A) célula anterior e para a próxima célula.

(B) primeira célula e para a célula anterior.

(C) célula anterior e para a própria célula

(D) primeira célula e para a própria célula.

(E) primeira célula e para a última célula.

Cometários:

Se são listas duplamente encadeadas, então cada elemento é composto de:

• Espaço para armazenamento da informação;
• Espaço para armazenamento da referência do próximo elemento da lista; e
• Espaço para armazenamento da referência do elemento anterior da lista.

A letra A trouxe os dois últimos espaço de cada elemento.

Gabarito: letra A.

[SUGEP/UFRPE 2016 UFRPE – Técnico em Tecnologia da Informação] Sobre as estruturas de dados lineares, analise as proposições abaixo. (Marque CERTO ou ERRADO o texto do item)

[3] Devido a sua característica dinâmica, uma lista não pode ser implementada em um arranjo.

Comentários:

Uma lista pode ser implementada em um arranjo sim. São as listas sequenciais.

Gabarito: ERRADO.

Então é isso!
[]s e até a próxima!
_________________________
Professor Rogerão Araújo