Implementação de Estruturas de Dados Lineares PDF

Summary

This document provides an overview of linear data structures, focusing on lists, stacks, queues, and other related concepts. The document covers their implementation and characteristics in detail, discussing their use in computer science algorithms.

Full Transcript

Implementação de estruturas de dados lineares Listas ligadas, Stacks, Queues, Deques, Maps, Iteradores, Comparadores Algoritmos e Estrutura de Dados 1 Listas Ligadas O array é uma estrutura de dados de baixo nível que pode muito bem ser us...

Implementação de estruturas de dados lineares Listas ligadas, Stacks, Queues, Deques, Maps, Iteradores, Comparadores Algoritmos e Estrutura de Dados 1 Listas Ligadas O array é uma estrutura de dados de baixo nível que pode muito bem ser usado para guardar os elementos duma coleção, organizados de forma linear. Mas, como se sabe, o array tem um grave inconveniente: a sua capacidade é logo fixada no momento em que é criado, não permitindo depois a sua expansão em caso de necessidade. E, para além disso, as operações de inserção e remoção de elementos numa posição intermédia do mesmo podem ser morosas, dada a possível necessidade de deslocar muitos dos elementos já guardados. A lista ligada surge como uma estrutura de dados linear alternativa ao array, resolvendo, por completo, as limitações dos arrays; sendo uma estrutura de natureza dinâmica, a sua dimensão vai aumentando e diminuindo, adaptando-se à quantidade de elementos que efetivamente precise de guardar. Poder-se-á mesmo afirmar que tem capacidade praticamente ilimitada, uma vez que apenas dependerá dos recursos memória disponíveis. mas também tem como inconveniente o acesso passar a ser sequencial… Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 2 Lista Ligada Simples (SLL) Uma lista ligada simples (Singly Linked List – SLL) é uma estrutura de dados dinâmica que consiste numa sequência de nodos Cada nodo guarda: um dos elementos que se pretende colecionar (ou a referência para esse elemento); um apontador (uma referência, em Java) para o próximo nodo. Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 3 A classe Node Definida como classe genérica, e interna (nested) à classe SLL. Genérica de modo a poder vir a acomodar um elemento do tipo que quisermos (digamos de um tipo ainda não definido E). Interna à classe SLL, uma vez que a mesma só precisa de estar disponível (visível) dentro da classe SLL. Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 4 Atributos e métodos consultores da classe SLL // Poderíamos ter definido a SLL apenas // com o atributo head. // Opta-se por incluir também o tail e o size // para conseguirmos métodos mais eficientes Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 5 Passos a dar para a inserção dum elemento no início da SLL 1. Criar o novo nodo; 2. Colocar no nodo o novo elemento; 3. Colocar o novo nodo a apontar para o primeiro nodo; 4. Colocar o apontador head a apontar para o novo nodo. Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 6 Passos a dar para a inserção dum elemento no fim da SLL 1. Criar o novo nodo; 2. Colocar no nodo o novo elemento; 3. Colocar o novo nodo a apontar para null; 4. Colocar o último nodo a apontar para o novo nodo; 5. Colocar o apontador tail a apontar para Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados o novo nodo. 7 Métodos de inserção da SLL Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 8 Passos a dar para a remoção do primeiro elemento da SLL 1. Colocar o apontador head a apontar para o nodo seguinte da lista. A ação anterior, por si só, leva a que o garbage collector (“coletor de lixo”) elimine da memória o nodo que deixou de ser referenciado. Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 9 Método de remoção da SLL A remoção do último nodo é uma operação pouco eficiente Uma vez que requer que se percorra toda a lista até se chegar ao penúltimo nodo, que terá que passar a apontar para null. Trata-se de um algoritmo de complexidade linear – O(n); quando, todas as outras operações que vimos eram de complexidade constante – O(1). Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 10 Lista Duplamente Ligada Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 11 Lista Duplamente Ligada (DLL) Uma lista duplamente ligada (Doubly Linked List – DLL) é uma lista ligada que pode ser percorrida nos dois sentidos Cada nodo guarda: um dos elementos que se pretende colecionar; um apontador prev para o nodo antecessor; um apontador next para o próximo nodo. Para que não venha a ser necessário tratar de forma separada os casos particulares de inserção e remoção nos extremos da DLL, é comum optar-se por adicionar no início e no fim da lista dois nodos especiais: O nodo header no início da lista, E o nodo trailer no fim da lista. Estes nodos são conhecidos por sentinelas, existirão sempre (mesmo na lista vazia) e não guardam qualquer elemento da coleção. Repare-se que desta forma, qualquer inserção ou remoção de um nodo, vai sempre acontecer entre outros nodos, e não nos extremos. Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 12 Definição da classe genérica DLL [1/4] Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 13 Inserir um novo nodo na DLL Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 14 Remover um nodo da DLL Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 15 Definição da classe genérica DLL [2/4] Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 16 Definição da classe genérica DLL [3/4] Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 17 Definição da classe genérica DLL [4/4] Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 18

Use Quizgecko on...
Browser
Browser