Hej!
Ślęczę nad jednym z ćwiczeń na uczelnię, gdzie mam sobie zaimplementować listę jednokierunkową (samodzielnie - bez kolekcji) oraz Iterator do niej. Coś jak ListIterator z biblioteki. Listę napisałem, wrzuciłem do projektu interfejs Iterator z metodami next, first, last, isDone i current, ale niestety mimo długiego siedzenia nie wiem, jak te metody zaimplementować w przypadku takiej listy. Google niestety jakoś nie pomaga. Macie może gdzieś na dysku, czy na jakiejś stronce przykład tego, jak zdefiniowane są metody dla takiej listy w przypadku ListIterator z biblioteki? Na podstawie tego mógłbym wywnioskować sposób działania, a tak trochę stoję :/
0
0
Iterator posiada stan ktory wskazuje jego aktualna pozycje w liscie. Zalezy jak liste zaimplementowales, ten stan to np. obecny indeks (jesli uzywasz tablicy) lub referenja na obecny wezel w liscie wiazanej. Metody isDone() itp. sa latwe: sprawdzasz czy indeks jest == size - 1, lub czy currentNode.next == null (czy jakkolwiek zaimplementowales taka liste).
Metody first() i last() sa srednio szczesliwe, ani Iterator ani ListIterator takowych nie ma - jest to do zrobienia, ale one wymagaja zapisywania dodatkowego stanu a nie wiem czy jest sens sie z tym babrac jak pewnie nie jest wymagane?
Metoda current() jest banalna, metoda next() rowniez.
Jeden hak - co sie stanie jak stworzysz iterator ktory trzyma liste z momentu utworzenia, i w trakcie iteracji ta lista sie zmieni? Standatdowe javowe iteratory sa fail-fast, tzw. rzucaja wyjatkami w takim przypadku - ConcurrentModificationException. Najlatwiej zrobic to tak, ze w liscie utrzymujesz liczbe long ktora trzyma liczbe modyfikcji listy - wszystkie operacje zmieniajace liste w jakis sposob zwiekszaja licznik o 1 (czyli np. metoda add() na koncu robi ++modificationCount, to samo metoda remove() i addAll()). Iterator rowniez ma to pole, ktore jest final (nie modyfikowalne) i jest podawane jako argument konstruktora w momencie gdy iterator dla listy jest tworzony. Kazda metoda iteratora najsampierw sprawdza czy jego modificationCount == modyficationCount listy, i jesli nie, rzuca ConcurrentModificationException (choc mozesz nazwac ten typ inaczej, Concurrent w nazwie myli wiele osob i zaczynaja szukac bledu w watkach nawet w jednowatkowych programach ;d); jesli sa rowne, wszystko jest ok i wykonujesz normalny kod.
Iterator jak widac wymaga dostepny do pol prywatnych listy (choc to zalezy jak wszystko zaimplementujesz, ale np. modyficationCount czy wskaznik na linka w liscie laczonej to elementy implementacji i nie powinny byc widoczne na zewnatrz. Najlatwiej zrobic to tak, ze implementacja interfejsu Iterator jest klasa zagniezdzona w klasie List (ale nie statyczna, poniewaz wymaga dostepu do pol niestatycznych) - takie klasy maja dostep do wszyskich pol klasy 'zewnetrznej', nawet prywatnych.
Standardowe kolekcje Javy dzialaja wlasnie w taki sposob. Teraz masz juz wystarczajaco duzo informacji zeby moc samemu zaimplementowac iteratora i nie czekac na gotowce.
0
No dobra. Nawet ciut, ciut mi rozjaśniłeś sytuację (zwłaszcza tym dodaniem iteratora do klasy Lista jako prywatną klasę). Dziękuję Tylko problem teraz...niby coś tam zaimplementowałem, ale jak użyć tego w programie? Nie mogę w mainie stworzyć iteratora, bo to klasa prywatna...może choć tyle powiesz z bardziej z bardziej konkretnych rzeczy? Mam coś takiego:
Lista + klasa Elementu + Iterator
public class Lista implements List {
private Element head = new Element(null); //wartownik
private int size;
public Lista(){
clear();
}
public void clear(){
head.setNext(null);
size=0;
}
public void add(Object value){
if (head.getNext()==null) head.setNext(new Element(value)); //JEŚLI LISTA JEST PUSTA USTAWIAMY NASTĘPNIK WARTOWNIKA
else {
Element last = head.getNext();
//wyszukiwanie ostatniego elementu
while(last.getNext() != null)
last=last.getNext();
// i ustawianie jego referencji next na nowowstawiany Element
last.setNext(new Element(value));}
++size;
}
public Object get(int index) throws IndexOutOfBoundsException{
if(index<0 || index>size) throw new IndexOutOfBoundsException();
Element particular = head.getNext();
for(int i=0; i <= index; i++)
particular = particular.getNext();
return particular.getValue();
}
public boolean delete(Object o){
if(head.getNext() == null) return false;
if(head.getNext().getValue().equals(o)){
head.setNext(head.getNext().getNext());
size--;
return true;
}
Element delete = head.getNext();
while(delete != null && delete.getNext() != null){
if(delete.getNext().getValue().equals(o)){
delete.setNext(delete.getNext().getNext());
size--;
return true;
}
delete = delete.getNext();
}
return false;
}
public int size(){
return size;
}
/**
* Metoda, która sprawdza, czy lista jest pusta
* @return true, gdy rozmiar listy wynosi 0, w innym wypadku false
*/
public boolean isEmpty(){
return size == 0;
}
public void wyswietlListe() {
}
private static final class Element{
private Object value;
private Element next; //Referencja do kolejnego obiektu
public Element(Object value){
setValue(value);
}
public void setValue(Object value) {
this.value = value;
}
public Object getValue() {
return value;
}
//ustawia referencję this.next na obiekt next podany w atgumencie
public void setNext(Element next) {
if (next != null)
this.next = next;
}
public void addBeforeNext(Element next) {
if (next != null) {
setNext(next);
}
}
/**
* @return kolejny element
*/
public Element getNext(){
return next;
}
/**
* @param n kolejny element
*/
}
private class IteratorListowy implements Iterator{
private final Lista lista;
Element current;
public IteratorListowy(Lista lista) {
this.lista = lista;
current = head.getNext();
}
public void next() {
current = current.next;
}
public boolean isDone() {
return current.next == null;
}
public Object current() {
return current;
}
}
}
oraz jakiś tam testowy main():
public class Program {
public static void main(String[] args) {
Lista lista = new Lista();
Student s1 = new Student("Kowalski", 3523);
Student s2 = new Student("Polański", 45612);
Student s3 = new Student("Karzeł", 8795);
Student s4 = new Student("Pałka", 3218);
Student s5 = new Student("Konowałek", 8432);
Student s6 = new Student("Kłopotek", 6743);
Student s7 = new Student("Ciołek", 14124);
lista.add(s1);
lista.add(s2);
lista.add(s3);
lista.add(s4);
lista.add(s5);
}
}
No i chciałbym sobie w tym mainie iterator stworzyć, ale nie wiem jak. Podobnie mam problem z zrobieniem metody WyswietlListe() w samej liście, bo potrzebowałbym tam stworzyć iterator, a jako, że mój w argumentach przyjmuje listę, to wewnątrz klasy tego nie zrobie, bo nie mam ani jednego obiektu klasy lista :/
1
Klasa IteratorListory nie powinna byc publiczna, zrob ja private. Jako ze nie jest statyczna, ma dostep do instancji klasy zewnetrznej, czyli nie potrzebuje dodatkowo pola lista - moze po prostu wywolywac metody / czytac i pisac do pol jakby to byly jej pola - wywal zatem to pole i parametr konstruktora. Do klasy Lista dodaj metode iterator() ktora robi po prostu new IteratorListowy().
Metoda wyswietlListe() po prosty wywoluje metode iterator() (lub tworzy sobie new IteratorListory() bo ma dostep do tej klasy, ale lepiej imho wolac ta metode) i dalej juz pewnie wiesz co robic.
0
Dziękuję bardzo za wskazówki. Wszystko zdaje się działać jak należy. Musiałem trochę zmienić definicję metody isDone(), żeby mi się zgrywała z pętlą w metodzie wyswietlListe(), ale już wydaje się być ok i program wyrzuca mi tyle linijek z literką "a", ile powinien.
public void wyswietlListe() {
IteratorListowy iterator = iterator();
for (iterator.first(); !iterator.isDone(); iterator.next())
{
System.out.println("a");
}
}
private class IteratorListowy implements Iterator{
private Element current;
public IteratorListowy() {
current = head;
}
public void next() {
current = current.next;
}
public boolean isDone() {
return current == null;
}
public Object current() {
return current;
}
public void first() {
current = head.getNext();
}
}
0
Wydaje mi sie ze masz bledy. Po pierwsze, dlaczego wypusujesz "a" a nie elementy listy? Prowadzacy pewnie nie bedzie zachwycony. Metoda next() powinna sprawdzac czy jest nastepny element, i jesli nie to rzucac wyjatek. W tej chwili jesli bedziesz wolal ciagle iter.next(); iter.next() itp. to dostaniesz w koncu NullPointerException, ktory niemal zawsze jest nieladnym bledem programisty. Nie zaimplementowales tego co opisalem jako fail-fast iteratorow, ale moze to za duzo.
Ogolnie, wydaje mi sie ze twoj iterator dziala tylko jesli sie go poprawnie uzywa, a proba niepoprawnego uzycia (co czesto sie w kodzie zdarza) doprowadzi do roznych nieciekawych wyjatkow i totalnego skolowania. Powinienes sie postarac o lepsza obsluge bledow. A przynajmniej tak robia kolekcje Javowe.
0
Tak, tak. Z tym "a" to tylko sprawdzałem, czy mi poprawną ilość elementów wyrzuca. wyłapywaniem błędów się zajmę i chyba nie powinno byc problemów. Ostatnia rzecz, jaka mnie nurtuje:
Zmieniłem sobie trochę metodę wyswietlListe() i wyświetla, ale jako coś w stylu:
lista2z1.Lista$Element@b583a80
lista2z1.Lista$Element@4d68af51
lista2z1.Lista$Element@13ce168b
lista2z1.Lista$Element@3f2a09d5
lista2z1.Lista$Element@60eb9f58
a chciałbym, żeby mi używało toString() z klasy Student. Myslałem, że program sam się domyśli, że ten "Object" to konkretniej klasa student. no ale nie :/
public void wyswietlListe() {
IteratorListowy iterator = iterator();
for (iterator.first(); !iterator.isDone(); iterator.next())
{
System.out.println(iterator.current());
}
}
1
Musisz z iterator.current() zwracac current.value a nie current. W tej chwili wolasz toString klasy Element.
0
no proszę, faktycznie. Dziękuję Ci bardzo za pomoc
0
cholera...jeszcze jeden problem mi wyskoczył. Zrobiłem program testujący i prawie nie wyłapałbym błędu. Chodzi o jakiś problem z usuwaniem elementów. Niby wszystko działa i rozmiar listy się zmniejsza, coraz mniej elementu wyswietlListe() mi pokazuje itd. Z jednym wyjątkiem - nie mogę usunąć s5. Niby jak wywołam metodę delete() dla wszystkim elementów po kolei (s1, s2, s3, s4, s5) to końcowe sprawdzenie isEmpty() wyrzuci mi komunikat, że lista jest pusta...ale wyswietlListe() wyrzuci mi s5. Jak wyrzucę samo s5, to też dostanę komunikat, że już niby tylko 4 elementy w liście, ale wyświetli się 5. Z innymi elementami nie mam takiego problemu. Co to znaczy?
public class Program {
public static void main(String[] args) {
Lista lista = new Lista();
Iterator iterator = lista.iterator();
Student s1 = new Student("Kowalski", 3523);
Student s2 = new Student("Polański", 45612);
Student s3 = new Student("Karzeł", 8795);
Student s4 = new Student("Pałka", 3218);
Student s5 = new Student("Konowałek", 8432);
Student s6 = new Student("Kłopotek", 6743);
Student s7 = new Student("Ciołek", 14124);
lista.add(s1);
lista.add(s2);
lista.add(s3);
lista.add(s4);
lista.add(s5);
lista.wyswietlListe();
lista.delete(s3);
lista.wyswietlListe();
lista.delete(s2);
lista.delete(s5);
lista.wyswietlListe();
if (lista.isEmpty()) {
System.out.println("Lista pusta.");
}
else
{
System.out.println("Lista zawiera " + lista.size() + " elementow.");
}
lista.clear();
if (lista.isEmpty()) {
System.out.println("Lista pusta.");
}
else
{
System.out.println("Lista zawiera " + lista.size() + " elementow.");
}
}
}
0
To pewnie znaczy ze masz jakis blad w logice usuwania elementow.
0
Nie wiem czy jeszce sie z tym meczysz, ale jakos ze napisales tak duzo prawie dzialajacego kodu, i ze mialem troche czasu to naskrobalem cos takiego:
package blah.main;
import java.util.NoSuchElementException;
interface Iterator {
Object next();
boolean isDone();
}
class Lista {
private Element head;
private Element tail;
private int size;
public void clear() {
head = null;
tail = null;
size = 0;
}
public void add(Object value) {
if (value == null) {
throw new IllegalArgumentException("nulls not supported");
}
if (head == null) {
head = new Element(value);
tail = head;
} else {
tail.next = new Element(value);
tail = tail.next;
}
++size;
}
public boolean delete(Object value) {
if (head == null) {
return false;
}
if (head.value.equals(value)) {
head = head.next;
--size;
return true;
}
Element tmp = head;
while (tmp.next != null && !tmp.next.value.equals(value)) {
tmp = tmp.next;
}
if (tmp.next == null) {
return false;
}
tmp.next = tmp.next.next;
--size;
return true;
}
public Object get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
Element current = head;
for (int i = 0; i < index; ++i) {
current = current.next;
}
return current.value;
}
public int size() {
return size;
}
public boolean isEmpty() {
assert size == 0;
return head == null;
}
public Iterator iterator() {
return new IteratorListowy();
}
public void printList() {
System.out.printf("#%d [", size);
Iterator iterator = iterator();
while (!iterator.isDone()) {
System.out.print(iterator.next());
if (!iterator.isDone()) {
System.out.print(", ");
}
}
System.out.println("]");
}
private static class Element {
private Object value;
private Element next;
public Element(Object value) {
this.value = value;
}
}
private class IteratorListowy implements Iterator {
private Element current;
public IteratorListowy() {
current = head;
}
public boolean isDone() {
return current == null;
}
public Object next() {
if (isDone()) {
throw new NoSuchElementException();
}
Object value = current.value;
current = current.next;
return value;
}
}
}
public class Main {
public static void main(String[] args) {
Lista lista = new Lista();
lista.delete("1");
String s1 = "1";
String s2 = "2";
String s3 = "3";
String s4 = "4";
String s5 = "5";
lista.add(s1);
lista.add(s2);
lista.add(s3);
lista.add(s4);
lista.add(s5);
lista.printList();
lista.delete(s1);
lista.printList();
lista.delete(s4);
lista.printList();
lista.delete(s3);
lista.printList();
lista.delete(s5);
lista.printList();
lista.delete(s2);
lista.printList();
}
}
Nie wiem czy dziala tak jak chcesz dla wszystkich use casow, i czy nie ma bledow, ale jakos dziala.