Índice

Introdução ............................................................................................................................................... 2

Listas Ligadas ......................................................................................................................................... 3

Estrutura das Listas Ligadas ................................................................................................................... 3

Operações de Listas Ligadas ................................................................................................................... 4

Função de inicialização ....................................................................................................................... 4

Função de inserção .............................................................................................................................. 4

Função que percorre os elementos da lista .......................................................................................... 5

Função que verifica se lista está vazia ................................................................................................ 5

Função de busca .................................................................................................................................. 5

Função que retira um elemento da lista .............................................................................................. 6

Função para liberar a lista ................................................................................................................... 7

Vantagens ................................................................................................................................................ 7

Desvantagens .......................................................................................................................................... 7

Tipos de Listas Ligadas .......................................................................................................................... 8

Listas Ligadas Simples ....................................................................................................................... 8

Propriedadas das Listas Ligadas Simples ........................................................................................... 8

Listas duplamente ligadas ................................................................................................................... 8

Vantagens ............................................................................................................................................ 9

Desvantagens ...................................................................................................................................... 9

Listas circulares .................................................................................................................................. 9

Lista circular duplamente encadeada ................................................................................................ 10

Vantagens .......................................................................................................................................... 10

Desvantagens .................................................................................................................................... 10

Projecto ................................................................................................................................................. 11

Conclusão .............................................................................................................................................. 12

Referências Bibliográficas .................................................................................................................... 13

Introdução

Frequentemente precisamos agrupar vários elementos/dados num conjunto. A partida

podemos não saber o número exacto de elementos a ser agrupados. Em cada instante

podemos acrescentar ou remover elemento ao conjunto. Em programação consideramos dois

tipos de estruturas que permitem guardar uma colecção de elementos: estrutura estática e

estrutura dinâmica. Os elementos podem ser organizados de um modo distinto.

Uma matriz é uma estrutura que é fornecido em linguagens de programação. No entanto, tem

pelo menos duas limitações: (1) rearranjar o tamanho da matriz necessária para criar uma

matriz com o tamanho pré-arranjo com o novo tamanho, e (2) nos dados de matriz são

próximas umas das outras sequencialmente na memória, o que significa que para inserir um

item para a matriz deve ser movido por outro arranjo. Esta limitação pode ser ultrapassada

pela utilização de estruturas ligadas.

A estrutura relacionada é uma coleção de nós que armazena os dados e links para outros nós.

Assim, os nós podem ser localizado em qualquer lugar da memória e da passagem a partir de

um nó para o outro dentro da estrutura ligada é conseguido através do armazenamento das

referências ou para outro nó ou nós na estrutura.

Uma lista encadeada é a forma mais simples de representar uma colecção de elementos que

juntos formam uma ordenação linear. Cada elemento da colecção é representado pelo objecto

da classe No .

Mesmo quando as estruturas ligadas pode ser implementado numa variedade de formas, mais

flexível é a utilização de um objeto separado para cada nó.

Listas de dados são conjuntos de elementos de dados "alienado em uma linha", as inserções e

exclusões são feitas em qualquer parte de uma lista encadeada.

As pilhas são importantes para compiladores e sistemas operativos, as inserções e deleções

são feitas apenas com uma extremidade da pilha isto é, na parte superior.

As filas de espera representam linhas, as inserções são feitas no final (também conhecido

como o calcanhar) de uma fila, e deleções são feitas a partir do topo (também conhecido

como a cabeça) de uma fila.

As árvores fornecem busca e arquivos de dados ordinamiento sytem e expressões compilação

em linguagem de máquina. Cada uma destas estruturas de dados tem muitas outras aplicações

interessantes.

O presente trabalho tem como objectivo fazer uma abordagem as listas ligadas, para melhor

compreensão e com isso sermos capazes de desenvolver uma aplicação cujo seja capaz de

registar vários serviços num Registo Cívil como registos de nascimentos, casamentos entre

outros.

Listas Ligadas

Uma lista ligada é uma estrutura linear e dinâmica, que corresponde a uma sequência lógica

de entradas ou nós. Tipicamente, em uma lista ligada há um ou dois pontos conhecidos de

