[TUTO][Estrutura de dados]Lista encadeada.

[lipinf 3]

Como vejo que a área de Java na WC está muito pobre e tenho bastante tempo livre hj, resolvi fazer alguns tutoriais para essa área =].

 

 

Tuto de Listas(linear e ordenada) encadeadas.

 

Dificuldade:

Básico

 

Índice:

1. Lista linear

2. Vantagens e desvantagens

3. Lista ordenada

4. Nodo ou Nó

5. Sources

 

 

 

Lista linear

 

Lista linear é uma estrutura de dados dinâmica cujos elementos estão organizados de maneira seqüencial. São estruturas flexíveis, que podem crescer ou diminuir durante a execução do programa, de acordo com a demanda.

 

Operações Mais Freqüentes Em Listas:

• Iniciar/Criar/Instanciar uma lista linear vazia

• Verificação do estado da lista: vazia ou cheia.

• Inclusão de elemento em uma posição específica;

• Remoção e retorno do elemento em uma posição específica;

• Consulta a um elemento em uma posição específica

• Alteração de um elemento de uma posição específica

• Busca de um elemento na lista

• Ordenação dos elementos da lista

• Fazer uma cópia da lista

• Mostrar a lista

 

Tipos de implementações de Listas:

1. Implementação seqüencial:

um vetor é utilizado para armazenar os elementos da estrutura. Vemos abaixo a representação gráfica de uma lista com 4 elementos armazenada em um vetor de capacidade para até 10 elementos.

 

2. Implementação encadeada:

Os elementos são armazenados em nodos que têm um campo que aponta para o próximo elemento da lista. Vemos abaixo a representação gráfica de uma lista vazia e de uma lista com 4 elementos encadeados.

 

 

 

 

Vantagens e Desvantagens do encadeamento em relação à implementação seqüencial:

 

• Desvantagens

1. Acesso indireto aos elementos;

2. Tempo variável para acessar os elementos (depende da posição do elemento) ;

3. Gasto de memória maior pela necessidade de um novo campo para o ponteiro

• Vantagens

1. A inserção e remoção de elementos podem ser feitas sem

deslocar os itens seguintes da lista;

2. Não há necessidade de previsão do número de elementos da

estrutura, o espaço necessário é alocado em tempo de execução;

3. Facilita o gerenciamento de várias listas (fusão, divisão,...)

 

 

Listas ordenadas

 

São listas lineares onde os elementos estão ordenados segundo um critério preestabelecido. As remoções são realizadas de qualquer posição, mas as inserções são feitos de modo que cada novo elemento a ser inserido ocupará a posição que mantenha os elementos ordenados. Essa ordenação é mantida para facilitar a busca de elementos na lista.

 

Operações Mais Freqüentes Em Listas:

• Iniciar/Criar uma lista linear vazia (Construtor)

• Verificação do estado da lista: vazia ou cheia.

• Inclusão de elemento;

• Remoção e retorno do elemento em uma posição específica;

• Consulta a um elemento em uma posição específica

• Busca de um elemento na lista (BUSCA BINÁRIA só na implementação sequencial)

• Fazer uma cópia da lista

• Mostrar a lista

 

Implementação seqüencial de uma lista ordenada.

Representação gráfica

Implementação encadeada de uma lista ordenada. (Encadeamento com nodos cabeça e sentinela)

Representação gráfica

 

 

 

Não há possibilidades de eu terminar esse tuto sem explicar o "esqueleto" da encadeação.

 

Nodo ou Nó

 

Um Nodo ou nó representa cada ponto de inter-conexão com uma estrutura ou rede, independente da função do equipamento representado por ele. Em Ciência da Computação, nodo ou nó também pode representar um elemento de uma árvore de busca binária ou um vértice de um grafo.(BY WIKIPEDIA)

Resumindo de uma forma bem vulgar, nodo é um elemento da lista encadeada.

 

 

Nodo cobeça:

Um nodo cabeça é um nodo extra, mantido sempre na primeira posição de uma lista encadeada. Ele não é usado para armazenar um elemento da lista, tendo como único objetivo simplificar as funções de inserção e remoção da lista. No caso de uma lista numérica ele pode ser usado para, por exemplo, armazenar o número de elementos na lista.

 

Nodo sentinela:

Um nodo sentinela também é um nodo extra, mantido na última posição da lista com o mesmo objetivo do nodo cabeça. Seu valor não faz parte da lista. Muitas vezes ele armazena o maior valor (HV – High Value) para o tipo armazenado. Isso simplifica, ainda mais, os processos de inserção e remoção.

 

 

Sources

 

LISTA SEQUENCIAL

É necessário se cadastrar para acessar o conteúdo.

• Entre
• ou
• Cadastre-se

 

 

LISTA ENCADEADA

obs: por motivos de preguiça, tempo e burrice(no final do tópico explico o porque da burrice) está sem nodo cabeça e sentinela.

 

É necessário se cadastrar para acessar o conteúdo.

• Entre
• ou
• Cadastre-se

 

 

NODO

 

É necessário se cadastrar para acessar o conteúdo.

• Entre
• ou
• Cadastre-se

 

 

 

Fim.

 

 

OBSERVAÇÕES GERAIS:

*Fiz o tutorial usando como referencia Netbeans.

*Algumas coisas do tuto fiz no word e depois passei pra cá, porque algumas formatações de texto não seu fazer aqui xD.

*Peço desculpas por qualquer erro de português, teclado ruim.

*Qualquer dúvida relacionada ao tópico estarei respondendo =]

 

**Ah, sobre a burrice(citada no tópico)... é que estava fazendo o tuto e sem querer fechei a página e perdi tudo u.u

então fui fazer tudo denovo e pra agilizar coloquei essa source sem nodo cabeça e sentinela eu mesmo(eu já tinha).

 

ESPERO TER AJUDADO, SE GOSTOU AGRADEÇA ;D