Listas Encadeadas Circulares
Listas Duplamente Encadeadas
Listas Encadeadas Circulares
Motivação para listas duplamente
encadeadas e circulares
3
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
4
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
5
Listas circulares
Ponteiros aterrados representam listas circulares vazias
6
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
tmp
tmp
tmp
7
Listas circulares – exclusão
• 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
8
Implementação Java
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;
}
10
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;
}
11
// transformar primeiro em último
Listas circulares – exclusão
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;
}
12
Implementação C++
Listas circulares – Inclusão na frente
template <class T>
void LinkedList<T>::InsertFront (T const& item)
{
ListElement<T>* const tmp = new ListElement<T> (item,0);
tail->next = tmp;
if(tail == 0)
tail = tmp;
else
{
tmp->next = tail->next;
}
tail->next = tmp;
}
14
Listas circulares – Inclusão no final
template <class T>
void LinkedList<T>::InsertFront (T const& item)
{
// frente será o sucessor de tail
// depois tail será tail->next
ListElement<T>* const tmp = new ListElement<T> (item,0);
ptr->next = tmp;
if(tail == 0)
tail = tmp;
else
{
tmp->next = tail->next;
}
tail->next = tmp;
tail = tmp; // transformar primeiro em último
}
15
Listas circulares – exclusão
template <class T>
void LinkedList<T>::ExtractLast (T const& item)
{
if (tail == 0)
throw invalid_argument "item not found");
ListElement<T>* tmp = 0;
tmp = tail->next;
item = tmp->datum;
tail->next = tmp->next
if (tail == tmp)
tail = 0;
delete tmp;
}
16
Listas Duplamente Encadeadas
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
18
LISTAS DUPLAMENTE ENCADEADAS
null
datum
datum
d a tu m
datum null
Fig. 5.7 Listas duplamente en
19
LISTAS DUPLAMENTE ENCADEADAS
• Uma propriedade característica das listas
duplamente encadeadas é expressa por:
p.next.prev = p = p.prev.next
• EXEMPLO
20
LISTAS DUPLAMENTE ENCADEADAS
Memória
Endereço
100
150
200
220
300
21
prev
NULL
200
100
150
220
datum
a
c
b
d
e
next
200
220
150
300
NULL
LISTAS DUPLAMENTE ENCADEADAS –
Inclusão
• inclusão do nó apontado por q à direita
do nó apontado por p
22
LISTAS DUPLAMENTE ENCADEADAS –
Exclusão
• exclusão do nó apontado por q
23
Implementação Java
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; }
// ...
}
// ...
}
25
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;
}
// ...
}
26
// esvaziar uma lista
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; }
// ...
}
27
//teste de lista vazia
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;
}
// ...
}
28
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;
}
// ...
}
29
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;
}
// ...
}
30
Método assign
public class DoubleLinkedList {
protected Element head;
protected Element tail;
// a lista corrente será uma cópia da lista list
public void assign(DoubleLinkedList list)
{
if(list != this)
{
purge ();
for(Element ptr = list.head;
ptr != null; ptr = ptr.next)
{
append (ptr.datum);
}
}
}
// ...
}
31
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;
}
if(ptr == null)
throw new IllegalArgumentException
("item not found");
if(head == tail)
{
head = null;
tail = null;
}
32
Método extract (2)
}
33
if(ptr == head) // exclui head
{
ptr.next.prev = null;
head = ptr.next;
}
else
if(ptr == tail)
// exclui tail
{
ptr.prev.next = null;
tail = ptr.prev;
}
else
{
ptr.prev.next = ptr.next;
ptr.next.prev = ptr.prev;
}
} // fim do extract
// fim da classe DoubleLinkedList
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 {
this.next.prev = tmp;
this.next = tmp;
}
}
34
Método insertBefore
// Inclui item antes do objeto corrente
public void insertBefore(Object item) {
Element tmp = new Element(item, this, this.prev);
if(head == this)
{
this.prev = tmp;
head = tmp;
}
else {
prev.next = tmp;
this.prev = tmp;
}
}
// ...
}
// ...
}
35
Implementação C++
Definição das Classes DoubleLinkedList<T>
e ListElement<T> (1)
template <class T>
class DoubleLinkedList;
template <class T>
class ListElement {
T datum;
ListElement* next;
ListElement* prev;
ListElement (T const&, ListElement*);
public:
T const& Datum () const;
ListElement const* Next () const;
ListElement const* Prev() const:
friend DoubleLinkedList<T>;
};
37
Definição das Classes DoubleLinkedList<T>
e ListElement<T> (2)
template <class T>
class DoubleLinkedList
{
ListElement<T>* head;
ListElement<T>* tail;
public:
DoubleLinkedList ();
~DoubleLinkedList ();
DoubleLinkedList (DoubleLinkedList const&);
DoubleLinkedList& operator = (DoubleLinkedList const&);
38
Definição das Classes DoubleLinkedList<T>
e ListElement<T> (3)
ListElement<T> const* Head () const;
ListElement<T> const* Tail () const;
bool IsEmpty () const;
T const& First () const;
T const& Last () const;
void
void
void
void
void
void
};
39
Prepend (T const&);
Append (T const&);
Extract (T const&);
Purge ();
InsertAfter (ListElement<T> const*, T const&);
InsertBefore (ListElement<T> const*, T const&);
Definição de Funções Membro da
Classe ListElement<T>
template <class T>
ListElement<T>::ListElement (
T const& _datum, ListElement<T>* _next, ListElement<T>* _prev) :
datum (_datum), next (_next), prev (_prev)
{}
template <class T>
T const& ListElement<T>::Datum () const
{ return datum; }
template <class T>
ListElement<T> const* ListElement<T>::Next () const
{ return next; }
ListElement<T> const* ListElement<T>::Prev () const
{ return prev; }
40
Construtor Default da Classe ListElement<T>
template <class T>
DoubleLinkedList<T>::DoubleLinkedList () :
head (0),
tail (0)
{}
41
Definição de Funções Membro Destrutor
e Purge da Classe ListElement<T>
template <class T>
void DoubleLinkedList<T>::Purge ()
{
while (head != 0)
{
ListElement<T>* const tmp = head;
head = head->next;
delete tmp;
}
tail = 0;
}
template <class T>
DoubleLinkedList<T>::~DoubleLinkedList ()
{ Purge (); }
42
Definição de Funções Accessor da Classe ListElement<T>
template <class T>
ListElement<T> const* DoubleLinkedList<T>::Head () const
{ return head; }
template <class T>
ListElement<T> const* DoubleLinkedList<T>::Tail () const
{ return tail; }
template <class T>
bool DoubleLinkedList<T>::IsEmpty () const
{ return head == 0; }
43
Definição de Funções First e Last da
Classe ListElement<T>
template <class T>
T const& DoubleLinkedList<T>::First () const
{
if(head == 0)
throw domain_error ("list is empty");
return head->datum;
}
template <class T>
T const& DoubleLinkedList<T>::Last () const
{
if(tail == 0)
throw domain_error ("list is empty");
return tail->datum;
}
44
Definição de Função Prepend da Classe ListElement<T>
template <class T>
void DoubleLinkedList<T>::Prepend (T const& item)
{
ListElement<T>* const tmp = new ListElement<T>
(item, head, 0);
if(head == 0)
tail = tmp;
head->prev = tmp;
head = tmp;
}
45
Definição de Função Append da Classe ListElement<T>
template <class T>
void DoubleLinkedList<T>::Append (T const& item)
{
ListElement<T>* const tmp = new ListElement<T>
(item, 0, tail);
if(head == 0)
head = tmp;
else
tail->next = tmp;
tail = tmp;
}
46
Definição de Função Construtor Copy
da Classe ListElement<T> (1)
template <class T>
DoubleLinkedList<T>::DoubleLinkedList (DoubleLinkedList<T>
const& DoubleLinkedList) :
head (0),
tail (0),
{
ListElement<T> const* ptr;
for(ptr = DoubleLinkedList.head; ptr != 0; ptr = ptr->next)
Append (ptr->datum);
}
47
Definição de Função Construtor Copy da
Classe ListElement<T> (2)
template <class T>
DoubleLinkedList<T>& DoubleLinkedList<T>::operator =
(DoubleLinkedList<T> const& DoubleLinkedList)
{
if(&DoubleLinkedList != this)
{
Purge ();
ListElement<T> const* ptr;
for(ptr = DoubleLinkedList.head; ptr != 0; ptr = ptr->next)
Append (ptr->datum);
}
return *this;
}
48
Definição de Função Extract da
Classe ListElement<T> (1)
template <class T>
void DoubleLinkedList<T>::Extract (T const& item)
{
ListElement<T>* ptr = head;
while(ptr != 0 && ptr->datum != item)
{
ptr = ptr->next;
}
if(ptr == 0)
throw invalid_argument ("item not found");
if(head == tail) // exclui head
{
head= 0;
tail = 0;
}
49
Definição de Função Extract da Classe
ListElement<T> (2)
if(ptr == head) // exclui head
{
ptr->next->prev = 0;
head = ptr->next;
}
else
if(ptr == tail) //exclui tail
{
ptr->prev->next = 0;
tail = prevPtr;
}
else
{
ptr->prev->next = ptr->next;
ptr->next->prev = ptr->prev;
}
delete ptr;
}
50
Definição da Função InsertAfter da
Classe ListElement<T>
template <class T>
void DoubleLinkedList<T>::InsertAfter
(ListElement<T> const* arg,T const& item)
{
ListElement<T>* ptr = const_cast<ListElement<T>*> (arg);
if(ptr == 0)
throw invalid_argument ("invalid position");
ListElement<T>* const tmp = new ListElement<T>
(item, ptr->next, ptr);
ptr->next = tmp;
if(tail == ptr)
tail = tmp;
else
ptr->next->prev = tmp;
}
51
Definição da Função InsertBefore da
Classe ListElement<T> (1)
template <class T>
void LinkedList<T>::InsertBefore (ListElement<T> const* arg,
T const& item)
{
ListElement<T>* ptr = const_cast<ListElement<T>*> (arg);
if(ptr == 0)
throw invalid_argument ("invalid position");
ListElement<T>* const tmp = new ListElement<T>
(item, ptr, ptr->prev);
52
Definição da Função InsertBefore da
Classe ListElement<T> (2)
if(head == ptr)
{ptr->prev = tmp;
head = tmp;
}
else
{
ptr->prev = tmp;
ptr->prev->next = tmp;
}
}
53