Buscar

08_Lista Encadeada (abordagem iterativa)

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 24 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 24 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 24 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

1
Lista Ligada
1
Prof. Cláudio Campelo, PhD
Departamento de Sistemas & Computação / UFCG
Estrutura de Dados e 
Algoritmos
Lista Ligada (Linked List)
2
� É uma estrutura de dados em que objetos são 
arranjados em ordem linear. 
� Ordem estabelecida por ligação (links) entre 
elementos da lista.
� Cada nó da lista armazena um elemento e uma 
referência para o próximo nó da lista. 
5 6 8 null
2
Lista Ligada (Linked List)
3
� Características
� Um dos tipos abstratos de dados fundamentais
� Sequência de tamanho arbitrário e dinâmico de 
elementos de algum tipo base
� Utiliza o espaço necessário (alocação dinâmica)
� A ordem é determinada por um ponteiro e não pelo 
índice como no array
� Acesso sequencial
Lista
4
� Operações
� Inserir
� Remover
� Pesquisar
� Tamanho
� Vazio
3
Questões de Implementação
5
� Implementação estática – implementada com 
arrays
� Implementação dinâmica – através de duas 
abordagens:
� Estrutura recursiva com métodos iterativos
� Cada elemento (nó) da lista contém um dado armazenado e um 
apontador para o próximo elemento da lista
� Estrutura recursiva com métodos recursivos
� Cada elemento (nó) da lista contém um dado armazenado e um 
apontador para o próximo elemento da lista
next
data
Questões de Implementação
6
� Implementação estática – implementada com 
arrays
� Implementação dinâmica – através de duas 
abordagens:
� Estrutura recursiva com métodos iterativos
� Cada elemento (nó) da lista contém um dado armazenado e um 
apontador para o próximo elemento da lista
� Estrutura recursiva com métodos recursivos
� Cada elemento (nó) da lista contém um dado armazenado e um 
apontador para o próximo elemento da lista
next
data
4
Questões de Implementação
7
� Lista vazia
� Representada por um nó especial (NIL) sem dado
� Pode também ser representado por NULL (não 
recomendado)
� Nós sentinela
� Representam a lista vazia e são acrescentados nas 
extremidades das listas
� Simplificam e aceleram alguns algoritmos sobre lista e 
dão garantia de que uma lista sempre contém algum nó 
(mesmo que seja vazio)
null
null
Nó sentilena NIL
Implementação
8
� Exemplo: lista de inteiros não negativos
null
-1 5 2
Lista vazia=NIL
(caso base)
Lista não vazia
(caso indutivo)
Como implementar em Java?
null
-1
headhead
5
Lista (Implementação)
9
public interface LinkedList<T> {
public boolean isEmpty();
public int size();
public T search(T element);
public void insert(T element);
public void remove(T element);
public T[] toArray();
}
Lista (Implementação)
10
public class SingleLinkedListNode<T> {
protected T data;
protected SingleLinkedListNode<T> next;
public SingleLinkedListNode () {
}
public SingleLinkedListNode (T data, Node<T> next) {
this.data = data;
this.next = next;
}
public boolean isNIL(){
return (this.data == null);
}
}
next
data
NIL
next
data
6
Lista (Implementação)
11
public class SingleLinkedListImpl<T> 
implements LinkedList<T>{
protected SingleLinkedListListNode<T> head;
public SingleLinkedListImpl() {
head = new SingleLinkedListNode<T>();
}
...
}
head
NIL
Lista (isEmpty)
12
� Apenas a lista vazia deve retornar true.
isEmpty(){
if head == NIL 
return true
else
return false
}
7
Lista (Inserir)
13
� Listas não ordenadas
� Inserções no início ou no fim
� Listas ordenadas
� Inserções na posição correta (preservar ordem)
inserir(6)
6
NIL
head
6
6
NIL
NIL
NIL
head
inicio
fim
ordenado
Lista (Inserir)
14
� Listas não ordenadas
� Inserções no início ou no fim
� Listas ordenadas
� Inserções na posição correta (preservar ordem)
inserir(3)
6
head
head
3
6
NIL
NIL
NIL
inicio
fim
ordenado
6 NIL
3
6
3
8
Lista (Inserir)
15
� Listas não ordenadas
� Inserções no início ou no fim
� Listas ordenadas
� Inserções na posição correta (preservar ordem)
inserir(5) head
head inicio
fim
ordenado
6 NIL3
6 NIL35
5 NIL63
6 NIL53
Lista (Inserir)
16
� Adotar listas não ordenadas e inserção no final
list-insert(item){
auxHead = head
if(head = NIL){
newHead = new SingleLinkedListNode(item)
newHead.next = head
head = newHead
} else {
while(auxHead.next != NIL){
auxHead = auxHead.next
}
newNode = new SingleLinkedListNode(item)
newNode.next = auxHead.next
auxHead.next = newNode
}
} Qual o tempo de execução?
9
Lista (Procurar)
17
� A procura é sequencial e se dá pelo valor 
armazenado
procurar 5
6 8 5
null
6 8 5
6 8 5
NIL
NIL
NIL
NIL
head
Lista (Procurar)
18
Qual o tempo de execução?
10
Lista (Remover)
19
� As remoções se dão pelo valor armazenado
remover 8 6 8 5
6 5
Como seria a remoção na lista?
6 8 5
NIL
NIL
NIL
head
8
previous aux
Lista (Remover)
20
� As remoções se dão pelo valor armazenado
list-remove(item) {
if (head.data == item) {
head = head.next
} else {
aux = head
while (aux != NIL AND aux.data != item) {
previous = aux
aux = aux.next
}
if (aux != NIL) {
previous.next = aux.next
}
}
}
Qual o tempo de execução?
11
Lista (Tamanho)
21
� Como calcular o tamanho de uma lista?
tamanho
6 8 5
0
6 8 5tamanho
6 8 5
NIL
NIL
NIL
NIL 3
Como seria o algoritmo do tamanho?
Lista (Tamanho)
22
list-size() {
size = 0
aux = head
while aux != NIL {
size = size + 1
aux = aux.next
}
return size
}
� Como calcular o tamanho de uma lista?
12
list-size() {
size = 0
aux = head
while aux != NIL {
size = size + 1
aux = aux.next
}
return size
}
Lista (Tamanho)
23
Qual o tempo de execução?
� Como calcular o tamanho de uma lista?
Lista (toArray)
24
� Deve retornar um array contendo os elementos da 
lista na ordem do head para o final.
T[] list-toArray(){
T[] result = new T[]
aux = head
int count = 0
while aux != NIL {
result[count] = aux.data
aux = aux.next
count++
}
return result
}
13
Exercício
25
� Implemente um método que encontre o maior
elemento de uma lista ligada.
� Implemente um método que encontre o menor
elemento de uma lista ligada.
Lista Duplamente Ligada
26
14
Lista Duplamente Ligada
27
� Cada nó tem referências para os nós sucessor e 
predecessor
� Listas duplamente encadeadas têm a vantagem de 
poderem ser percorridas em ambas as direções
� Isto permite reduzir para a metade o tempo máximo 
para acessar um elemento com base no seu índice
� Head e last ficam acessíveis na lista dupla
-1 nullnull -1 ...null -1 null...
Lista (Implementação)
28
� Como seria a implementação de uma lista 
duplamente ligada?
� A estrutura do nó muda?
� A estrutura da lista em si muda?
next
data
next
data
previous
15
Lista (Implementação)
29
� Como seria a implementação de uma lista 
duplamente ligada?
public class DoubleLinkedListNode<T> 
extends SingleLinkedListNode<T> {
protected DoubleLinkedListNode<T> previous;
public DoubleLinkedListNode() { }
public DoubleLinkedListNode(T data, 
DoubleLinkedListNode<T> next, 
DoubleLinkedListNode<T> previous) {
super(data, next);
this.previous = previous;
}
}
NIL
next
data
previous
Lista (Implementação)
30
� Como seria a implementação de uma lista 
duplamente ligada?
public interface DoubleLinkedList<T> {
public boolean isEmpty();
public int size();
public T search(T element);
public void insert(T element);
public void remove(T element);
public T[] toArray();
public void insertFirst(T element);
public void removeFirst();
public void removeLast();
}
16
Lista(Implementação)
31
� Como seria a implementação de uma lista 
duplamente ligada?
public interface DoubleLinkedList<T> {
public boolean isEmpty();
public int size();
public T search(T element);
public void insert(T element);
public void remove(T element);
public T[] toArray();
public void insertFirst(T element);
public void removeFirst();
public void removeLast();
}
Esses métodos já existem 
em algum lugar?
Lista (Implementação)
32
� Como seria a implementação de uma lista 
duplamente ligada?
public interface DoubleLinkedList<T> extends LinkedList<T> {
public void insertFirst(T element);
public void removeFirst();
public void removeLast();
}
17
public class DoubleLinkedListImpl<T> 
extends SingleLinkedListImpl<T> 
implements DoubleLinkedList<T> {
DoubleLinkedListNode<T> last;
public DoubleLinkedListImpl() {
head = new DoubleLinkedListNode();
last = head;
}
}
Lista (Implementação)
33
last
NIL
head
Algum método herdado precisa ser sobrescrito?
public class DoubleLinkedListImpl<T> 
extends SingleLinkedListImpl<T> 
implements DoubleLinkedList<T> {
DoubleLinkedListNode<T> last;
public DoubleLinkedListImpl() {
head = new DoubleLinkedListNode();
last = head;
}
}
Lista (Implementação)
34
last
head
Algum método herdado precisa ser sobrescrito?
search (por otimização),insert,remove
NIL
18
Lista Dupla(Search)
35
� Pelos dois sentidos: head e last
search(6) 6NIL
head
NIL
head
last
NIL
search(x) 6 NILNIL 10
head
last
last
//busca (com otimização)
List-search(item){
auxHead = head
auxLast = last 
while(auxHead != auxLast and auxHead.next != auxLast
auxHead.data != item and auxLast.data != item){
auxHead = auxHead.next
auxLast = auxLast.previous
}
if auxHead.data == item
return auxHead.data
if auxLast.data == item
return auxLast.data
}
Lista Dupla (Implementação)
36
19
Lista Dupla (Inserir no final = default)
37
inserir(6) 6NIL
head
NIL
head
NIL
inserir(10) 10 NILNIL 6
head
last last
last
Lista Dupla (Inserir no final = default)
38
//insere no final e ajusta os links next e previous
List-insert-last(item){
newLast = new DoubleLinkedListNode(item)
newLast.previous = last
newLast.next = NIL 
last.next = newLast
if (last == NIL) { //para o caso da lista vazia
head = newLast
}
last = newLast
}
20
Lista Dupla (Inserir no início)
39
inserir(6) 6NIL
head
NIL
head
last
NIL
inserir(10) 6 NILNIL 10
head
last
last
//insere no começo e ajusta os links next e previous
List-insert-first(item){
newHead = new DoubleLinkedListNode(item)
newHead.next = head
newHead.previous = NIL
head.previous = newHead
if (head == NIL) { //para o caso da lista vazia
last = newHead
}
head = newHead
}
List-insert(item){
List-insert-first(item)
}
Lista Dupla (Inserir no início)
40
21
Lista Dupla (remover no início)
41
remove-first() NIL
head
6 NIL
head
NIL
10 NILNIL 6
head
remove-first()
10 NIL
head
NIL
last last
last
last
Lista Dupla (remover no início)
42
//remover do inicio
List-remove-first(){
if (head != NIL) {
head = head.next
if (head == NIL) {
last = head
}
head.previous = NIL
}
}
22
Lista Dupla (remover no final)
43
remove-last() NIL
head
last
6 NIL
head
NIL
last
10 NILNIL
last
6
head
remove-last()
6 NIL
head
NIL
last
Lista Dupla (Remover no final)
44
//remover do final
List-remove-last(){
if last != NIL {
last = last.previous
if last == NIL{
head = last
} 
last.next = NIL
}
}
23
Lista Dupla (Remover pela chave = default)
45
remover(6) NIL
head
last
6 NIL
head
NIL
last
10 NILNIL
last
6
head
remover(6)
10 NIL
head
NIL
last
Lista Dupla (Remover pela chave = default)
46
list-remove(item){
if (head.data == item) {
remove-first()
} else {
aux = head
while (aux != NIL) AND (aux.data != item) {
aux = aux.next
}
if (aux != NIL) {
aux.previous.next = aux.next
aux.next.previous = aux.previous
}
}
24
Referências
47
� Capítulo 11

Outros materiais