Veröffentlicht 23. März 200520 j hallo, leuchtet jemanden die nachfolgende doppelt verlinkte zirkulaere liste ein? waere es moeglich, wenn jemand den code mal kommentiert? oder mir anhand des codes erklaeren, was passiert? thanks in advance. -------------------------------------- public class List { private Entry header; private int size; // Constructor for an empty list that only contains a dummy header element public List() { header = new Entry(null,null,null); } public void addFirst( Object o ) { //to do:call the private method addBefore if (size==0){ Entry newEntry = new Entry(o,null,null); header.next = newEntry; header.previous = newEntry; newEntry.previous = newEntry; newEntry.next = newEntry; size++; } else{addBefore(o,header.next);} } public Object getFirst() { //to do return null; } public Object removeFirst() { //to do return null; } public int size() { return size; } public boolean isEmpty(){ /*boolean empty; if(size>=1) empty=true; else empty=false; return empty;*/ return size==0; } public void clear() { //to do } // Return an iterator for the list public MyListIterator iterator() { return new MyListIterator(); } // private methods private Entry addBefore( Object o, Entry e ) { //to do Entry newEntry = new Entry(o,e,e.previous); e.previous = newEntry; header.next=newEntry; size++; return null; } private void remove( Entry e ) { } // Inner class MyListIterator private class MyListIterator implements MyIterator { private Entry tempHeader = header; public boolean hasNext() { if((header.next != null) && (tempHeader != header.previous)){ return true; } else return false; } public Object next() { tempHeader = tempHeader.next;//flaw //tempHeader=header.next; return tempHeader.element; } public boolean hasPrevious() { if((header.previous != null) && (tempHeader != header.next)){ return true; } else return false; } public Object previous() { tempHeader = tempHeader.previous; return tempHeader.element; } } // End of inner class MyListIterator // Inner class Entry private class Entry { Object element;//actual data Entry next; Entry previous; Entry( Object element, Entry next, Entry previous ) { this.element = element; this.next = next; this.previous = previous; } } // End of inner class Entry } // End of class List
23. März 200520 j Eine doppelt verkettete verlinkte Liste heisst einfach, dass jedes Element der Liste eine Referenz auf seinen Vorgänger und seinen Nachfolger hat. Bei einer nicht-zirkulaeren List, hat dabei das erste Element keine Referenz auf seinen Vorgänger, das letzte Element hat keine Referenz auf seinen Nachfolger, also in etwa so: null <-- Prev -- /------\ <-- Prev -- /------\ <-- Prev -- /------\ | Node | | Node | | Node | \------/ -- Next --> \------/ -- Next --> \------/ -- Next --> null Einer zirkulaeren Liste fehlen diese null-Referenzen am Anfang und am Ende der Liste - hier das letzte Element der Vorgänger des ersten Elementes und das erste Element der Nachfolger des letzten. Eine zusätzliche Referenz auf das erste Element dient dabei dazu, das 1. Element innerhalb dieses "Kreises" von Nodes zu identifizieren. Vom Prinzip her musst du dir die interne Verteilung der Nodes so vorstellen: /------\ <-- Prev -- /------\ <-- Prev -- /------\ | Node | | Node | | Node | \------/ -- Next --> \------/ -- Next --> \------/ | ^ | ^ | \----------------- Next ------------------/ | | | \--------------------- Prev ---------------------/
23. März 200520 j Besser Erklären geht wohl garned *Respekt* Nur mal so als Bestätigung *der verzählt keinen **** da*
23. März 200520 j vielen dank. passt der quelltext oben denn? d.h. ist das eine korrekt implementierte zirkulaere doppelt verlinkte list?
23. März 200520 j passt der quelltext oben denn? d.h. ist das eine korrekt implementierte zirkulaere doppelt verlinkte list?Nein! Viele Methoden sind überhaupt nicht implementiert (remove und clear z.B.). Die add Methode ändern ausserdem immer das erste Element, was natürlich kein korrektes Verhalten ist, wenn ich an Position 2, 3, ... ein Element einfügen will.
24. März 200520 j ja *******e ... und nu? Konzept der doppelt verketteten zirkulären Liste aneignen und in einer Klasse umsetzen.
24. März 200520 j ja *******e ... und nu?Ganz einfach: implementieren! Ich hab dir das Konzept oben erklärt, jetzt musst du schon ein bisschen was selber tun.
Archiv
Dieses Thema wurde archiviert und kann nicht mehr beantwortet werden.