acesso, normalmente o topo da lista (seu primeiro elemento) e eventualmente o fim da lista

(seu último elemento).

Cada nó armazena também a localização do próximo elemento na seqüência, ou seja, de seu

nó sucessor. Desse modo, o armazenamento de uma lista não requer uma área contígua de

memória.

Fig. 1 Representa graficamente uma estrutura de lista ligada.

Estrutura das Listas Ligadas

A estrutura consiste numa seqüência encadeada de elementos, em geral chamados de nós da

lista. A lista é representada por um ponteiro para o primeiro elemento (ou nó).

Do primeiro elemento, podemos alcançar o segundo seguindo o encadeamento, e assim por

diante. O último elemento da lista aponta para NULL, sinalizando que não existe um próximo

elemento.

Para exemplificar a implementação de listas encadeadas em C, vamos considerar um exemplo

simples em que queremos armazenar valores inteiros numa lista encadeada. O

nó da lista pode ser representado pela estrutura abaixo:

struct lista {

int info;

struct lista* prox;

};

typedef struct lista Lista;

Podemos notar que trata-se de uma estrutura auto-referenciada, pois, além do campo que

armazena a informação (no caso, um número inteiro), há um campo que é um ponteiro para

uma próxima estrutura do mesmo tipo. Embora não seja essencial, é uma boa estratégia

definirmos o tipo Lista como sinônimo de struct lista, conforme mostrado acima.

O tipo Lista representa um nó da lista e a estrutura de lista encadeada é representada pelo

ponteiro para seu primeiro elemento (tipo Lista*).

Considerando a definição de Lista, podemos definir as principais funções necessárias para

implementarmos uma lista encadeada.

As listas ligadas apresentam operações como: inicializa uma lista vazia, cria um novo nó,

inserir um nó na lista, procurar um nó na lista, imprimir a lista, remover um nó na lista,

liberar a lista (Remover todos os elementos) .

Operações de Listas Ligadas

Função de inicialização

A função que inicializa uma lista deve criar uma lista vazia, sem nenhum elemento.

Como a lista é representada pelo ponteiro para o primeiro elemento, uma lista vazia é

representada pelo ponteiro NULL, pois não existem elementos na lista. A função tem como

valor de retorno a lista vazia inicializada, isto é, o valor de retorno é NULL. Uma possível implementação da função de inicialização é mostrada a seguir:

/* função de inicialização: retorna uma lista vazia */

Lista* inicializa (void)

{

return NULL;

}

Função de inserção

Uma vez criada a lista vazia, podemos inserir novos elementos nela. Para cada elemento

inserido na lista, devemos alocar dinamicamente a memória necessária para armazenar o

elemento e encadeá-lo na lista existente. A função de inserção mais simples insere o novo

elemento no início da lista.

Uma possível implementação dessa função é mostrada a seguir. Devemos notar que o

ponteiro que representa a lista deve ter seu valor atualizado, pois a lista deve passar a ser

representada pelo ponteiro para o novo primeiro elemento. Por esta razão, a função de

inserção recebe como parâmetros de entrada a lista onde será inserido o novo elemento e a

informação do novo elemento, e tem como valor de retorno a nova lista, representada pelo

ponteiro para o novo elemento.

/* inserção no início: retorna a lista atualizada */

Lista* insere (Lista* l, int i)

{

Lista* novo = (Lista*) malloc(sizeof(Lista));

novo->info = i;

novo->prox = l;

return novo;

}

Esta função aloca dinamicamente o espaço para armazenar o novo nó da lista, guarda a

informação no novo nó e faz este nó apontar para (isto é, ter como próximo elemento) o

elemento que era o primeiro da lista. A função então retorna o representa a lista, que é o

ponteiro para o novo primeiro elemento. A Figura 2 ilustra a operação de inserção de um

novo elemento no início da lista.

Fig2. Inserção de um novo elemento no início da lista.

O trecho de código que cria uma lista inicialmente vazia e insere nela novos elementos.

int main (void)

{

Lista* l; /* declara uma lista não inicializada */

l = inicializa(); /* inicializa lista como vazia */

l = insere(l, 23); /* insere na lista o elemento 23 */

l = insere(l, 45); /* insere na lista o elemento 45 */

...

return 0;

}

