Estrutura de dados

Aula 2 - Listas
Definição: Uma lista linear agrupa informações referentes a um conjunto de elementos que, de alguma forma, se relacionam entre si. Uma lista linear é então um conjunto de n >= 0 nós L[1], L[2], …, L[n] tais que suas propriedades decorrem, unicamente, da posição relativa dos nós dentro da sequência linear. Tem-se - se n>0, L[1] é o primeiro nó, - para 1 ,k ,=n, o nó L[k] é precedido por L[k-1]. Vasto número de aplicações => importância! Interface exemplo de uma Lista: 1) Adiciona um dado elemento no fim da Lista. 2) Adiciona um dado elemento em um dada posição. 3) "Pega" o elemento de uma dada posição. 4) Remove o elemento de uma dada posição. 5) Verifica se um dado elemento está contido na Lista. => busca 6) Informa a quantidade de elementos da Lista. Casos particulares => filas e pilhas! O tipo de armazenamento de uma lista linear pode ser classificado de acordo com a posição relativa na memória de dois nós consecutivos na lista. O primeiro caso corresponde à alocação sequencial de memória, enquanto o segundo é conhecido como alocação encadeada. Listas com vetores (alocação sequencial estática) Idéia: "...dividir o espaço de memória alocado em pequenos pedaços idênticos. Cada pedaço armazenará um objeto (entidade). Além disso, vamos indexar (numerar) os pequenos pedaços para ser fácil recuperar um dado objeto." Um array é uma porção de memória fixa e sequencial dividida em pedaços idênticos indexados a partir do 0 (em Java). Em cada posição do array, podemos guardar um tipo de dados. Na verdade, cada posição pode guardar uma referência para um determinado tipo, inclusive objetos. Problema: A capacidade de um array é fixa e deve ser informada no momento da criação do array - alocação estática, sem possibilidade de redimensionamento. Algumas Operações 1 - Adiciona um dado elemento no fim da Lista Vamos considerar que o armazenamento no array será mantido compactado à esquerda, sem

permitir "buracos" no array. 1.1 -