Vererbte Liste

[Reap]

Hallo....ich hab jetzt mal eine einfach verkettete Liste mit all ihren Methoden gemacht. Nun sollen wir mittels Vererbung eine doppelt verkettete Liste machen. Und genau hier liegt mein Verständnisproblem.
Die Klasse Node schaut so aus:

public class Node {
    
    public Comparable data;				// content of the Node
    public Node next;					// pointer to next Node
    public Node(Comparable data) {		// constructor
        this.data = data;
        this.next = null;
    }
   
}

Die Klasse DoubleNode so:

public class DLNode extends Node{
	
	public Node prev;
	
    public DLNode(Comparable elem){
		super(elem);
		this.prev = null;
	}
	
}

Die Methode insert in LinkedList(einfach verkettet)

p

ublic class LinkedList implements MyList{
    
    protected int size = 0;	// size of the list, so that getSize() has O(1)
    protected Node head; // first node of the list
    protected Node tail; // last node of the list
    
    public LinkedList() { // dummy-element
    	head = new Node(null);
        tail = head;
    }
    
    //insert a node,whose element is val, after the node pos and return the added node
    protected Node insert(Node pos, Comparable val){
    	Node theNode = new Node(val);
    	theNode.next = pos.next;
    	pos.next = theNode;
    	size++;
    	
    	if(pos == tail){
    		tail = theNode;
    	}
   
    	return theNode;
    }
  }

Soweit noch alles klar aber jetzt kommts:

public class DoubleLinkedList extends LinkedList{

	protected int size = 0;	// size of the list, so that getSize() has O(1)
    protected DLNode head; // first node of the list
    protected DLNode tail; // last node of the list
    
    public DoubleLinkedList() { // dummy-element
    	super();
    }
    
    //insert a node,whose element is val, after the node pos and return the added node
    protected DLNode insert(DLNode pos, Comparable val){
    	DLNode temp = new DLNode(val);
    	
    	//always 4 pointer operations to add a node
    	temp.next = pos.next;
    	temp.next.prev = temp; ...ERROR 
         ...GEHT NICHT DA WENN ICH TEMP.NEXT EINGEBE ER GLAUBT 
         DER KNOTEN SEI VON DER KLASSE NODE UND ER SOMIT KEIN PREV MEHR KENNT. ICH MUSS
        ABER LEIDER DIE KLASSE "DLNode" SO LASSEN WIE ES IST DASS WAR ÜBUNGSVORGABE
    	
    	pos.next = temp;
    	temp.prev = pos;
    	size++;
    	
    	if(pos == tail){
    		tail = temp;
    	}
   
    	return temp;
    }

Was soll ich also tun?
mfg,
Reap

 

[messi]

       ((DLNode) temp.next).prev = temp;

 

[Reap]

Hallo...danke...hätte mir auch selber einfallen können (aber dass sagt man immer später 8) )
Warum erkennt JAVA dass eigentlich nicht automatisch denn ich habe ja temp als DLNode deklariert also müsste es
ja wissen dass temp.next auch vom Typ DLNode sein wird.....wahrscheinlich weil ich next als Node deklariert habe...wenn ich next als DLNode deklariert hätte dann wäre es kein Problem dass er mir temp.next.prev akzeptiert.

Ich hab da noch eine Frage:
Wenn ich DLNode so umändere dass ich next auch als DLNode deklariere bleibt mir dann immer noch ein Node next
in meiner DLNode Klasse übrig? Wenn ja wpher weiß dann das Programm welches next es nehmen solll? Welches next nimmt dann der Konstruktor?

public class DLNode extends Node{
	
	public Comparable data;
         public DLNode next;
	public DLNode prev;
	
    public DLNode(Comparable elem){
		super(elem);
		this.prev = null;
	}
	
}

mfg,
Reap

 

[messi]

Warum erkennt JAVA dass eigentlich nicht automatisch denn ich habe ja temp als DLNode deklariert also müsste es ja wissen dass temp.next auch vom Typ DLNode sein wird.....wahrscheinlich weil ich next als Node deklariert habe...wenn ich next als DLNode deklariert hätte dann wäre es kein Problem dass er mir temp.next.prev akzeptiert.