Não podemos deixar de actualizar a variável que representa a lista a cada inserção de um

novo elemento.

Função que percorre os elementos da lista

Para ilustrar a implementação de uma função que percorre todos os elementos da lista, vamos

considerar a criação de uma função que imprima os valores dos elementos armazenados

numa lista. Uma possível implementação dessa função é mostrada a seguir.

/* função imprime: imprime valores dos elementos */

void imprime (Lista* l)

{

Lista* p; /* variável auxiliar para percorrer a lista */

for (p = l; p != NULL; p = p->prox)

printf(“info = %d\n”, p->info);

}

Função que verifica se lista está vazia

Pode ser útil implementarmos uma função que verifique se uma lista está vazia ou não. A

função recebe a lista e retorna 1 se estiver vazia ou 0 se não estiver vazia. Como sabemos,

uma lista está vazia se seu valor é NULL. Uma implementação dessa função é mostrada a

seguir:

/* função vazia: retorna 1 se vazia ou 0 se não vazia */

int vazia (Lista* l)

{

if (l == NULL)

return 1;

else

return 0;

}

Essa função pode ser re-escrita de forma mais compacta, conforme mostrado abaixo:

/* função vazia: retorna 1 se vazia ou 0 se não vazia */

int vazia (Lista* l)

{

return (l == NULL);

}

Função de busca

Outra função útil consiste em verificar se um determinado elemento está presente na lista. A

função recebe a informação referente ao elemento que queremos buscar e fornece como valor

de retorno o ponteiro do nó da lista que representa o elemento. Caso o elemento não seja

encontrado na lista, o valor retornado é NULL.

/* função busca: busca um elemento na lista */

Lista* busca (Lista* l, int v)

{

Lista* p;

for (p=l; p!=NULL; p=p->prox)

if (p->info == v)

return p;

return NULL; /* não achou o elemento */

}

Função que retira um elemento da lista

Para completar o conjunto de funções que manipulam uma lista, devemos implementar uma

função que nos permita retirar um elemento. A função tem como parâmetros de entrada a lista

e o valor do elemento que desejamos retirar, e deve retornar o valor atualizado da lista, pois,

se o elemento removido for o primeiro da lista, o valor da lista deve ser actualizado.

A função para retirar um elemento da lista é mais complexa. Se descobrirmos que o elemento

a ser retirado é o primeiro da lista, devemos fazer com que o novo valor da lista passe a ser o

ponteiro para o segundo elemento, e então podemos liberar o espaço alocado para o elemento

que queremos retirar. Se o elemento a ser removido estiver no meio da lista, devemos fazer

com que o elemento anterior a ele passe a apontar para o elemento seguinte, e então podemos

liberar o elemento que queremos retirar. Devemos notar que, no segundo caso, precisamos do

ponteiro para o elemento anterior para podermos acertar o encadeamento da lista. As Figuras

3 e 4 ilustram as operações de remoção.

Fig. 3 Remoção do primeiro elemento da lista. Fig. 4Remoção de um elemento no meio da lista.

Uma possível implementação da função para retirar um elemento da lista é mostrada a seguir.

Inicialmente, busca-se o elemento que se deseja retirar, guardando uma referência para o

elemento anterior.

/* função retira: retira elemento da lista */

Lista* retira (Lista* l, int v) {

Lista* ant = NULL; /* ponteiro para elemento anterior */

Lista* p = l; /* ponteiro para percorrer a lista*/

/* procura elemento na lista, guardando anterior */

while (p != NULL && p->info != v) {

ant = p;

p = p->prox;

}

/* verifica se achou elemento */

if (p == NULL)

return l; /* não achou: retorna lista original */

/* retira elemento */

if (ant == NULL) {

/* retira elemento do inicio */

l = p->prox;

}

else {

/* retira elemento do meio da lista */

ant->prox = p->prox;

}

free(p);

return l;

}

O caso de retirar o último elemento da lista recai no caso de retirar um elemento no meio da

lista, conforme pode ser observado na implementação acima. Mais adiante, estudaremos a

implementação de filas com listas encadeadas. Numa fila, devemos armazenar, além do

