doppelt verkettete liste einfügen

[newbie2009]

hey leute habe ein problem mit der doppelt verketteten liste:

void addBehind(Object key){
		// erst 
		Datensatz vorletztes = ende.getVorgänger();
		Datensatz neu = new Datensatz(vorletztes,ende,key);
		vorletztes.setNachfolger(neu);
		ende.setVorgänger(neu);
		
	}

zum konstrkutor, erstes element gibt den vorgänger, zweites element den nachfolger, drittes den wert.
Was mich wundert ist, dass die methode funktioniert
wenn ich also die werte 11,13,15,17 einfüge befinden sie sich auch in dieser reihnefolge in der liste.

wenn ich mir die methode aber anschaue , sieht es für mich aus, als müsste der neue werte immer zwischen die zwei letzten eingefügt werden, ungefähr so :

liste:11,13     input-> 15      ergibt 11,15,13

so verstehe ich die methode, denn zuerst erhält man ja die referenz vom vorgänger und legt sie in vorletztes ab, dann erstellt man den neuen knoten mit der eben abgelegten referenz als vorgänger und dem ende als nachfolger.
Daher macht es irgendwie keinen sinn, dass die methode funktioniert.🙁

 

[eRaaaa]

Hi, an sich hast du Recht, allerdings kennen wir alle die Listimplementierung nicht.
Es muss ja auch nicht unbedingt so sein, dass man sagt, dass das Ende auf

null

zeigt, vllt ist ja hier ein Datensatz-Objekt welches das Ende markieren soll, dann würde die add-Methode Sinn machen.
Also:

11,13,ENDE
13 = vorletztes
13.setNachfolger->15
ENDE.setVorgaenger->15
-->
11,13,15,ENDE

 

[newbie2009]

public class doubleLinked {
	
	class Datensatz{
		private Datensatz vorgänger;
		private Datensatz nachfolger;
		private Datensatz position;
		private Object wert ;
		
		
		public Datensatz(){
			
		}
		
		public Datensatz(Datensatz vorgänger,Datensatz nachfolger, Object wert){
			this.vorgänger=vorgänger;
			this.nachfolger=nachfolger;
			this.wert=wert;
		}
		public Datensatz getVorgänger() {
			return vorgänger;
		}
		public void setVorgänger(Datensatz vorgänger) {
			this.vorgänger = vorgänger;
		}
		public Datensatz getNachfolger() {
			return nachfolger;
		}
		public void setNachfolger(Datensatz nachfolger) {
			this.nachfolger = nachfolger;
		}
		public Object getWert() {
			return wert;
		}
		public void setWert(Object wert) {
			this.wert = wert;
		}

		public void setPosition(Datensatz position) {
			this.position = position;
		}

		public Datensatz getPosition() {
			return position;
		}
		
	}
	
		
	Datensatz anfang=new Datensatz(null,null,"");
	Datensatz ende= new Datensatz(null,null,"");
	Datensatz position;
	
	
		doubleLinked(){
			
			
			
			anfang.setNachfolger(ende);
			ende.setVorgänger(anfang);
			position=anfang;
			
			
		}
	
		
		// bewegt zeiger um einen nach rechts
		void next(){
			if(position.getNachfolger()!=null){
				position=position.getNachfolger();
			}
		}
		
		
		//gibt liste aus
	void print(){
	 position=anfang;
	 while(position.getNachfolger()!=null){
		 next();
		 System.out.println(position.getWert()+"");
		 
	 }System.out.println();
	}

	void addBehind(Object key){
		// erst 
		Datensatz vorletztes = ende.getVorgänger();
		
		Datensatz neu = new Datensatz(vorletztes,ende,key);
		vorletztes.setNachfolger(neu);
		ende.setVorgänger(neu);
		
	}
	
	
		public static void main(String[] args) {
			
			doubleLinked list = new doubleLinked();
		
			list.addBehind(10);
			list.addBehind(11);
			list.addBehind(13);
			list.addBehind(15);
			list.addBehind(77);
			
			
			list.print();
		
			
		}
		
	
	}

 

[Semox]

Hi newbie2009

Ich habe auch eine doppelt verkettete Liste geschrieben, die noch einige wenige Bugs hat, aber sonst recht gut funktioniert. Hier ist der Link zur Source...

http://www.java-forum.org/hausaufga...tete-liste-erzeugen-editieren.html#post647403

Vielleicht kannst Du Dir da ja was abgucken...

Viele Grüße,
Semo

 

[eRaaaa]

War da jetzt noch eine Frage offen? 😀

    Datensatz anfang=new Datensatz(null,null,"");
    Datensatz ende= new Datensatz(null,null,"");

siehe letzter Post

 

[newbie2009]

hehe ja stimmt anfang und ende werden nur als markierung benutzt 🙂
Aber dann müsste die methode doch auch funktionieren oder nich, auf den ersten blick tut sie es auch aber irgendwas läuft da verkehrt...

void addfirst(Object key){
		
		Datensatz elem = anfang.getNachfolger();
		Datensatz neu = new Datensatz(anfang,elem,key);
		anfang.setNachfolger(neu);
		
		
			
		}

😳

oh ich glaube das muss so heißen 😀

		void addfirst(Object key){
		
		
		Datensatz next= anfang.getNachfolger();
		
		Datensatz neu = new Datensatz(anfang,next,key);
		anfang.getNachfolger().setVorgänger(neu);
		
		anfang.setNachfolger(neu);
		
		
			
		}

mm oder doch nich oh man referenzen verwirren mich immer 😀

 

[eRaaaa]

nur schnell überflogen, aber wahrscheinlich fehlt da das [c]elem.setVorgänger(neu);[/c] im ersten Code...

EDIT:

oh man referenzen verwirren mich immer

wenn du das so nicht kannst, mal es dir doch einfach auf:

ANFANG <--> 10 <-->  ENDE

die 11 willst du jetzt zwischen ANFANG und 10 einfügen.
ANFANG zeigt im Moment auf 10, d.h. du musst auf jedenfall dort den Nachfolger neu setzen (auf 11, vorher natürlich den Aktuellen merken *g*)
Das bedeutet auch immer dass du den Vorgänger von 11 setzen musst
- anfang.setNachfolger(11)
- 11.setVorgaenger(anfang)

ANFANG <--> 11     |     10  <-->  ENDE

so, jetzt musst du die beiden Teilen natürlich wieder zusammenfrickeln.

- 11.setNachfolger(tmpNachfolgerVonAnfang(10))
- tmpNachfolgerVonAnfang.setVorgaenger(11)

ANFANG <--> 11  <--> 10  <-->  ENDE

 

[newbie2009]

hehe vielen dank 🙂
aber so klappts jetzt 🙂

void addfirst(Object key){
		
		
		Datensatz next= anfang.getNachfolger();
		Datensatz neu = new Datensatz(anfang,next,key);
		anfang.getNachfolger().setVorgänger(neu);
		anfang.setNachfolger(neu);
		
		
			
		}