Listas Lineares Prof. Mateus Raeder Professor.unisinos.br/mraeder mraeder@unisinos.br

Listas Lineares

Prof. Mateus RaederProfessor.unisinos.br/mraeder

mraeder@unisinos.br

Tipo Abstrato de Dados (TAD)

• Um Tipo Abstrato De Dados (TAD) é a especificação matemática de um conjunto de dados e das operações que podem ser executadas sobre esses dados.

• TAD define o que cada operação faz, mas não como faz.

• Em Java, um TAD pode ser expresso por uma interface.

(Goodrich, 2007)

Estrutura de Dados

• Para implementar um TAD, numa linguagem de programação, é necessário encontrar uma forma de representá-los nessa linguagem utilizando tipos e operações suportadas pelo computador.

• Estrutura de Dados (ED) = materialização do TAD– Em Java, ED é modelado por uma classe.

• Dados em TAD: representado por variáveis na classe• Operações em TAD: representados por método na classe.

• Assim, um mesmo tipo abstrato de dados pode ser concretizado (ou implementado) de diversas formas.

• TADs são materializados pela estruturas de dados.– Lista Encadeada (implementação com referências)– Lista com alocação estática (implementação usando array)

(Goodrich, 2007)

Prof. Mateus Raeder - Programação II 4

Listas Lineares

• A Lista Linear é a estrutura que permite representar um conjunto de dados de forma a preservar a relação de ordem existente entre eles.

• Uma lista linear, ou tabela, é um conjunto de n>= 0 nós L[1], L[2], ..., L[n] , onde:– Se n>0, L[1] é o primeiro nó,– Para 1 < k <= n, o nó L[k] é precedido por L[k-1].

• Seqüência Linear de dados

(SZWARCFITER, 1994)

Prof. Mateus Raeder - Programação II 5

zda cb

INFORMAÇÕES

Número RG Nome Nasc. Cargo

d

Estrutura dos nós

• Estrutura interna é abstraída nó

campo do nó

chave: elemento

identificador do nó na lista

Prof. Mateus Raeder - Programação II 6

Exemplos de aplicações com listas

• notas de alunos• cadastro de funcionários de uma empresa• itens em estoque em uma empresa• dias da semana• vagões de um trem• letras de uma palavra• pessoas esperando ônibus• cartas de baralho• precipitações pluviométricas em um

mês / dia

Prof. Mateus Raeder - Programação II 7

Listas: Tipo de Armazenamento

• O tipo de armazenamento de uma lista linear pode ser classificado de acordo com a posição relativa (sempre contígua ou não) na memória de dois nós consecutivos na lista.– Lista linear com alocação estática de memória

• Também chamada de Lista Seqüencial• Nós em posições contíguas de memória• Geralmente representado por arrays• Útil para implementar filas e pilhas (variáveis para controlar fim e

início)

– Lista linear com alocação dinâmica de memória• Também chamada de Lista Encadeada• Posições de memória são alocadas a medida que são necessárias• Nós encontram-se aleatoriamente dispostos na memória e são

interligados por ponteiros, que indicam a próxima posição da tabela– Nós precisam de um campo a mais: campo que indica o endereço do

próximo nó.(SZWARCFITER, 1994)

Listas Lineares: Classificação

Prof. Mateus Raeder - Programação II 8

SEM restrição para inserção e remoção de elementos

COM restrição para inserção e remoção de elementos

(SZWARCFITER, 1994)

Prof. Mateus Raeder - Programação II 9

Listas Lineares Gerais

• Listas lineares gerais: – a inclusão e remoção de elementos pode ser

realizada em qualquer posição da lista.

• Essas listas não apresentam nenhuma restrição de acesso. – podendo sofrer inserções ou retiradas em qualquer lugar, inclusive

no meio da lista. – Ex: lista de chamada dos alunos.

• As listas gerais podem ser ordenadas ou não ordenadas.– Lista Ordenada: os nós encontram-se ordenados segundo os

valores de suas chaves– Lista Não Ordenada: os nós não estão ordenados

(SZWARCFITER, 1994)

Prof. Mateus Raeder - Programação II 10

Casos particulares de listas

• Deque: inserções e remoções são permitidas apenas nas extremidades da lista;

• Pilha: Inserções e remoções são realizadas em apenas um extremo;

• Fila: inserções realizadas em um extremo e remoções em outro.

1 2 3 4 5 6 7

1 2 3 4 5 6 7

1 2 3 4 5 6 7

(SZWARCFITER, 1994)

Prof. Mateus Raeder - Programação II 11

Operações sobre listas lineares gerais