ponteiro para o primeiro elemento, um ponteiro para o último elemento. Nesse caso, se for

removido o último elemento, veremos que será necessário actualizar a fila.

Função para liberar a lista

Uma outra função útil que devemos considerar destrói a lista, liberando todos os elementos

alocados. Uma implementação dessa função é mostrada abaixo. A função percorre elemento a

elemento, liberando-os. É importante observar que devemos guardar a referência para o

próximo elemento antes de liberar o elemento corrente (se liberássemos o elemento e depois

tentássemos acessar o encadeamento, estaríamos acessando um espaço de memória que não

estaria mais reservado para nosso uso).

void libera (Lista* l)

{

Lista* p = l;

while (p != NULL) {

Lista* t = p->prox; /* guarda referência para o próximo elemento

*/

free(p); /* libera a memória apontada por p */

p = t; /* faz p apontar para o próximo */

}

}

Vantagens A inserção ou remoção de um elemento na lista não implica a mudança de lugar de

outros elementos;

Não é necessário definir, no momento da criação da lista, o número máximo de

elementos que esta poderá ter. Ou seja, é possível alocar memória "dinamicamente",

apenas para o número de nós necessários.

É uma estrutura de dados dinâmica, muito flexível, que permite a fácil inserção e

remoção dos seus elementos.

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

Desvantagens

A manipulação torna-se mais "perigosa" uma vez que, se o encadeamento (ligação)

entre elementos da lista for mal feito, toda a lista pode ser perdida;

Para aceder ao elemento na posição n da lista, deve-se percorrer os n - 1 anteriores.

Acesso indirecto aos elementos .

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

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

Tipos de Listas Ligadas

Listas Ligadas Simples

Uma lista encadeada simples é aquela que contém apenas um link por nó. Este link aponta

para o próximo nó da lista, ou para um valor nulo (vazio) quando se trata do nó final.

Se um nó contém dados de campo refere-se a um outro nó, em seguida, vários nós podem ser

fiadas utilizando apenas uma variável para aceder a sequência completa de nós. Uma

sequência de nós como este é a implementação mais comum de uma lista encadeada, que é

uma estrutura de dados constituído por

nós onde cada nó contém determinadas

informações e de referência para outro nó

na lista.

Se um nó tem apenas um link para o seu

sucessor dentro desta seqüência, a lista é

chamada de uma simples lista ligada. Um

exemplo desta lista é mostrado na Figura

5. Note que apenas uma variável p é usada

para acessar qualquer nó na lista. O

último nó na lista pode ser reconhecida

como um ca mpo de referência nula. Figura 1. Exemplo Lista Ligada Simples

Propriedadas das Listas Ligadas Simples

Uma lista vazia aponta sempre para NULL

O último NÓ da lista sempre aponta para NULL

Qualquer NÓ da lista sempre aponta para o NÓ seguinte, permitindo um passeio do

primeiro ao último.

Todo NÓ criado deve sempre apontar para NULL, até que sua posição na lista seja

definida.

Listas duplamente ligadas

A estrutura de lista encadeada vista nas seções anteriores caracteriza-se por formar um

encadeamento simples entre os elementos: cada elemento armazena um ponteiro para o

próximo elemento da lista.

Desta forma, não temos como percorrer eficientemente os elementos em ordem inversa, isto

é, do final para o início da lista. O encadeamento simples também dificulta a retirada de um

elemento da lista.

Mesmo se tivermos o ponteiro do elemento que desejamos retirar, temos que percorrer a lista,

elemento por elemento, para encontrarmos o elemento anterior, pois, dado um determinado

elemento, não temos como acessar diretamente seu elemento anterior.

Para solucionar esses problemas, podemos formar o que chamamos de listas duplamente

encadeadas. Nelas, cada elemento tem um ponteiro para o próximo elemento e um ponteiro

para o elemento anterior.

Desta forma, dado um elemento, podemos acessar ambos os elementos adjacentes: o próximo

e o anterior. Se tivermos um ponteiro para o último elemento da lista, podemos percorrer a

lista em ordem inversa, bastando acessar continuamente o elemento anterior, até alcançar o

primeiro elemento da lista, que não tem elemento anterior (o ponteiro do elemento anterior

vale NULL).

