Listas Encadeadas Circulares
Listas Duplamente Encadeadas
Motivação para listas duplamente
encadeadas e circulares
2
LISTAS CIRCULARES
Um dos inconvenientes do emprego de listas
encadeadas consiste no caso de, dado um ponteiro
para um nó p de uma lista encadeada, não se ter
acesso aos nós que precedem o nó p
Este inconveniente pode ser contornado com o
emprego de listas circulares
Listas circulares são listas encadeadas nas quais o
ponteiro do último nó deixa de ser aterrado para
apontar o primeiro nó da lista
3
LISTAS CIRCULARES
Uma lista circular não tem um primeiro nó nem
último nó “naturais”
Uma convenção útil é apontar o ponteiro externo
(“tail” para a lista circular) para o último nó, sendo
o conceito de último vindo de tempo de inclusão
O ponteiro head torna-se permanentemente
aterrado e o ponteiro tail aponta o último elemento
da lista
Outra alternativa consiste em usar apenas um
ponteiro externo head
4
Listas circulares
Ponteiros aterrados representam listas circulares vazias
5
Listas circulares – inclusão
Inclusão de um nó com endereço apontado por tmp na frente e
na retaguarda de uma lista circular apontada por tail
A inclusão na retaguarda é uma inclusão na frente seguida de
tail ← tmp
6
Listas circulares – inclusão na frente
// frente será o sucessor de tail
public void insertFront(Object item){
Element tmp = new Element (item, null);
if (tail = null)
tail = tmp;
else {
tmp.next = tail.next;
tail.next = tmp;
}
}
7
Listas circulares – inclusão no final
// frente será o sucessor de tail
// depois tail será tail.next
public void insertRear(Object item){
Element tmp = new Element (item, null);
if (tail = null)
tail = tmp;
else {
tmp.next = tail.next;
tail.next = tmp;
}
tail = tmp;
// transformar primeiro em último
}
8
Listas circulares – exclusão (1)
Exclusão do nó da frente de uma lista circular na
qual tail aponta o último nó com a recuperação
da informação desse nó em y
9
Listas circulares – exclusão (2)
public void extractLast(Object item)
{
if (tail = null)
throw new IllegalArgumentException
("item not found");
Element tmp = tail.next;
item = tmp.datum;
tail.next = tmp.next
if (tail = tmp)
tail = null;
}
10
LISTAS DUPLAMENTE ENCADEADAS
Alterando-se os nós de listas encadeadas de
forma que cada nó passe a contar, além do
registro de informação e do ponteiro para o
sucessor, também um ponteiro para
antecessor se obtém listas duplamente
encadeadas
11
LISTAS DUPLAMENTE ENCADEADAS
null
datum
datum
d a tu m
datum null
Fig. 5.7 Listas duplamente enca
12
LISTAS DUPLAMENTE ENCADEADAS
Uma propriedade característica das listas
duplamente encadeadas é expressa por:
p.next.prev = p = p.prev.next
EXEMPLO
13
LISTAS DUPLAMENTE ENCADEADAS
Memória
Endereço
100
150
200
220
300
prev
NULL
200
100
150
220
datum
a
c
b
d
e
next
200
220
150
300
NULL
14
LISTAS DUPLAMENTE ENCADEADAS –
Inclusão (1)
inclusão do nó apontado por q à direita do
nó apontado por p
15
LISTAS DUPLAMENTE ENCADEADAS –
Exclusão (1)
exclusão do nó apontado por q
16
Listas Duplamente Encadeadas
Implementação
Classe DoubleLinkedList
public class DoubleLinkedList {
protected Element head;
// cabeça
protected Element tail;
// cauda
public final class Element { // elemento do lista
Object datum;
// dado do elemento ou item
Element next;
// ponteiro para sucessor
Element prev;
// ponteiro para antecessor
Element(Object datum, Element next, Element prev) { // construtor
this.datum = datum;
this.next = next;
this.prev = prev;
}
public Object getDatum()
// obter dado
{ return datum; }
public Element getNext()
// obter sucessor
{ return next; }
public Element getPrev()
// obter antecessor
{ return prev; }
// ...
}
// ...
}
18
Métodos Construtor e purge
public class DoubleLinkedList
{
protected Element head;
protected Element tail;
public DoubleLinkedList () // construir uma lista
{}
public void purge ()
{
head = null;
tail = null;
}
// ...
// esvaziar uma lista
}
19
Métodos getHead, getTail e isEmpty
public class DoubleLinkedList
{
protected Element head;
protected Element tail;
public Element getHead () // cabeça da lista
{ return head; }
public Element getTail () // cauda da lista
{ return tail; }
public boolean isEmpty ()
{ return head == null; }
//teste de lista vazia
// ...
}
20
Métods getFirst e getLast
public class DoubleLinkedList {
protected Element head;
protected Element tail;
public Object getFirst() {
// obter o primeiro elemento
//da lista
if(head == null)
throw new ContainerEmptyException();
return head.datum;
}
public Object getLast() {
// obter o último elemento
//da lista
if(tail == null)
throw new ContainerEmptyException();
return tail.datum;
}
// ...
}
21
Método prepend
public class DoubleLinkedList
{
protected Element head;
protected Element tail;
// inluir o objeto item no início da lista corrente
public void prepend(Object item)
{
Element tmp = new Element(item, head, null);
if(head == null)
tail = tmp;
head.prev = tmp;
head = tmp;
}
// ...
}
22
Método append
public class DoubleLinkedList
{
protected Element head;
protected Element tail;
// incluir o objeto item no final da lista corrente
public void append (Object item)
{
Element tmp = new Element (item, null, tail);
if(head == null)
head = tmp;
else
tail.next = tmp;
tail = tmp;
}
// ...
}
23
Método assign
public class DoubleLinkedList {
protected Element head;
protected Element tail;
// a lista list será uma cópia da lista corrente
public void assign(DoubleLinkedList list)
{
if(list != this)
{
purge ();
for(Element ptr = list.head;
ptr != null; ptr = ptr.next)
{
append (ptr.datum);
}
}
}
// ...
}
24
Método extract (1)
public class DoubleLinkedList
{
protected Element head;
protected Element tail;
// Exclui objeto item
public void extract(Object item)
{
Element ptr = head;
while(ptr != null && ptr.datum != item)
{
ptr = ptr.next;
}
// encontrado ptr
// se for válido excluir elemento
25
Método extract (2)
if(ptr == null)
throw new IllegalArgumentException("item not found");
if(ptr == head) // exclui head
{
ptr.next.prev = null;
head = ptr.next;
}
else
{
ptr.prev.next = ptr.next;
ptr.next.prev = ptr.prev;
}
if(ptr == tail)
// exclui tail
{
ptr.prev.next = null;
tail = ptr.prev;
}
}
}
26
Método insertAfter
// Inclui item depois do objeto corrente
public void insertAfter(Object item)
{
Element tmp = new Element (item, next, this);
if(tail == this){
this.next = tmp;
tail = tmp;
}
else {
next.prev = tmp;
this.next = tmp;
}
}
27
Método insertBefore
// Inclui item antes do objeto corrente
public void insertBefore(Object item) {
Element tmp = new Element(item, this, this.prev);
if(this == head)
{
this.prev = tmp;
head = tmp;
}
else {
prev.next = tmp;
this.prev = tmp;
}
}
// ...
}
// ...
}
28