• Verificar se lista está cheia• Verificar se lista está vazia• Inserção de um nó na i-ésima posição• Inserção de nó no final da lista• Exclusão do i-ésimo nó• Acesso ao i-ésimo nó• Exibir conteúdo dos nós da lista• Alteração do i-ésimo nó• Localizar nó através da chave• Combinação de duas ou mais listas• Classificação da lista• Cópia da lista

Listas Lineares Gerais com Alocação Estáticaou

Listas Seqüênciais

Prof. Mateus Raeder - Programação II 13

Lista linear geral com alocação estática

• Também chamada de Lista Seqüencial• Suponhamos uma lista geral de números inteiros L

que, em certo momento, possui os seguintes 7 elementos:

5 -4 8 0 -1 6 2• Declarando um vetor de inteiros de nome

L[0..Max-1], disporemos a lista nas primeiras posições do vetor, de modo que o primeiro nó da lista ocupe a posição 0 do vetor, e indicaremos seu término por uma variável inteira de nome size que indica a posição do último elemento. Teremos

size

14

Exercício: Lista com alocação estática

• Inserir 3 no fim da lista:

• Retirar 8:

• Retirar o 1º elemento:

• Inserir 7 no início da lista:

5 -4 8 0 -1 6 2 3

5 -4 0 -1 6 2 3

-4 0 -1 6 2 3

7 -4 0 -1 6 2 3

size

size

size

size

Operações implementadas sobrelistas lineares gerais

public interface IndexListObject { /** Returns the number of elements in this list. */ public int size(); /** Returns whether the list is empty. */ public boolean isEmpty(); /** Inserts an element e to be at index i, shifting all elements after this. */ public void add (int i, Object e) throws IndexOutOfBoundsException; /** Returns the element at index i, without removing it. */ public Object get (int i) throws IndexOutOfBoundsException; /** Removes and returns the element at index i, shifting the elements after this. */ public Object remove (int i) throws IndexOutOfBoundsException; /** Replaces the element at index i with e, returning the previous element at i. */ public Object set (int i, Object e) throws IndexOutOfBoundsException;}

(Goodrich, 2007)

Listas Seqüenciais

public class ArrayIndexListObject implements IndexListObject { private Object[] A; // array storing the elements of the indexed list private int capacity = 16; // initial length of array A private int size = 0; // number of elements stored in the indexed list

/** Creates the indexed list with initial capacity 16. */

public ArrayIndexListObject() {

A = new Object[capacity];

}

/** Returns the number of elements in the indexed list. */

public int size() {

return size;

}

/** Returns whether the indexed list is empty. */

public boolean isEmpty() {

return size() == 0;

}

(Goodrich, 2007)

Prof. Mateus Raeder - Programação II 17

Lista geral com alocação estática

/** Returns the element stored at the given index. */

public Object get(int r) throws IndexOutOfBoundsException {

checkIndex(r, size());

return A[r];

}

/** Replaces the element stored at the given index. */

public Object set(int r, Object e) throws IndexOutOfBoundsException {

checkIndex(r, size());

Object temp = A[r];

A[r] = e;

return temp;

}

CS 307 Fundamentals of Computer Science

18

Inserção

V0 1 2 sizer

V0 1 2 sizer

V0 1 2 size

or

Lista geral com alocação estática

/** Inserts an element at the given index. */

public void add(int r, Object e)

throws IndexOutOfBoundsException {

checkIndex(r, size() + 1);

if (size == capacity) {// an overflow

capacity *= 2;

Object[] B = new Object[capacity];

for (int i=0; i<size; i++)

B[i] = A[i];

A = B;

}

for (int i=size-1; i>=r; i--)// shift elements up

A[i+1] = A[i];

A[r] = e;

size++;

}

Prof. Mateus Raeder - Programação II 19

CS 307 Fundamentals of Computer Science

20

Remoção

V0 1 2 sizer

V0 1 2 size

or

V0 1 2 sizer

Lista geral com alocação estática

/** Removes the element stored at the given index. */

public Object remove(int r)

throws IndexOutOfBoundsException {

checkIndex(r, size());

Object temp = A[r]; for (int i=r; i<size-1; i++)// shift elements down

A[i] = A[i+1];

size--;

return temp;

}

Prof. Mateus Raeder - Programação II 21

Lista geral com alocação estática

/** Checks whether the given index is in the range [0, n - 1] */

protected void checkIndex(int r, int n) // throws IndexOutOfBoundsException {//

if (r < 0 || r >= n)

throw new IndexOutOfBoundsException("Illegal index: " + r);

}

}

Prof. Mateus Raeder - Programação II 22

Exercícios

• Exercício 1. Crie a classe Aluno, representando um aluno que conterá um nome (String) e uma nota (double). – Adicione métodos de acesso e modificação para os

atributos da classe.– Sobrescreva nesta classe o método toString da

classe Object.