Fig. 6 Arranjo da memória de uma lista duplamente encadeada

Para exemplificar a implementação de listas duplamente encadeadas, vamos novamente

considerar o exemplo simples no qual queremos armazenar valores inteiros na lista.

O nó da lista pode ser representado pela estrutura abaixo e a lista pode ser representada

através do ponteiro para o primeiro nó.

struct lista2 {

int info;

struct lista2* ant;

struct lista2* prox;

};

typedef struct Lista2 Lista2;

Vantagens

Maior facilidade de controle da lista, maior confiabilidade e menor risco de perda acidental

da lista.

Desvantagens

Maior gasto de espaço em disco (2 nós a mais).

Listas circulares

Algumas aplicações necessitam representar conjuntos cíclicos. Por exemplo, as arestas que

delimitam uma face podem ser agrupadas por uma estrutura circular. Para esses casos,

podemos usar listas circulares.

Numa lista circular, o último elemento tem como próximo o primeiro elemento da lista,

formando um ciclo. A rigor, neste caso, não faz sentido falarmos em primeiro ou último

elemento. A lista pode ser representada por

um ponteiro para um elemento inicial

qualquer da lista. A Figura 7 ilustra o arranjo

da memória para a representação de uma lista

circular. Fig. 7 Arranjo da memória de uma lista

circular.

Para percorrer os elementos de uma lista circular, visitamos todos os elementos a partir do

ponteiro do elemento inicial até alcançarmos novamente esse mesmo elemento. O código

abaixo exemplifica essa forma de percorrer os elementos. Neste caso, para simplificar,

consideramos uma lista que armazena valores inteiros.

Devemos salientar que o caso em que a lista é vazia ainda deve ser tratado (se a lista é vazia,

o ponteiro para um elemento inicial vale NULL).

void imprime_circular (Lista* l)