Genau, aber das wäre schlechtes Design.

Wenn ich DLNode so umändere dass ich next auch als DLNode deklariere bleibt mir dann immer noch ein Node next in meiner DLNode Klasse übrig? Wenn ja wpher weiß dann das Programm welches next es nehmen solll? Welches next nimmt dann der Konstruktor?

DLNode.next "überschattet" dann Node.next. Ist aber auch wieder schlechtes Design, weil beide Felder erreichbar sind und du deshalb aufpassen musst, welches benutzt wird.

 

[Guest]

Hallo...danke für die Antwort...mittlerweile habe ich auch alle Methoden der DoubleLinkedList fertig.
Was mich aber stört ist dass ich so wenig Methoden von der LinkedList übernehmen kann...nicht einnmal den Konstruktor.....könnte man dass nicht irgendwie anders...geschickter machen?

public class DoubleLinkedList extends LinkedList{

    protected DLNode head; // first node of the list
    protected DLNode tail; // last node of the list
    
    public DoubleLinkedList() { // dummy-element
    	head = new DLNode(null);
        tail = head;
    }
    
    //insert a node,whose element is val, after the node pos and return the added node
    protected DLNode insert2(DLNode pos, Comparable val){
    	
    	DLNode temp = new DLNode(val);
    	temp.next = pos.next;
        
        if(temp.next != null){
        ( (DLNode) temp.next).prev = temp; 
        }
        
        pos.next = temp;
    	temp.prev = pos;
    	size++;
    	
    	if(pos == tail){
    		tail = temp;
    	}
   
    	return temp;
    }

.....usw. andere Methoden
}

insert 2 funktioniert nur wenn ich den Konstruktor neu schreibe und head und tail auch in DLNode umschreibe.
Is auch klar...aber gibt es nicht trotzdem irgendeinen Weg dass ich nicht den Konstruktor umändern muss?

Denn wenn ich ihn nicht umändere dann erstellt er mir einen einfachen Knoten von der Klasse Node und keinen DLNode...


mfg,
Hannes

 

[Beni]

Damit du möglichst viel von LinkedList übernehmen kannst, musst du LinkedList entsprechend aufbauen.
Ich kann dir mal ein Beispiel geben, wie ich das versucht hätte.

Zum die Knoten herstellen, gibts eine eigene Methode "createNode", die einfach "new Node" zurückgibt. Wenn man die überschreibt, kann man "new DNode" zurückgeben, und sofort verwendet die Liste nur noch DNodes.

Damit man add/insert/remove/etc... nicht neu erfinden muss, würde ich noch eine Methode einbauen, welche nur das Verbinden der Knoten übernimmt. Das Verbinden ist ja der einzige Schritt, bei dem sich die DoubleLinkedList wirklich total anders verhält, als die einfache LinkedList (das sind die Methoden de-/connect).

public class LinkedList {
	private Node head, tail;
	private int size = 0;
	
	public LinkedList(){
		// nix zu tun hier
	}
	
	// ein Knoten einfügen
	public void add( Object value ){
		if( size == 0 ){
			head = create( value );
			tail = head;
		}
		else{
			Node node = create( value );
			connect( tail, node, null );
			tail = node;
		}
		size++;
	}
	
	// Knoten an der Stelle index entfernen
	public void remove( int index ){
		if( size == 1 ){
			head = null;
			tail = null;
		}
		else{
			Node node = head;
			for( int i = 0; i+1 < index; i++ ){
				node = node.getNext();
			}
			
			Node head = node;
			Node remove = head.getNext();
			Node tail = remove.getNext();
			
			deconnect( head, remove, tail );
		}
		size--;
	}
	
	// Einen neuen Knoten herstellen
	protected Node create( Object value ){
		return new Node( value );
	}
	