• No método main de uma classe qualquer, crie uma lista linear geral (implementação dada em aula). Crie vários objetos alunos e o insira na lista. • Exercício 2. Na classe ArrayIndexListObject,

sobrescreva nesta classe o método toString da classe Object.

Estouro das Listas

• Estouro de listas:– Estouro negativo (underflow): lista vazia sofre

operação de extração– Estouro positivo (overflow): quando a inserção de

um elemento excede a capacidade total da lista.

Lista geral com alocação estática

/** Inserts an element at the given index. */

public void add(int r, Object e)

throws IndexOutOfBoundsException {

checkIndex(r, size() + 1);

if (size == capacity) {// an overflow

capacity *= 2;

Object[] B = new Object[capacity];

for (int i=0; i<size; i++)

B[i] = A[i];

A = B;

}

for (int i=size-1; i>=r; i--)// shift elements up

A[i+1] = A[i];

A[r] = e;

size++;

}

Prof. Mateus Raeder - Programação II 25

Listas Lineares Geraise Genéricas

Obs: Antes de continuar com esse conteúdo, ensinar tipos genéricos

Prof. Mateus Raeder - Programação II 26

Lista Linear Geral: Interface

public interface IndexList<E> {

/** Returns the number of elements in this list. */

public int size();

/** Returns whether the list is empty. */

public boolean isEmpty();

/** Inserts an element e to be at index i, shifting all elements after this. */

public void add(int i, E e)

throws IndexOutOfBoundsException;

/** Returns the element at index i, without removing it. */

public E get(int i)

throws IndexOutOfBoundsException;

/** Removes and returns the element at index i, shifting the elements after this. */

public E remove(int i)

throws IndexOutOfBoundsException;

/** Replaces the element at index i with e, returning the previous element at i. */

public E set(int i, E e)

throws IndexOutOfBoundsException;

}

Prof. Mateus Raeder - Programação II 27

(Goodrich, 2007)

Lista Linear Geral com Tipos Genéricos (1)

public class ArrayIndexList<E> implements IndexList<E> {

private E[] A; // array storing the elements of the indexed list

private int capacity = 16; // initial length of array A

private int size = 0; // number of elements stored in the indexed list

/** Creates the indexed list with initial capacity 16. */

public ArrayIndexList() {

A = (E[]) new Object[capacity];

}

/** Returns the number of elements in the indexed list. */

public int size() {

return size;

}

/** Returns whether the indexed list is empty. */

public boolean isEmpty() {

return size() == 0;

}

Prof. Mateus Raeder - Programação II 28

(Goodrich, 2007)

Lista Linear Geral com Tipos Genéricos (2)

/** Returns the element stored at the given index. */

public E get(int r)

throws IndexOutOfBoundsException {

checkIndex(r, size());

return A[r];

}

/** Replaces the element stored at the given index. */

public E set(int r, E e)

throws IndexOutOfBoundsException {

checkIndex(r, size());

E temp = A[r];

A[r] = e;

return temp;

}

Prof. Mateus Raeder - Programação II 29

Lista Linear Geral com Tipos Genéricos (3)

/** Inserts an element at the given index. */

public void add(int r, E e)

throws IndexOutOfBoundsException {

checkIndex(r, size() + 1);

if (size == capacity) {// an overflow

capacity *= 2;

E[] B =(E[]) new Object[capacity];

for (int i=0; i<size; i++)

B[i] = A[i];

A = B;

}

for (int i=size-1; i>=r; i--)// shift elements up

A[i+1] = A[i];

A[r] = e;

size++;

}

Prof. Mateus Raeder - Programação II 30

Lista Linear Geral com Tipos Genéricos (4)

/** Removes the element stored at the given index. */

public E remove(int r)

throws IndexOutOfBoundsException {

checkIndex(r, size());

E temp = A[r];

for (int i=r; i<size-1; i++)// shift elements down

A[i] = A[i+1];

size--;

return temp;

}

/** Checks whether the given index is in the range [0, n - 1] */

protected void checkIndex(int r, int n) //

throws IndexOutOfBoundsException {//

if (r < 0 || r >= n)

throw new IndexOutOfBoundsException("Illegal index: " + r);

}

}

Prof. Mateus Raeder - Programação II 31

Exercícios

• Exercício 3. Repetir exercício 1, mas usando a classe ArrayIndexList com tipos genéricos.

Referências Bibliográficas

• GOODRICH, MICHAEL T. ; TAMASSIA, ROBERTO. Estruturas de dados e algoritmos em Java. 4.ed. Bookman. 2007.

• SZWARCFITER, JAYME LUIZ / MARKENZON, LILIAN Estruturas De Dados E Seus Algoritmos. Ed. LTC, 1994.

Prof. Mateus Raeder - Programação II 33