Upload
others
View
3
Download
0
Embed Size (px)
Citation preview
Estruturas de Informação I - Aula 12Listas encadeadas
João Araujo Ribeiro
Universidade do Estado do Rio de Janeiro
Departamento de Engenharia de Sistemas e Computação
João Araujo Ribeiro (UERJ) Estruturas de Informação I EstrInf 1 / 33
Resumo
1 EI12 - Listas Encadeadas
2 EI12 - Pilha como Lista Encadeada
3 EI12 - Fila como Lista Encadeada
4 EI12 - Lista Encadeada Circular
5 EI12 - Lista Duplamente Encadeada
João Araujo Ribeiro (UERJ) Estruturas de Informação I EstrInf 2 / 33
EI12 - Listas Encadeadas
Listas EncadeadasVimos anteriormente os diversos tipos de listas possíveis. Neste capítulo
vamos nos aprofundar na programação e uso de listas encadeadas
João Araujo Ribeiro (UERJ) Estruturas de Informação I EstrInf 3 / 33
EI12 - Listas Encadeadas
Lista Simplesmente encadeada
Uma lista simplesmente encadeada é uma coleção de nós que coletivamente
formam uma sequência linear.
João Araujo Ribeiro (UERJ) Estruturas de Informação I EstrInf 4 / 33
EI12 - Listas Encadeadas
Head e Tail
O primeiro nó é conhecido como Head e o último como Tail.
João Araujo Ribeiro (UERJ) Estruturas de Informação I EstrInf 5 / 33
EI12 - Listas Encadeadas
Inserção no início da lista
João Araujo Ribeiro (UERJ) Estruturas de Informação I EstrInf 6 / 33
EI12 - Listas Encadeadas
Algoritmo de inserção no início
1 Algoritmo insere_inicio(L, e):
2 newest = Node(e) {cria um novo nó para armazenar o elemento e}
3 newest.next = L.head {aponta a próxima referência do novo nó
4 para o antigo nó head}
5 L.head = newest {Aponta head para o novo nó}
6 L.size = L.size + 1 {incrementa o contador de nós}
João Araujo Ribeiro (UERJ) Estruturas de Informação I EstrInf 7 / 33
EI12 - Listas Encadeadas
Inserção no �m da lista eencadeada
João Araujo Ribeiro (UERJ) Estruturas de Informação I EstrInf 8 / 33
EI12 - Listas Encadeadas
Algoritmo de inserção no �m
1 Algoritmo insere_fim(L, e):
2 newest = Node(e) {cria novo nó para armazenar elemento e}
3 newest.next = None {Faz o próximo apontar para None}
4 L.tail.next = newest {Faz antigo próximo de tail apontar para o novo nó}
5 L.tail = newest {faz a variável tail apontar para novo nó}
6 L.size = L.size + 1 {incrementa o contador de nós}
João Araujo Ribeiro (UERJ) Estruturas de Informação I EstrInf 9 / 33
EI12 - Listas Encadeadas
Remover elemento de lista encadeada
João Araujo Ribeiro (UERJ) Estruturas de Informação I EstrInf 10 / 33
EI12 - Listas Encadeadas
Algoritmo de remoção
1 Algorithm remove_primeiro(L):
2 if L.head is None then
3 Indica erro: a lista está vazia.
4 L.head = L.head.next {faz head apontar para o próximo}
5 L.size = L.size - 1 {decrementa contador}
João Araujo Ribeiro (UERJ) Estruturas de Informação I EstrInf 11 / 33
EI12 - Listas Encadeadas
Removendo último
Infelizmente não podemos remover o último elemento tão facilmente.
Mesmo mantendo um ponteiro para o último elemento, numa lista
encadeada simples devemos começar de head e atravessar a lista
inteiramente para atingir o último elemento. Este problema não haveria se
a lista fosse duplamente encadeada.
João Araujo Ribeiro (UERJ) Estruturas de Informação I EstrInf 12 / 33
EI12 - Pilha como Lista Encadeada
Implementando uma pilha como lista encadeada
Como base, implementamos uma classe _Node
1 class _Node:
2 """Classe não publica para armazenar um nó."""
3 __slots__ = �_element� , �_next�
4 def init (self, element, next):
5 self._element = element
6 self._next = next
João Araujo Ribeiro (UERJ) Estruturas de Informação I EstrInf 13 / 33
EI12 - Pilha como Lista Encadeada
Pilha como lista encadeada 1/3
1 class LinkedStack:
2 """Implementação LIFO de Pilha usando lista encadeada."""
3 #-------------------------- Classe Node --------------------------
4 class _Node:
5 """Classe não pública para armazenar um nó."""
6 __slots__ = �_element� , �_next�
7
8 def __init__(self, element, next): # carrega nó
9 self._element = element # referência para elemento do usuário
10 self._next = next # referência para o próximo nó
11 #------------------------------- métodos da Pilha -----------------------
12 def __init__ (self):
13 """Cria pilha vazia."""
14 self._head = None # referência para head
15 self._size = 0 # numero de elementos
16
17 def __len__ (self):
18 """Retorna o número de elementos na pilha."""
19 return self._size
João Araujo Ribeiro (UERJ) Estruturas de Informação I EstrInf 14 / 33
EI12 - Pilha como Lista Encadeada
Pilha como lista encadeada 2/3
21 def is_empty(self):
22 """Retorna True se a pilha está vazia."""
23 return self._size == 0
24
25 def push(self, e):
26 """Adiciona element e no topo da pilha."""
27 self._head = self._Node(e, self._head) # cria novo nó
28 self._size += 1
29
30 def top(self):
31 """Retorna (mas não remove) o elemento do topo da pilha.
32 Levanta exceção Empty se pilha está vazia.
33 """
34 if self.is_empty( ):
35 raise Empty(�Pilha Vazia�)
36 return self._head._element # topo da pilha éa cabeça da lista
João Araujo Ribeiro (UERJ) Estruturas de Informação I EstrInf 15 / 33
EI12 - Pilha como Lista Encadeada
Pilha como lista encadeada 3/3
38 def pop(self):
39 """Remove e retorna o elemento do topo da pilha.
40 Levanta exceção Empty se pilha está vazia.
41 """
42 if self.is_empty( ):
43 raise Empty(�Pilha Vazia�)
44 answer = self._head._element
45 self._head = self._head._next
46 self._size -= 1
47 return answer
João Araujo Ribeiro (UERJ) Estruturas de Informação I EstrInf 16 / 33
EI12 - Fila como Lista Encadeada
Fila como lista encadeada 1/3
1 class LinkedQueue:
2 """Implementação FIFO de Fila usando lista encadeada."""
3 #-------------------------- Classe Node --------------------------
4 class _Node:
5 """Classe não pública para armazenar um nó."""
6 __slots__ = �_element� , �_next�
7
8 def __init__(self, element, next): # carrega nó
9 self._element = element # referência para elemento do usuário
10 self._next = next # referência para o próximo nó
11 #------------------------------- métodos da Fila -----------------------
12 def __init__ (self):
13 """Cria fila vazia."""
14 self._head = None
15 self._tail = None
16 self._size = 0 # numero de elementos
17
18 def __len__ (self):
19 """Retorna o número de elementos na fila."""
20 return self._size
João Araujo Ribeiro (UERJ) Estruturas de Informação I EstrInf 17 / 33
EI12 - Fila como Lista Encadeada
Fila como lista encadeada 2/3
22 def is_empty(self):
23 """Retorna True se a fila está vazia."""
24 return self._size == 0
25
26 def first(self):
27 """Retorna (mas não remove) o elemento da frente da fila."""
28 if self.is_empty( ):
29 raise Empty(�Fila Vazia�)
30 return self._head._element
31
32 def dequeue(self):
33 """Remove e retorna o elemento do frente da fila.
34 Levanta exceção Empty se fila está vazia..
35 """
36 if self.is_empty( ):
37 raise Empty(�Fila Vazia�)
João Araujo Ribeiro (UERJ) Estruturas de Informação I EstrInf 18 / 33
EI12 - Fila como Lista Encadeada
Fila como lista encadeada 3/3
38 answer = self._head._element
39 self._head = self._head._next
40 self._size -= 1
41 if self.is_empty( ):# caso especial fila vazia
42 self._tail = None
43 return answer
44
45 def enqueue(self, e):
46 """Adiciona elemento ao fim da fila."""
47 newest = self._Node(e, None) # nó será o novo tail
48 if self.is_empty( ):
49 self._head = newest # caso especial: previamente vazia
50 else:
51 self._tail._next = newest
52 self._tail = newest
53 self._size += 1
João Araujo Ribeiro (UERJ) Estruturas de Informação I EstrInf 19 / 33
EI12 - Lista Encadeada Circular
Lista Encadeada Circular
João Araujo Ribeiro (UERJ) Estruturas de Informação I EstrInf 20 / 33
EI12 - Lista Encadeada Circular
Lista Encadeada Circular sem início nem �m
João Araujo Ribeiro (UERJ) Estruturas de Informação I EstrInf 21 / 33
EI12 - Lista Encadeada Circular
Fila Circular como lista encadeada 1/3
1 class CircularQueue:
2 """Implementação de Fila como lista encadeada circular."""
3 class _Node:
4 """Classe não publica para armazenar um nó."""
5 __slots__ = �_element� , �_next�
6
7 def __init__(self, element, next): # carrega nó
8 self._element = element # referência para elemento do usuário
9 self._next = next # referência para o próximo nó
10
11 def __init__ (self):
12 """Cria fila vazia."""
13 self._tail = None
14 self._size = 0
15
16 def __len__ (self):
17 """Retorna o número de elementos na fila."""
18 return self._size
19
20 def is_empty(self):
21 """Retorna True se a fila está vazia."""
22 return self._size == 0
João Araujo Ribeiro (UERJ) Estruturas de Informação I EstrInf 22 / 33
EI12 - Lista Encadeada Circular
Fila Circular como lista encadeada 2/3
24 def first(self):
25 """Retorna (mas não remove) o elemento da frente da fila."""
26 if self.is_empty( ):
27 raise Empty(�Fila Vazia�)
28 head = self._tail._next
29 return head._element
30
31 def dequeue(self):
32 """Remove e retorna o elemento do frente da fila.
33 Levanta exceção Empty se fila está vazia..
34 """
35 if self.is_empty( ):
36 raise Empty(�Fila Vazia�)
37 oldhead = self._tail._next
38 if self._size == 1: # remove único elemento
39 self._tail = None # fila fica vazia
40 else:
41 self._tail._next = oldhead._next # bypass antigo head
42 self._size -= 1
43 return oldhead._element
João Araujo Ribeiro (UERJ) Estruturas de Informação I EstrInf 23 / 33
EI12 - Lista Encadeada Circular
Fila Circular como lista encadeada 3/3
44
45 def enqueue(self, e):
46 """Adiciona elemento ao fim da fila."""
47 newest = self._Node(e, None) # nó será o novo tail
48 if self.is_empty( ):
49 newest._next = newest # circular
50 else:
51 newest._next = self._tail._next # novo nó aponta para head
52 self._tail._next = newest # antigo tail aponta para novo nó
53 self._tail = newest # novo nó se torna tail
54 self._size += 1
55
56 def rotate(self):
57 """Roda elemento frontal para fim da fila."""
58 if self._size > 0:
59 self._tail = self._tail._next # antigo head vira novo tail
João Araujo Ribeiro (UERJ) Estruturas de Informação I EstrInf 24 / 33
EI12 - Lista Duplamente Encadeada
Lista duplamente encadeada
Numa lista duplamente encadeada cada nó mantém uma referência para o
nó imediatamente anterior e outra para o nó imediatamente posterior. (no
exemplo abaixo, usando sentinelas)
João Araujo Ribeiro (UERJ) Estruturas de Informação I EstrInf 25 / 33
EI12 - Lista Duplamente Encadeada
Por que usar sentinelas?
Poderíamos implementar a lista duplamente encadeada sem sentinelas, mas
elas simpli�cam enormemente a inserção e eliminação de nós, pois sempre
existe um nó antes e depois e não precisamos tratar casos especiais, como
anteriormente
João Araujo Ribeiro (UERJ) Estruturas de Informação I EstrInf 26 / 33
EI12 - Lista Duplamente Encadeada
Inserindo elemento
João Araujo Ribeiro (UERJ) Estruturas de Informação I EstrInf 27 / 33
EI12 - Lista Duplamente Encadeada
Inserindo elemento no início
João Araujo Ribeiro (UERJ) Estruturas de Informação I EstrInf 28 / 33
EI12 - Lista Duplamente Encadeada
Removendo elemento
João Araujo Ribeiro (UERJ) Estruturas de Informação I EstrInf 29 / 33
EI12 - Lista Duplamente Encadeada
Nó para lista duplamente encadeada
1 class _Node:
2 """Classe não pública para armazenar um nó."""
3 __slots__ = �_element� , �_prev� , �_next�
4
5 def __init__ (self, element, prev, next):
6 self._element = element
7 self._prev = prev
8 self._next = next
João Araujo Ribeiro (UERJ) Estruturas de Informação I EstrInf 30 / 33
EI12 - Lista Duplamente Encadeada
lista duplamente encadeada 1/2
1 # coding=UTF-8
2 class _DoublyLinkedBase:
3 """Uma classe base para lista duplamente encadeada."""
4 class _Node:
5 """Classe não pública para armazenar um nó."""
6 __slots__ = �_element� , �_prev� , �_next�
7
8 def __init__ (self, element, prev, next):
9 self._element = element
10 self._prev = prev
11 self._next = next
12
13 def __init__(self):
14 """Cria lista vazia"""
15 self._header = self._Node(None, None, None)
16 self._trailer = self._Node(None, None, None)
17 self._header._next = self._trailer # trailer após header
18 self._trailer._prev = self._header # header antes de trailer
19 self._size = 0
20
21 def __len__ (self):
22 """Retorna o número de elementos na lista."""
João Araujo Ribeiro (UERJ) Estruturas de Informação I EstrInf 31 / 33
EI12 - Lista Duplamente Encadeada
Lista duplamente encadeada 2/2
24
25 def is_empty(self):
26 """Retorna True se a fila está vazia."""
27 return self._size == 0
28
29 def _insert_between(self, e, predecessor, successor):
30 """Adiciona elemento e entre dois nós existentes e retorna novo nó."""
31 newest = self._Node(e, predecessor, successor)
32 predecessor._next = newest
33 successor._prev = newest
34 self._size += 1
35 return newest
36
37 def _delete_node(self, node):
38 """Deleta nó não sentinela e retorna seu elemento."""
39 predecessor = node._prev
40 successor = node._next
41 predecessor._next = successor
42 successor._prev = predecessor
43 self._size -= 1
44 element = node._element
45 node._prev = node._next = node._element = None
João Araujo Ribeiro (UERJ) Estruturas de Informação I EstrInf 32 / 33
EI12 - Lista Duplamente Encadeada
FIM
João Araujo Ribeiro (UERJ) Estruturas de Informação I EstrInf 33 / 33