zirkulaere doppelt verlinkte liste erklaeren?

[lesezeichen]

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

	

[perdian]

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  ---------------------/          

[HuDeanY]

Besser Erklären geht wohl garned *Respekt*

Nur mal so als Bestätigung

*der verzählt keinen **** da*

[lesezeichen]

vielen dank.

passt der quelltext oben denn? d.h. ist das eine korrekt implementierte zirkulaere doppelt verlinkte list?

[perdian]

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.

[lesezeichen]

ja *******e ... und nu?

[geloescht_Newlukai]

ja *******e ... und nu?

Konzept der doppelt verketteten zirkulären Liste aneignen und in einer Klasse umsetzen.

[perdian]

ja *******e ... und nu?

Ganz einfach: implementieren!

Ich hab dir das Konzept oben erklärt, jetzt musst du schon ein bisschen was selber tun.