Listas Duplamente Encadeadas
Profs Prog2 e Lab2 Unisinos
Listas Duplamente Encadeadas
• Cada nó possui dois ponteiros:
previous
element
next
nó
• Vantagem: simplifica certas operações e permite
percorrer a lista nos dois sentidos.
• Desvantagem: gasta mais espaço do que a
simplesmente encadeada (mais um ponteiro em cada
nó) e pode tornar mais complexas certas operações.
Programação II
2
Lista encadeada com referência
ao ultimo elemento da lista
head
Apontador para o
primeiro nó da lista
Apontador para o
último nó da lista
null
início de lista
tail
null
final de lista
Programação II
3
classe DNode
public class DNode<E> {
private E element;
private DNode<E> next;
private DNode<E> previous;
public DNode(E element) {
this (element, null, null);
}
public DNode(E element, DNode<E> next,
DNode<E> previous) {
super();
this.element = element;
this.next = next;
this.previous = previous;
}
public E getElement() {
return element;
}
public void setElement(E element) {
this.element = element;
}
public DNode<E> getNext() {
return next;
}
public void setNext(DNode<E> next) {
this.next = next;
}
public DNode<E> getPrevious() {
return previous;
}
public void setPrevious(DNode<E> previous)
{
this.previous = previous;
}
} // end of class
previous
element
next
nó
Programação II
4
class DLinkedList (1)
public class DLinkedList<E> {
protected DNode<E> head; //nodo cabeça da lista
protected DNode<E> tail; //nodo cauda da lista
protected long size; //número de nodos da lista
public DLinkedList() {
size = 0;
head = tail = null;
}
public boolean isEmpty() {
return head == null;
}
head
tail
Programação II
5
class DLinkedList (2)
public E getFirst() throws UnderflowException {
if (isEmpty())
throw new UnderflowException();
return head.getElement();
}
public E getLast() throws UnderflowException {
if (isEmpty())
throw new UnderflowException();
return tail.getElement();
}
tail
head
b
c
d
e
Programação II
6
class DLinkedList (3)
public void addFirst(E insertItem) {
DNode<E> n = new DNode<E>(insertItem);
}
tail
head
n
b
c
d
e
a
Programação II
class DLinkedList (3)
public void addFirst(E insertItem) {
DNode<E> n = new DNode<E>(insertItem);
if (isEmpty()) {
head = tail = n;
}
}
tail
head
n
a
Programação II
class DLinkedList (3)
public void addFirst(E insertItem) {
DNode<E> n = new DNode<E>(insertItem);
if (isEmpty()) {
head = tail = n;
}
else {
head.setPrevious(n);
n.setNext(head);
head = n;
}
size++;
}
head
n
b
c
d
tail
e
a
Programação II
class DLinkedList (4)
public void addLast(E insertItem) {
DNode<E> n = new DNode<E>(insertItem);
if (isEmpty()) {
head = tail = n;
}
else {
tail.setNext(n);
n.setPrevious(tail);
tail = n;
}
size++;
head
}
b
c
tail
d
e
n
x
Programação II
class DLinkedList (5)
public E removeFirst() throws UnderflowException {
if (isEmpty()) {
throw new UnderflowException();
}
E removedItem = head.getElement();
if (head == tail) {
head = tail = null;
}
return removedItem;
}
head
removedItem
Programação II
tail
e
null
12
class DLinkedList (5)
public E removeFirst() throws UnderflowException {
if (isEmpty()) {
throw new UnderflowException();
}
E removedItem = head.getElement();
if (head == tail) {
head = tail = null;
}
else {
head = head.getNext();
head.setPrevious(null);
}
size--;
return removedItem;
head
}
b
c
Programação II
tail
d
e
13
class DLinkedList (6)
public E removeLast() throws UnderflowException {
if (isEmpty()) {
throw new UnderflowException();
}
E removedItem = tail.getElement();
if (head == tail) {
head = tail = null;
}
else {
DNode<E> penultimo = tail.getPrevious();
tail = penultimo;
tail.setNext(null);
}
size--;
return removedItem;
penultimo
head
}
b
c
Programação II
d
tail
e
14
class DLinkedList (7)
public void print() {
DNode<E> current = head;
while (current != null) {
System.out.println(current.getElement());
current = current.getNext();
}
}
head
2
current =null
3
4
tail
5
Programação II
15
Testando a lista
public static void main(String args[]) {
DLinkedList<Integer> list = new DLinkedList<Integer>();
list.addLast(2);
list.addLast(4);
list.addLast(6);
list.addLast(1);
list.addLast(8);
list.addLast(9);
list.print();
try {
list.removeFirst();
} catch (UnderflowException e) {
e.printStackTrace();
}
list.print();
}
Programação II
16
Exercício 1
• Na classe DLinkedList (implementação de lista
duplamente encadeada), implementar um método
com a seguinte assinatura:
– “private Node<E> find(E key)”.
• Este método deve buscar na lista o nó de chave key
e retorná-lo.
Programação II
17
Exercício 1
public DNode<E> find(E key) {
DNode<E> current = head;
while (current != null) {
if (current.getElement().equals(key)) {
return current;
}
current = current.getNext();
}
return null;
}
Programação II
18
Exercício 2
• Na classe DLinkedList (implementação de lista
duplamente encadeada), implementar um método
com a seguinte assinatura:
– “public boolean addBefore (E el, E key)”.
• Este método deve inserir na lista um nó com chave el
na posição anterior ao nó que contenha a chave key.
Programação II
19
Exercício 2
public boolean addBefore(E el, E chave) {
DNode<E> current = find(chave);
if (current == null) {
return false;
} else if (current == head) {
addFirst(el);
return true;
} else {
DNode<E> n2 = new DNode<E>(el);
DNode<E> before = current.getPrevious();
before.setNext(n2);
n2.setPrevious(before);
n2.setNext(current);
current.setPrevious(n2);
return true;
}
}
Programação II
20