{

Lista* p = l; /* faz p apontar para o nó inicial */

/* testa se lista não é vazia */

if (p) {

{

/* percorre os elementos até alcançar novamente o início */

do {

printf("%d\n", p->info); /* imprime informação do nó */

p = p->prox; /* avança para o próximo nó */

} while (p != l);

Lista circular duplamente encadeada

Uma lista circular também pode ser construída com encadeamento duplo. Neste caso, o que

seria o último elemento da lista passa ter como próximo o primeiro elemento, que, por sua

vez, passa a ter o último como anterior. Com essa construção podemos percorrer a lista nos

dois sentidos, a partir de um ponteiro para um elemento qualquer. Abaixo, ilustramos o

código para imprimir a lista no sentido reverso, isto é, percorrendo o encadeamento dos

elementos anteriores.

void imprime_circular_rev (Lista2* l)

{

Lista2* p = l; /* faz p apontar para o nó inicial */

/* testa se lista não é vazia */

if (p) {

{

/* percorre os elementos até alcançar novamente o início */

do {

printf("%d\n", p->info); /* imprime informação do nó */

p = p->ant; /* "avança" para o nó anterior */

} while (p != l);

}

Vantagens

Economia de espaço em disco (1 nó a menos que a lista duplamente encadeada com

sentinelas), maior confiabilidade em relação ao modelo comum.

Desvantagens

Maior complexidade nos algoritmos.

Projecto

Cartório é um nome genérico que designa uma repartição pública ou privada que tem a

custódia de documentos (cartas) e que lhes dá fé pública.

Registo civil é o termo jurídico que designa o assentamento dos factos da vida de um

indivíduo, tais como o seu nascimento, casamento, divórcio ou morte (óbito). Também são

passíveis de registro civil as interdições, as tutelas, as adopções, os pactos pré-nupciais, o

exercício do poder familiar (chamado de pátrio poder no antigo código civil de 1916 do

Brasil; em Portugal: poder paternal), a opção de nacionalidade, entre outros fatos que

afectam diretamente a relação jurídica entre diferentes cidadãos.

Conclusão

Uma Lista Ligada representa um conjunto de elementos denominados nós onde as

informações são armazenadas.

Cada nó deve obrigatoriamente possuir um apontador para o próximo elemento da lista,

caracterizando assim uma ligação entre nós.

Portanto, um nó é um registo que contém a informação a ser armazenada e o apontador ara o

próximo nó.

A utilização de listas ligadas resolve vários problemas típico que, se usando vectores seria

muito trabalhoso.

Alguns problemas exigem que certas prioridades dos elementos do vectores sejam garantidas

como, por exemplo, a ordem em que o elementos são inseridos define a ordem que serão

removidos.

As listas ligadas conseguem ser mais vantajosas em relação aos vectores pois usando as listas

ligadas, não há necessidade de redimensionar pois considera cada elemento individualmente,

pois num vector o redimensionamento é obrigatóio.

Nas Listas ligadas não é preciso deslocar valores para garantir alguma ordem dos elementos,

mas uma das desvantagens das listas ligadas é que com estas não é possível fazer acesso

imediato ou seja é necessário percorrer alguns elementos.

Podemos utilizar a estrutura dinâmica simplesmente encadeada ou duplamente

encadeada para implementação da lista circular.

Para implementação deste tipo de lista devemos especificar classe NoD composto por

elemento, referência para o elemento seguinte e referência para o elemento anterior.

Listas circulares são listas onde o primeiro e último elemento estão ligados.

Uma lista encadeada é a forma mais simples de representar uma colecção de elementos que

juntos formam uma ordenação linear. Cada elemento da colecção é representado pelo objecto

da classe No . A ordenação é determinada armazenando num nó uma referência para um

elemento e uma referência, chamada de próximo, para o próximo nó da

colecção.

As listas duplamente ligadas consiste quando cada No da lista duplamente encadeada possui

uma ligação não só para o próximo elemento, mas também para o elemento anterior da lista.

Esta variante da lista simplesmente encadeada permite a inserção e a remoção na cabeça e na

cauda da lista com o tempo de execução O(1).

Listas circulares são listas onde o primeiro e último elemento estão ligados. Podemos utilizar

a estrutura dinâmica simplesmente encadeada ou duplamente encadeada para implementação

da lista circular.

Referências Bibliográficas

Adam Drozdek, Estructura de datos y algoritmos en Java, Thomson, 2ª. Edicíon.

Grupo Papime Pe - 100205, Introduccíon a las ciências de La computación con Java,

Universidad Nacional Autónoma de México, 1º Edición, 2007

Detel, Harvey M. Y Deitel, Paul J., Cómo programar en C/C++ y Java, Pearson

Educación, México, 2004, Cuarta Edición.

Caelum Ensino e Soluções em Java – CS -14 Algoritmos Estruturas de Dados em Java

http://www.cin.ufpe.br/~jndm/edados/referencias/Algoritmos%20e%20Estruturas%20

de%20Dados%20em%20Java.pdf (acessado a 15/03/2012)

Algoritmos e Tipos Abstractos de Informação, 2003

http://ltodi.est.ips.pt/atai/index_files/TADs%20em%20Java%20e%20Estruturas.pdf

(acessado a 15/03/2012)

MC 102 – Aoritmos e Programação de Computadores - Listas Ligadas, 2007

http://www.lis.ic.unicamp.br/~mc102/files/mc102jk-a28-4pp.pdf

(acessado a 21/03/2012)

Estruturas de Dados Dinâmicas e Genéricos em Java

Adaptado dos slides do livro: Java, an Introduction to Problem Solving and

Programming, 4ºd Walter Savitch

http://pwp.net.ipl.pt/cc.isel/cvaz/Textos/POO/EDDG.pdf (acessado a 21/03/2012)

W. Celes e J. L. Rangel, Listas Encadeadas

http://www.ic.unicamp.br/~ra069320/PED/MC102/1s2008/Apostilas/Cap10.pdf

(acessado a 25/03/2012)

Nelson Freire , Linguagem JAVA Contentores de Objetos

http://www.dei.isep.ipp.pt/~nfreire/JAVA%20-%20Contentores.pdf

(acessado a 25/03/2012)

Prof. Daniel Lucrédio , Desenvolvimento de Software Orientado a Objetos

http://www2.dc.ufscar.br/~daniel/files/dsoo/08.poo.parte2.pdf

(acessado a 27/03/2012)