Listas
Simplesmente Encadeadas
Professores de Programação II
Criando um objeto
• Objeto é uma instância de uma classe;
• Usamos o operador new para criar um objeto.
Variável que conterá uma
referência a um objeto
ContaCorrente minhaConta;
minhaConta = new ContaCorrente ( );
Criação do objeto
ContaCorrente minhaConta = new ContaCorrente ( );
Programação II
2
Garbage Collection
String str = “Primeiro espaço”;
System.out.println (“Usando memória original: “+str);
str = “Outro espaço”;
System.out.println (“Usando outro espaço de memória: “+str);
Primeiro espaço
str
Área de memória
liberada pelo
Garbage Collection
10 100
Outro espaço
System.gc();
10
100
Não obriga a limpar, mas “pede”
para que o Garbage Collection limpe se possível
Programação II
3
Listas: Tipo de Armazenamento
• O tipo de armazenamento de uma lista linear pode ser
classificado de acordo com a posição relativa na memória
de dois nós consecutivos na lista (sempre contígua ou
não).
• Lista linear com alocação estática de memória
–
–
–
–
Também chamadas de Listas Sequenciais
Nós em posições contíguas de memória
Geralmente representado por arrays
Útil para implementar filas e pilhas (variáveis para controlar fim e início)
• Lista linear com alocação dinâmica
– Também chamadas de Listas Encadeadas
– Posições de memória são alocadas a medida que são necessárias
– Nós encontram-se aleatoriamente dispostos na memória e são interligados por
ponteiros, que indicam a próxima posição da tabela
• Nós precisam de um campo a mais: campo que indica o endereço do
próximo nó.
Programação II
4
Listas Simplesmente Encadeadas
• Uma lista simplesmente encadeada é uma sequência
de objetos alocados dinamicamente, onde cada
objeto faz referência ao seu sucessor na lista
• Lista encadeada básica:
– possui variável head que referencia para o primeiro
elemento da lista
– cada Objeto refere a seu sucessor
– ultimo elemento contém a referência null (para indicar que
não referencia nenhum outro).
Ineficiente: se queremos inserir um elemento no final da lista, temos
que localizar o último elemento: para tanto é necessário
percorrer todos os elementos da lista.
Programação II
5
Lista Encadeada Básica
element next
head
Apontador para o
primeiro nó da lista
Node
...
null
final de lista
Programação II
6
Lista encadeada com referência ao último elemento da lista
• Como tornar mais eficiente:
– utilizar uma segunda variável, chamada tail, que referencia o
último elemento da lista.
– eficiência obtida a custa do espaço adicional
head
tail
Apontador para o
primeiro nó da lista
Apontador para o
último nó da lista
...
null
final de lista
Programação II
7
Classe Node
/** Nodo de uma lista simplesmente encadeada de strings **/
public class Node {
private String element; //assumimos que os elementos são strings
private Node next;
/** Cria um nodo com um dado elemento e o próximo nodo **/
public Node(String s, Node n){
element = s;
next = n;
}
/** Cria um nodo com um dado elemento e o próximo nodo em null**/
public Node( String element ) {
this( element, null );
element next
}
/** Retorna o elemento deste nodo **/
public String getElement(){ return element; }
/** Retorna o próximo elemento deste nodo **/
Node
public Node getNext(){ return next; }
/** Define o elemento deste nodo **/
public void setElement(String newElem){ element = newElem; }
/** Define o próximo elemento deste nodo **/
public void setNext(Node newNext){ next = newNext; }
}
Programação II
8
Operações sobre lista
– public boolean isEmpty()
• verifica se a lista está vazia
– public Node getFirst()
• Retorna o primeiro elemento da lista, sem removê-lo
– public Node getLast()
• Retorna o último elemento da lista, sem removê-lo
– public void addFirst( Node novoNodo )
• insere element na frente da lista
– public void addLast( Node novoNodo )
• insere element no final da lista
– public Node removeFirst()
• remove e retorna o primeiro elemento da lista
– public Node removeLast()
• remove e retorna o primeiro elemento da lista
– public void print()
• exibe o conteúdo da lista
Programação II
9
Class SLinkedList
/** Lista simplesmente encadeada **/
public class SLinkedList {
protected Node head; //nodo cabeça da lista
protected Node tail; //nodo cauda da lista
protected long size; //número de nodos da lista
/** Construtor default que cria uma lista vazia **/
public SLinkedList(){
head = null;
tail = null;
size = 0;
}
//demais métodos aqui
}
Programação II
10
isEmpty(), getFirst() e getLast()
public boolean isEmpty(){
return head == null;
}
public Node getFirst() throws UnderflowException {
if (isEmpty()) throw new UnderflowException();
return head;
}
public Node getLast() throws UnderflowException {
if (isEmpty()) throw new UnderflowException();
return tail;
}
Programação II
11
Inserção em lista simplesmente encadeada
- Na cabeça da lista:
tail
head
a
...
tail
head
b
...
tail
head
c
...
Programação II
12
Inserção em lista simplesmente encadeada
- Na cabeça da lista:
public void addFirst(Node novoNodo){
novoNodo.setNext(head);
head = novoNodo;
size++;
if(size == 1)
tail = head;
}
Programação II
13
Inserção em lista simplesmente encadeada
- Na cauda da lista:
tail
head
a
...
tail
head
b
...
head
c
tail
...
Programação II
14
Inserção em lista simplesmente encadeada
- Na cauda da lista:
public void addLast(Node novoNodo){
if(isEmpty())
addFirst(novoNodo);
else{
novoNodo.setNext(null);
tail.setNext(novoNodo);
tail = novoNodo;
size++;
}
}
Programação II
15
Remoção em lista simplesmente encadeada
- Da cabeça da lista:
tail
head
a
...
tail
head
b
...
tail
head
c
...
Programação II
16
Remoção em lista simplesmente encadeada
- Da cabeça da lista:
public Node removeFirst() throws UnderflowException {
if(isEmpty()) throw new UnderflowException();
Node removedItem = head;
if (head == tail) {
head = tail = null;
}
else {
head = head.getNext();
}
return removedItem;
}
Programação II
17
Remoção em lista simplesmente encadeada
- Da cauda da lista:
tail
head
a
...
current
current
current
current
head
b
tail
...
current
Programação II
18
Remoção em lista simplesmente encadeada
- Da cauda da lista:
public Node removeLast() throws UnderflowException {
if (isEmpty()) throw new UnderflowException();
Node removedItem = tail;
if (head == tail) {
head = tail = null;
}
else {
Node current = head;
while (current.getNext() != tail) {
current = current.getNext();
}
tail = current;
current.setNext(null);
}
return removedItem;
}
Programação II
19
Classe UnderflowException
public class UnderflowException extends Exception {
public String toString() {
return "UNDERFLOW!";
}
}
Programação II
20
Exercício
Como imprimir a lista simplesmente encadeada?
a) Crie um método print(), que percorre a lista e imprime os elementos.
Programação II
21
Exercício - Resposta
public void print() {
if (isEmpty()) {
System.out.println("Empty list");
}
else {
System.out.print("The list is: ");
Node current = head;
while (current != null) {
System.out.print(current.getElement().toString()+" ");
current = current.getNext();
}
Systemout.println("\n");
}
}
Programação II
22
Testando a Lista Simplesmente Encadeada
public static void main(String args[]){
Node n = new Node (“A”);
SLinkedList lista = new SLinkedList();
Lista.addFirst (n);
try{
lista.addFirst(new Node("A"));
lista.addFirst(new Node("B"));
lista.addFirst(new Node("C"));
lista.addLast(new Node("D"));
lista.addLast(new Node("E"));
lista.addLast(new Node("F"));
lista.removeFirst();
lista.removeLast();
}catch(UnderflowException e){
System.out.println("ERRO: impossível remover!");
e.printStackTrace();
}
lista.print();
}
Programação II
23
Exercício
Como inserir um elemento no meio de uma lista simplesmente encadeada?
a) Crie um método chamado addAfter(Node n, int pos), que insere o nodo
n depois do nodo de número pos (considerando que o primeiro nodo é o
nodo na posição 0).
b) Crie um método chamado addBefore(Node n, int pos), que insere o
nodo n antes do nodo de número pos (considerando que o primeiro nodo
é o nodo na posição 0).
Programação II
24
Exercício
Como fazer a lista ficar genérica?
a) Transforme a classe Node (que utiliza String) para um tipo genérico E
b) Transforme a classe SLinkedList para um tipo genérico E (o mesmo do Node)
- Programação II
25
Classe Node com String
/** Nodo de uma lista simplesmente encadeada de strings **/
public class Node {
private String element; //assumimos que os elementos são strings
private Node next;
/** Cria um nodo com um dado elemento e o próximo nodo **/
public Node(String s, Node n){
element = s;
next = n;
}
/** Cria um nodo com um dado elemento e o próximo nodo em null**/
public Node( String element ) {
this( element, null );
}
/** Retorna o elemento deste nodo **/
public String getElement(){ return element; }
/** Retorna o próximo elemento deste nodo **/
public Node getNext(){ return next; }
/** Define o elemento deste nodo **/
public void setElement(String newElem){ element = newElem; }
/** Define o próximo elemento deste nodo **/
public void setNext(Node newNext){ next = newNext; }
}
Programação II
26
Classe Node Genérica
/** Nodo de uma lista simplesmente encadeada de strings **/
public class Node<E>{
private E element;
private Node<E> next;
/** Cria um nodo com um dado elemento e o próximo nodo **/
public Node(E s, Node<E> n){
element = s;
next = n;
}
/** Cria um nodo com um dado elemento e o próximo nodo em null**/
public Node( E element ) {
this( element, null );
}
/** Retorna o elemento deste nodo **/
public E getElement(){ return element; }
/** Retorna o próximo elemento deste nodo **/
public Node<E> getNext(){ return next; }
/** Define o elemento deste nodo **/
public void setElement(E newElem){ element = newElem; }
/** Define o próximo elemento deste nodo **/
public void setNext(Node<E> newNext){ next = newNext; }
}
Programação II
27
Classe SLinkedList Genérica
/** Lista simplesmente encadeada **/
public class SLinkedList<E> {
protected Node<E> head; //nodo cabeça da lista
protected Node<E> tail; //nodo cauda da lista
protected long size; //número de nodos da lista
/** Construtor default que cria uma lista vazia **/
public SLinkedList(){
head = null;
tail = null;
size = 0;
}
//demais métodos aqui
//todas as ocorrências do tipo Node devem ser
alteradas para Node<E>
}
Programação II
28
Testando a Lista Simplesmente Encadeada Genérica
public static void main(String args[]){
SLinkedList<String> lista = new SLinkedList<String>();
try{
lista.addFirst(new Node<String>("A"));
lista.addFirst(new Node<String>("B"));
lista.addFirst(new Node<String>("C"));
lista.addLast(new Node<String>("D"));
lista.addLast(new Node<String>("E"));
lista.addLast(new Node<String>("F"));
//lista.addLast(new Node<Integer>(1));
lista.removeFirst();
lista.removeLast();
lista.addAfter(new Node<String>("0"),3);
lista.addBefore(new Node<String>("1"),4);
lista.addBefore(new Node<String>("3"), 8);
}catch(IndexOutOfBoundsException e){
System.out.println("ERRO: índice iválido!");
e.printStackTrace();
}catch(UnderflowException e){
System.out.println("ERRO: lista vazia, impossível remover!");
e.printStackTrace();
}
lista.print();
}
Prof. Mateus Raeder - Programação II
29