Estruturas de Dados - Lista Encadeada

Prévia do material em texto

Estruturas de Dados
Filipe Francisco
29 de setembro de 2017
Filipe Francisco Estruturas de Dados 29 de setembro de 2017 1 / 21
Aula passada
O que vimos:
Introduc¸a˜o a estruturas de dados
Lista
Tipos de alocac¸a˜o
sequencial
encadeada
Lista sequencial
Introduc¸a˜o a lista encadeada
Filipe Francisco Estruturas de Dados 29 de setembro de 2017 2 / 21
Lista encadeada
Em uma lista encadeada, alocamos memo´ria dinamicamente, ou seja,
quando ha´ necessidade
evita um eventual desperd´ıcio de memo´ria (evita caso sonde alocamos
mais espac¸o do que utilizaremos)
Portanto, ja´ sabemos que a lista encadeada e´ mais eficiente do ponto
de vista de memo´ria
Pergunta: o uso da lista encadeada evita todo problema de memo´ria?
Em outras palavras: ainda podemos ter problema de memo´ria caso
utilizemos a lista encadeada?
Filipe Francisco Estruturas de Dados 29 de setembro de 2017 3 / 21
Lista encadeada
Problema: disponibilidade de memo´ria
o limite de memo´ria que pode ser alocada para uma lista encadeada e´ a
memo´ria livre do sistema
a disponibilidade de memo´ria livre deve ser checada para cada alocac¸a˜o
Ideia de um reservato´rio de no´s
vetor que conte´m todos os no´s que podem ser usados em listas
encadeadas
limita-se a soma dos tamanhos das listas (na˜o o tamanho de cada lista
individualmente)
Os no´s dispon´ıveis no reservato´rio formam uma lista encadeada (um
dos no´s sera´ o primeiro da lista)
Isso nos permite reutilizar espac¸os de memo´ria que foram liberados
Ale´m do vetor, temos dois pontos associados ao reservato´rio:
disp: primeiro no´ da lista de no´s dispon´ıveis
λ: representa a auseˆncia de no´
Filipe Francisco Estruturas de Dados 29 de setembro de 2017 4 / 21
Reservato´rio de no´s: reserva e libera
Algoritmo: Reserva(R)
Entrada: reservato´rio R
Sa´ıda: ı´ndice do no´ dispon´ıvel, ou λ caso na˜o exista
1 r = R.disp.prox
2 R.disp.prox = R.S [r ].prox
3 retorne r
Algoritmo: Libera(r ,R)
Entrada: ı´ndice do no´ r , reservato´rio R
1 R.S [r ].prox = R.disp.prox
2 R.disp.prox = r
Filipe Francisco Estruturas de Dados 29 de setembro de 2017 5 / 21
Sistema de identificac¸a˜o
Permite a manipulac¸a˜o do conteu´do de um a´tomo a partir do seu
identificador
A´tomo: qualquer conteu´do de memo´ria que pode ser identificado pela
sua localizac¸a˜o
Identificador: identifica um a´tomo para um sistema de identificac¸a˜o
Observac¸o˜es:
supomos que o sistema de identificac¸a˜o e´ capaz de reconhecer λ
as listas encadeadas passam a usar identificadores para realizar o
encadeamento
justificativa: func¸o˜es recebem ponteiros, na˜o estruturas
Exemplo: atribuic¸a˜o de valor x ao campo cp de um a´tomo a
v→chave = x
”→” e´ o operador do sistema de identificac¸a˜o
Filipe Francisco Estruturas de Dados 29 de setembro de 2017 6 / 21
Lista encadeada
Lista formada por uma sequeˆncia de no´s
No´s esta˜o dispostos em posic¸o˜es arbitra´rias de memo´ria
A ordem dos elementos na lista e´ estabelecida pelo uso de no´s para o
armazenamento dos elementos
Cada no´ v e´ formado por dois campos:
v→chave: guarda o elemento
v→prox : indica a localizac¸a˜o do no´ que o sucede na lista
Podemos considerar que v→prox ao mesmo tempo representa o no´
seguinte a v , e representa a ideia de uma lista de no´s apo´s v
Filipe Francisco Estruturas de Dados 29 de setembro de 2017 7 / 21
Lista encadeada
Para representar a auseˆncia de no´, utilizaremos um no´ especial λ
λ ao mesmo tempo representa a auseˆncia de no´, e representa a ideia de
uma lista nula
se v = λ, enta˜o v e´ um no´ nulo
se v→prox = λ, enta˜o v na˜o tem um no´ seguinte a ele
Trabalharemos com a ideia de um no´ vazio como no´ inicial da lista
chamaremos este no´ de no´ cabec¸a da lista
o no´ cabec¸a na˜o pertence de fato a` lista; ele so´ existe para facilitar
nosso trabalho!
o ”corpo” da lista e´ a sequeˆncia de no´s seguintes ao no´ cabec¸a
Para passarmos uma lista encadeada como paraˆmetro, basta
passarmos o no´ cabec¸a
Filipe Francisco Estruturas de Dados 29 de setembro de 2017 8 / 21
Lista encadeada: criar
Algoritmo: CriarListaEncadeada()
Sa´ıda: no inicial vazio da lista encadeada
1 criar novo no´ v
2 v→prox = λ
3 retorne v
Complexidade: O(1)
Filipe Francisco Estruturas de Dados 29 de setembro de 2017 9 / 21
Lista encadeada: buscar
Algoritmo: BuscarEmListaEncadeada(v , x)
Entrada: no´ inicial v , valor x
Sa´ıda: no´ cuja chave e´ x , ou λ se na˜o ha´ no´ com chave x na lista
1 enquanto v→prox 6= λ fac¸a
2 v = v→prox
3 se v→chave == x enta˜o
4 retorne v
5 retorne λ
Complexidade: O(n)
Filipe Francisco Estruturas de Dados 29 de setembro de 2017 10 / 21
Lista encadeada: incluir
Algoritmo: IncluirEmListaEncadeada(v , x)
Entrada: no´ inicial v , valor x
1 criar novo no´ u
2 u→chave = x
3 u→prox = λ
4 enquanto v→prox 6= λ fac¸a
5 v = v→prox
6 v→prox = u
Complexidade: O(n)
Filipe Francisco Estruturas de Dados 29 de setembro de 2017 11 / 21
Lista encadeada: incluir
Algoritmo: IncluirEmListaEncadeada(v , x)
Entrada: no´ inicial v , valor x
1 criar novo no´ u
2 u→chave = x
3 u→prox = λ
4 enquanto v→prox 6= λ fac¸a
5 v = v→prox
6 v→prox = u
Complexidade: O(n)
Pergunta: este me´todo e´ eficiente?
Filipe Francisco Estruturas de Dados 29 de setembro de 2017 12 / 21
Lista encadeada: incluir
Em uma lista, na˜o ha´ necessidade de mantermos a ordem de inserc¸a˜o
dos elementos
o importante e´ garantir que um elemento inserido continue na lista ate´
ser removido (ou seja, na˜o haja perca de dados)
Em uma lista encadeada, a posic¸a˜o onde inserimos o novo no´
influencia na complexidade
Pergunta: podemos escrever um me´todo de inserc¸a˜o mais eficiente
que o anterior (cuja complexidade e´ O(n))?
Em outras palavras: onde devemos adicionar o novo no´ para
obtermos uma complexidade menor?
Filipe Francisco Estruturas de Dados 29 de setembro de 2017 13 / 21
Lista encadeada: incluir
Algoritmo: IncluirEmListaEncadeada(v , x)
Entrada: no´ inicial v , valor x
1 criar novo no´ u
2 u→chave = x
3 u→prox = v→prox
4 v→prox = u
Complexidade: O(1)
Filipe Francisco Estruturas de Dados 29 de setembro de 2017 14 / 21
Lista encadeada: excluir
Algoritmo: ExcluirEmListaEncadeada(v , x)
Entrada: no´ inicial v , valor x
Sa´ıda: no´ exclu´ıdo, ou λ se x na˜o pertence a` lista
1 enquanto v→prox 6= λ e v→prox→chave 6= x fac¸a
2 v = v→prox
3 se v→prox == λ enta˜o
4 retorne λ
5 r = v→prox
6 v→prox = r→prox
7 retorne r
Complexidade: O(n)
Filipe Francisco Estruturas de Dados 29 de setembro de 2017 15 / 21
Lista circular
Lista duplamente encadeada
Cada no´ guarda informac¸o˜es sobre dois no´s: antecessor e sucessor
Em listas circulares, um no´ v e´ uma estrutura com as seguintes
informac¸o˜es:
v → chave: guarda o elemento
v → prox : indica a localizac¸a˜o do no´ que o sucede na lista
v → ant: indica a localizac¸a˜o do no´ que o antecede na lista
Para passarmos uma lista circular como paraˆmetro, basta passarmos o
no´ cabec¸a da lista
novamente, utilizaremos um no´ vazio como no´ cabec¸a
O no´ anterior ao no´ cabec¸a e´ o u´ltimo, e o no´ sucessor do no´ cabec¸a
e´ o primeiro
Na˜o ha´ necessidade de sentinela para verificarmos o fim da lista
Me´todos ficam mais simples se comparado a` lista encadeada
Filipe Francisco Estruturas de Dados 29 de setembro de 2017 16 / 21
Lista circular: criar
Algoritmo: CriarListaCircular()
Sa´ıda: no inicial vazio da lista circular
1 criar novo no´ v
2 v→prox = v
3 v→ant = v
4 retorne v
Complexidade: O(1)
Filipe Francisco Estruturas de Dados 29 de setembro de 2017 17 / 21
Lista circular: buscar
Algoritmo: BuscarEmListaCircular(v , x)
Entrada: no´ inicial v , valor x
Sa´ıda: no´ cuja chave e´ x , ou λ se na˜o ha´no´ com chave x na lista
1 u = v
2 enquanto v→prox 6= u fac¸a
3 v = v→prox
4 se v→chave == x enta˜o
5 retorne v
6 retorne λ
Complexidade: O(n)
Filipe Francisco Estruturas de Dados 29 de setembro de 2017 18 / 21
Lista circular: incluir (no in´ıcio da lista)
Algoritmo: IncluirEmListaCircular(v , x)
Entrada: no´ inicial v , valor x
1 criar novo no´ u
2 u→chave = x
3 u→prox = v→prox
4 u→ant = v
5 v→prox = u
6 u→prox→ant = u
Complexidade: O(1)
Filipe Francisco Estruturas de Dados 29 de setembro de 2017 19 / 21
Lista circular: incluir (no final da lista)
Algoritmo: IncluirEmListaCircular(v , x)
Entrada: no´ inicial v , valor x
1 criar novo no´ u
2 u→chave = x
3 u→prox = v
4 u→ant = v→ant
5 v→ant→prox = u
6 v→ant = u
Complexidade: O(1)
Filipe Francisco Estruturas de Dados 29 de setembro de 2017 20 / 21
Lista circular: excluir
Algoritmo: ExcluirEmListaCircular(v , x)
Entrada: no´ inicial v , valor x
Sa´ıda: no´ exclu´ıdo, ou λ se na˜o ha´ no´ com chave x na lista
1 r = BuscarEmListaCircular(v , x)
2 se r 6= λ enta˜o
3 r→ant→prox = r→prox
4 r→prox→ant = r→ant
5 retorne r
Complexidade: O(n)
Filipe Francisco Estruturas de Dados 29 de setembro de 2017 21 / 21