Aula 05 Listas Lineares

5.1

Aula 5: Listas Lineares

Conceito de vetores, matrizes
Conceito de listas e deques
Algoritmos de busca em listas lineares

5.2

Conceito
Uma lista linear agrupa informações sobre um conjunto de elementos que se relacionam entre si.
Exemplos:
Notas de alunos de uma turma
Quantidades de produtos no estoque de uma loja
Nomes de clientes de uma empresa
Operações básicas em listas lineares

- Busca de um elemento
- Inserção de um elemento
- Remoção de um elemento

5.3

Classificação de Listas Lineares
Com relação ao modo de armazenamento da memória
Listas Sequenciais: os elementos ocupam posições contíguas na memória.
...

...
Elementos

Listas Encadeadas: os elementos encontram-se dispersos pela memória, sendo ligados por variáveis - ponteiro.
Ponteiro

elemento

Ponteiro

Ponteiro

elemento

Ponteiro

elemento

5.4

Classificação de Listas Lineares
Com relação ao modo como os elementos são inseridos/removidos 1. Listas (em geral): inserções e remoções são permitidas em qualquer posição.
2. Deques: inserções e remoções são permitidas apenas nas extremidades.
...
Inserir

Remover

Inserir

Remover

5.5

Classificação de Listas Lineares
Com relação ao modo como os elementos são inseridos/removidos 3. Pilhas: inserções e remoções são permitidas apenas em uma das extremidades (a outra permanece fixa).
Extremidade
Fixa
Inserir

...

Remover

4. Filas: as inserções são feitas numa extremidade, e as remoções na outra.
...
Inserir

Remover

Voltar

5.6

Classificação das Listas Sequenciais
Com relação ao modo de indexar os elementos
Vetores: utilizam apenas um índice para localizar o elemento desejado.
Exemplo: Vetor V com n elementos (n > 0)
V

1

2

3

4

n-1

n

...
- V[1] é o primeiro elemento
- V[4] é o quarto elemento
- Em geral, V[k] é o k-ésimo elemento (1 ≤ k ≤ n)

5.7

Classificação das Listas Sequenciais
Matrizes: utilizam dois índices para localizar o elemento desejado.
Exemplo: Matriz M com 5 linhas e 5 colunas
1

M

2

3

4

5

1

M [3, 4]

2
3
4
5
a