Listas encadeadas

SIMONGAME

Mecanismo: sequência aleatória de cores (e notas musicais) deve ser memorizada e repetida pelo usuário

TAD Lista Simplesmente Encadeada (LSE) head ∅

A

B

C

D

Classe Nó nó prox

elem

em Java public class No { private E item; private No prox; public No(E item) { this.item = item; prox = null; } public No(E item, No prox) { this.item = item; this.prox = prox; } public E getItem() { return item; } public No getProx() { return prox; } public void setItem(E item) { this.item = item; } public void setProx(No prox) { this.prox = prox;
}
}

Nós Ligados
No no1 = new No("Fulano");
No no2 = new No("Beltrano");
No no3 = new No("Cicrano"); no1.setProx(no2); no2.setNext(no3); new No
("Fulano", new No
("Beltrano", new No("Cicrano")))

Tipo Abstrato Lista public interface Lista { public void insere(int pos, E item); public void insere(E item); public E remove(int pos); public boolean remove(E item); public E busca(int pos); public boolean busca(E item); public void modifica(int pos, E item); public int tamanho(); public boolean vazia(); }

classe LSE public class LSE implements Lista { private No inicio; public LSE() { inicio = null;
}
public boolean vazia() { return inicio == null;
}
public int tamanho () { int tamanho = 0; for (No no = inicio; no != null; no = no.getProx()) tamanho++; return tamanho;
}
}

LSE: Inserção public void insere(E item) { if (vazia()) { inicio = new No(item)
} else {
No no = new No(item); no.setProx(inicio); inicio = no;
}
}

inicio

no
8

A

B

LSE: Inserção numa posição inicio temp

temp

no

∅
B

9

C

D
G
public void insere(int pos, E item) { if (vazia()) { inicio = new No(item)
} else {
No temp = inicio; for (int i = 1; i < pos-1; i++) temp = temp.getProx();
No no = new No(item); no.setProx(temp.getProx()); temp.setProx(no);
}
}

LSE: Remoção
! (1) entrada: valor do elemento a remover
!