Listas Duplamente Encadeadas

Afluentes: Estrutura de Dados

Vídeoaulas

• Análise visual de Listas Encadeadas Duplas
• Lista Encadeada Dupla - Implementação em java: Só assista esse vídeo depois de tentar implementar por si. Esse vídeo é a resolução do exercício.

Lista Duplamente Encadeada

Uma lista duplamente encadeada é assim denominada pela forma como os nós que compõem a lista são ligados. Ao contrário das listas simples, existem dois caminhos possíveis para se percorrer a lista. Pode-se pesquisar a lista duplamente encadeada em sentido normal e em sentido inverso. Isso se da pelo fato de que os elementos da lista possuem dois ponteiros, um que aponta para o próxim o nó e outro que aponta para o anterior. Adicionalmente, o primeiro nó terá seu ponteiro anterior apontando para NULL e o último nó terá seu ponteiro proximo apontando igualmente para NULL.

Estrutura de Dados de uma Lista Duplamente Encadeada

class No {              // Nó da lista duplamente encadeada
    int informacao;     // Informação que se quer armazenar
    No proximo;         // Ponteiro para o próximo nó
    No anterior;        // Ponteiro para o nó anterior
}

class ListaDupla {      // Lista duplamente encadeada
    No inicio;          // Ponteiro para o primeiro nó da lista
    No fim;             // Ponteiro para o último nó da lista
    int tamanho;        // Quantidade de elemntos na lista
}

Exercícios

Implemente em linguagem de programação Java as seguintes operações na Lista Encadeada Dupla:

• Inserir no início
• Retirar do início;
• Inserir no meio;
• Retirar do meio;
• Inserir no fim;
• Retirar do fim;