Baixe o app para aproveitar ainda mais
Prévia do material em texto
1 Lista Ligada 1 Prof. Cláudio Campelo, PhD Departamento de Sistemas & Computação / UFCG Estrutura de Dados e Algoritmos Lista Ligada (Linked List) 2 � É uma estrutura de dados em que objetos são arranjados em ordem linear. � Ordem estabelecida por ligação (links) entre elementos da lista. � Cada nó da lista armazena um elemento e uma referência para o próximo nó da lista. 5 6 8 null 2 Lista Ligada (Linked List) 3 � Características � Um dos tipos abstratos de dados fundamentais � Sequência de tamanho arbitrário e dinâmico de elementos de algum tipo base � Utiliza o espaço necessário (alocação dinâmica) � A ordem é determinada por um ponteiro e não pelo índice como no array � Acesso sequencial Lista 4 � Operações � Inserir � Remover � Pesquisar � Tamanho � Vazio 3 Questões de Implementação 5 � Implementação estática – implementada com arrays � Implementação dinâmica – através de duas abordagens: � Estrutura recursiva com métodos iterativos � Cada elemento (nó) da lista contém um dado armazenado e um apontador para o próximo elemento da lista � Estrutura recursiva com métodos recursivos � Cada elemento (nó) da lista contém um dado armazenado e um apontador para o próximo elemento da lista next data Questões de Implementação 6 � Implementação estática – implementada com arrays � Implementação dinâmica – através de duas abordagens: � Estrutura recursiva com métodos iterativos � Cada elemento (nó) da lista contém um dado armazenado e um apontador para o próximo elemento da lista � Estrutura recursiva com métodos recursivos � Cada elemento (nó) da lista contém um dado armazenado e um apontador para o próximo elemento da lista next data 4 Questões de Implementação 7 � Lista vazia � Representada por um nó especial (NIL) sem dado � Pode também ser representado por NULL (não recomendado) � Nós sentinela � Representam a lista vazia e são acrescentados nas extremidades das listas � Simplificam e aceleram alguns algoritmos sobre lista e dão garantia de que uma lista sempre contém algum nó (mesmo que seja vazio) null null Nó sentilena NIL Implementação 8 � Exemplo: lista de inteiros não negativos null -1 5 2 Lista vazia=NIL (caso base) Lista não vazia (caso indutivo) Como implementar em Java? null -1 headhead 5 Lista (Implementação) 9 public interface LinkedList<T> { public boolean isEmpty(); public int size(); public T search(T element); public void insert(T element); public void remove(T element); public T[] toArray(); } Lista (Implementação) 10 public class SingleLinkedListNode<T> { protected T data; protected SingleLinkedListNode<T> next; public SingleLinkedListNode () { } public SingleLinkedListNode (T data, Node<T> next) { this.data = data; this.next = next; } public boolean isNIL(){ return (this.data == null); } } next data NIL next data 6 Lista (Implementação) 11 public class SingleLinkedListImpl<T> implements LinkedList<T>{ protected SingleLinkedListListNode<T> head; public SingleLinkedListImpl() { head = new SingleLinkedListNode<T>(); } ... } head NIL Lista (isEmpty) 12 � Apenas a lista vazia deve retornar true. isEmpty(){ if head == NIL return true else return false } 7 Lista (Inserir) 13 � Listas não ordenadas � Inserções no início ou no fim � Listas ordenadas � Inserções na posição correta (preservar ordem) inserir(6) 6 NIL head 6 6 NIL NIL NIL head inicio fim ordenado Lista (Inserir) 14 � Listas não ordenadas � Inserções no início ou no fim � Listas ordenadas � Inserções na posição correta (preservar ordem) inserir(3) 6 head head 3 6 NIL NIL NIL inicio fim ordenado 6 NIL 3 6 3 8 Lista (Inserir) 15 � Listas não ordenadas � Inserções no início ou no fim � Listas ordenadas � Inserções na posição correta (preservar ordem) inserir(5) head head inicio fim ordenado 6 NIL3 6 NIL35 5 NIL63 6 NIL53 Lista (Inserir) 16 � Adotar listas não ordenadas e inserção no final list-insert(item){ auxHead = head if(head = NIL){ newHead = new SingleLinkedListNode(item) newHead.next = head head = newHead } else { while(auxHead.next != NIL){ auxHead = auxHead.next } newNode = new SingleLinkedListNode(item) newNode.next = auxHead.next auxHead.next = newNode } } Qual o tempo de execução? 9 Lista (Procurar) 17 � A procura é sequencial e se dá pelo valor armazenado procurar 5 6 8 5 null 6 8 5 6 8 5 NIL NIL NIL NIL head Lista (Procurar) 18 Qual o tempo de execução? 10 Lista (Remover) 19 � As remoções se dão pelo valor armazenado remover 8 6 8 5 6 5 Como seria a remoção na lista? 6 8 5 NIL NIL NIL head 8 previous aux Lista (Remover) 20 � As remoções se dão pelo valor armazenado list-remove(item) { if (head.data == item) { head = head.next } else { aux = head while (aux != NIL AND aux.data != item) { previous = aux aux = aux.next } if (aux != NIL) { previous.next = aux.next } } } Qual o tempo de execução? 11 Lista (Tamanho) 21 � Como calcular o tamanho de uma lista? tamanho 6 8 5 0 6 8 5tamanho 6 8 5 NIL NIL NIL NIL 3 Como seria o algoritmo do tamanho? Lista (Tamanho) 22 list-size() { size = 0 aux = head while aux != NIL { size = size + 1 aux = aux.next } return size } � Como calcular o tamanho de uma lista? 12 list-size() { size = 0 aux = head while aux != NIL { size = size + 1 aux = aux.next } return size } Lista (Tamanho) 23 Qual o tempo de execução? � Como calcular o tamanho de uma lista? Lista (toArray) 24 � Deve retornar um array contendo os elementos da lista na ordem do head para o final. T[] list-toArray(){ T[] result = new T[] aux = head int count = 0 while aux != NIL { result[count] = aux.data aux = aux.next count++ } return result } 13 Exercício 25 � Implemente um método que encontre o maior elemento de uma lista ligada. � Implemente um método que encontre o menor elemento de uma lista ligada. Lista Duplamente Ligada 26 14 Lista Duplamente Ligada 27 � Cada nó tem referências para os nós sucessor e predecessor � Listas duplamente encadeadas têm a vantagem de poderem ser percorridas em ambas as direções � Isto permite reduzir para a metade o tempo máximo para acessar um elemento com base no seu índice � Head e last ficam acessíveis na lista dupla -1 nullnull -1 ...null -1 null... Lista (Implementação) 28 � Como seria a implementação de uma lista duplamente ligada? � A estrutura do nó muda? � A estrutura da lista em si muda? next data next data previous 15 Lista (Implementação) 29 � Como seria a implementação de uma lista duplamente ligada? public class DoubleLinkedListNode<T> extends SingleLinkedListNode<T> { protected DoubleLinkedListNode<T> previous; public DoubleLinkedListNode() { } public DoubleLinkedListNode(T data, DoubleLinkedListNode<T> next, DoubleLinkedListNode<T> previous) { super(data, next); this.previous = previous; } } NIL next data previous Lista (Implementação) 30 � Como seria a implementação de uma lista duplamente ligada? public interface DoubleLinkedList<T> { public boolean isEmpty(); public int size(); public T search(T element); public void insert(T element); public void remove(T element); public T[] toArray(); public void insertFirst(T element); public void removeFirst(); public void removeLast(); } 16 Lista(Implementação) 31 � Como seria a implementação de uma lista duplamente ligada? public interface DoubleLinkedList<T> { public boolean isEmpty(); public int size(); public T search(T element); public void insert(T element); public void remove(T element); public T[] toArray(); public void insertFirst(T element); public void removeFirst(); public void removeLast(); } Esses métodos já existem em algum lugar? Lista (Implementação) 32 � Como seria a implementação de uma lista duplamente ligada? public interface DoubleLinkedList<T> extends LinkedList<T> { public void insertFirst(T element); public void removeFirst(); public void removeLast(); } 17 public class DoubleLinkedListImpl<T> extends SingleLinkedListImpl<T> implements DoubleLinkedList<T> { DoubleLinkedListNode<T> last; public DoubleLinkedListImpl() { head = new DoubleLinkedListNode(); last = head; } } Lista (Implementação) 33 last NIL head Algum método herdado precisa ser sobrescrito? public class DoubleLinkedListImpl<T> extends SingleLinkedListImpl<T> implements DoubleLinkedList<T> { DoubleLinkedListNode<T> last; public DoubleLinkedListImpl() { head = new DoubleLinkedListNode(); last = head; } } Lista (Implementação) 34 last head Algum método herdado precisa ser sobrescrito? search (por otimização),insert,remove NIL 18 Lista Dupla(Search) 35 � Pelos dois sentidos: head e last search(6) 6NIL head NIL head last NIL search(x) 6 NILNIL 10 head last last //busca (com otimização) List-search(item){ auxHead = head auxLast = last while(auxHead != auxLast and auxHead.next != auxLast auxHead.data != item and auxLast.data != item){ auxHead = auxHead.next auxLast = auxLast.previous } if auxHead.data == item return auxHead.data if auxLast.data == item return auxLast.data } Lista Dupla (Implementação) 36 19 Lista Dupla (Inserir no final = default) 37 inserir(6) 6NIL head NIL head NIL inserir(10) 10 NILNIL 6 head last last last Lista Dupla (Inserir no final = default) 38 //insere no final e ajusta os links next e previous List-insert-last(item){ newLast = new DoubleLinkedListNode(item) newLast.previous = last newLast.next = NIL last.next = newLast if (last == NIL) { //para o caso da lista vazia head = newLast } last = newLast } 20 Lista Dupla (Inserir no início) 39 inserir(6) 6NIL head NIL head last NIL inserir(10) 6 NILNIL 10 head last last //insere no começo e ajusta os links next e previous List-insert-first(item){ newHead = new DoubleLinkedListNode(item) newHead.next = head newHead.previous = NIL head.previous = newHead if (head == NIL) { //para o caso da lista vazia last = newHead } head = newHead } List-insert(item){ List-insert-first(item) } Lista Dupla (Inserir no início) 40 21 Lista Dupla (remover no início) 41 remove-first() NIL head 6 NIL head NIL 10 NILNIL 6 head remove-first() 10 NIL head NIL last last last last Lista Dupla (remover no início) 42 //remover do inicio List-remove-first(){ if (head != NIL) { head = head.next if (head == NIL) { last = head } head.previous = NIL } } 22 Lista Dupla (remover no final) 43 remove-last() NIL head last 6 NIL head NIL last 10 NILNIL last 6 head remove-last() 6 NIL head NIL last Lista Dupla (Remover no final) 44 //remover do final List-remove-last(){ if last != NIL { last = last.previous if last == NIL{ head = last } last.next = NIL } } 23 Lista Dupla (Remover pela chave = default) 45 remover(6) NIL head last 6 NIL head NIL last 10 NILNIL last 6 head remover(6) 10 NIL head NIL last Lista Dupla (Remover pela chave = default) 46 list-remove(item){ if (head.data == item) { remove-first() } else { aux = head while (aux != NIL) AND (aux.data != item) { aux = aux.next } if (aux != NIL) { aux.previous.next = aux.next aux.next.previous = aux.previous } } 24 Referências 47 � Capítulo 11
Compartilhar