	// Der Knoten "middle" irgendwie zwischen "head" und "tail" einbauen
	// (head und tail können null sein)
	// Vorher: head.getNext() == tail
	// Nachher: head.getNext() == middle && middle.getNext() == tail
	protected void connect( Node head, Node middle, Node tail ){
		if( head != null )
			head.setNext( middle );
		
		middle.setNext( tail );
	}
	
	// Den Knoten "middle", der zwischen "head" und "tail" ist, irgendwie
	// entfernen (head und tail können null sein).
	// Borher: head.getNext() == middle && middle.getNext() == tail
	// Nachher: head.getNext() == tail
	protected void deconnect( Node head, Node middle, Node tail ){
		if( head != null )
			head.setNext( tail );
	}
	
	// Die Knoten-Klasse, von der kann man einfach ableiten...
	protected static class Node{
		private Node next;
		private Object value;
		
		public Node( Object value ){
			this.value = value;
		}
		
		public Node getNext() {
			return next;
		}
		public void setNext( Node next ) {
			this.next = next;
		}
		public Object getValue() {
			return value;
		}
		public void setValue( Object value ) {
			this.value = value;
		}
	}
}

[Edit: "ICH MUSS ABER LEIDER DIE KLASSE "DLNode" SO LASSEN WIE ES IST DASS WAR ÜBUNGSVORGABE".
Arg... Sorry, hab mal wieder überlesen, dass ihr nicht selbst denken dürft. Na ich hoffe mal, dass du trotzdem mit meinem Geschreibsel was anfangen kannst. ]

 

[Reap]

Hallo...danke für die Antwort.

Ich hab aber ein Problem und zwar bei createNode()...Wenn ich jetzt createNode überschreiben will in meiner
DoublelinkedLst Klasse so schreibt er dass das nicht geht:

create in LinkedList()

// create a new node
    protected Node create( Comparable val ){ 
       return new Node(val); 
    }

Versuch create in DoubleLinkedList umzuschreiben

// create a new node
    protected DLNode create( Comparable val ){ 
       return new DLNode(val); 
    }

haut er mir einen Fehler raus da DLNode create nicht dasselbe ist wie Node create....ich kanns noch kompensieres
indem ich wieder einen typecast mache aber Code spare ich halt dann nur bedingt.

mfg,
Reap

 

[Beni]

Hm? Ich bekomme keine Probleme wenn ich sowas mache:

public class DLinkedList extends LinkedList{
	protected Node create( Object value ) {
		return new DNode( value );
	}
	
	protected void connect( Node arg0, Node arg1, Node arg2 ) {
		// ...
	}
	
	protected void deconnect( Node arg0, Node arg1, Node arg2 ) {
		// ...
	}
	
	protected static class DNode extends Node{
		private DNode previous;
		
		public DNode( Object value ){
			super( value );
		}

		public DNode getPrevious() {
			return previous;
		}

		public void setPrevious( DNode previous ) {
			this.previous = previous;
		}
		
		
	}
}

 

[Reap]

Ich aber leider schon.....

protected Node create( Object value ) { 
      return new DLNode( value ); 
   }

Wenn ich den Code hernehme muss ich erst wieder typecasten.....da wenn ich
DLNode a = create(Object) eingebe er mir sagt create(Object) müsse vom Typ
DLNode sein und nicht vom TypNode.

Wenn ich
Node a = create(Object) hernehme dann erzeugt er mir zwar einen Knoten aber er erkennt das prev
nicht.....gibts dafür überhaupt ne Lösung ohne dass ich am Knoten nicht etwas umändere?


Ich weiß dass return DLNode(value) bei der create Mehode nur geht weil jeder DLNode auch ein Node iist.
Also es muss in die Richtung gehen oder? Ich komm einfach nicht weiter...

mfg,
Reap

 

[Beni]

Ohne Cast kommst du bei dieser (leicht unsinnigen *hust*) Aufgabe nicht aus. Irgendwann musst du mal ein "(DLNode)node" einbauen (Es sei denn, du verwendest Generics, aber das ist ein anderes Thema).

 

[Reap]

Hallo...ok ich lass es einfach so wies ist.....es stimmt ja auch so wie is jetzt hab........
mfg,
Reap