einfach verkettete Liste

M4ST0R

Hallo, ich hatte eine Aufgabe, eine einfach verkettete Liste zu erstellen.

Genauern gesagt ist die Aufgabe nicht so einfach, eher komplex. Ich soll eine Klasse mit 3 Methoden push_front, remove und print_all erstellen. Im Internet habe ich ein kleines Beispiel gefunden, wo noch mehr Methoden verwendet wurden.

push_front: "Hierbei soll eine Referenz auf ein Element (Objekt einer Klasse, die das Interface ListElement implementiert.) der Liste hinzugefügt werden. Implementieren Sie mindestens 2 nichtabstrakte Subklassen von Element."
remove: "Damit sollen alle Referenzen auf ein Element (Vergleich der Referenzen) aus der Liste entfernt werden."
print_all: Alle Elemente (zugehörige Zeichenkettendarstellungen) ausgeben.
Zusatz: Verwendung von Polymorphismus.

Ich habe schonmal etwas am Code rumprobiert und es kommt einfach nichts gutes dabei raus. Ich will auch nicht, dass Ihr mir die komplette Aufgabe löst, sondern nur in die richtige Richtung zeigt.

Liste.java

public class Liste {

	private Liste altesElement;
	String Daten;
	public Liste next;
	public Liste last;

	public Liste()
	{
		altesElement=null;
	}
	public boolean leer()
	{
		return(altesElement==null);
	}
	public void push_front(String string)
	{
		Liste neuesElement= new Liste();
		neuesElement.next=altesElement;
		neuesElement.last=null;

		if(neuesElement.next!=null){
			Liste temp = neuesElement.next;
			temp.last = neuesElement;
		}
		altesElement=neuesElement;
	}
	public Liste rückgabe()
	{
		return(altesElement);
	}
	public void remove(Liste l1)
	{
		altesElement=altesElement.next;
		altesElement.last=null;
	}
	public void print_all()
	{
		Liste aktuell=altesElement;
		while(aktuell!=null){
			System.out.println(Daten);
			aktuell=aktuell.next;
		}
	}
	public String toString()
	{
		return Daten;
	}
	public static void main(String[] args)
	{

	}
}

IListe.java

interface IListe {
	public void Etwas(String s);

}
class Test1 extends Liste implements IListe
{
	public void Etwas(String s)
	{
		Liste l1=new Liste();
		l1.push_front("1");

		l1.print_all();
		l1.remove(l1);
		l1.print_all();
	}

}
class Test2 implements IListe
{
	public void Etwas(String s)
	{
		Liste l2=new Liste();
		l2.push_front("2");

		l2.print_all();
		l2.remove(l2);
		l2.print_all();
	}
}

Leo29

Du solltest ruhig auf Papier erstmal alles schreiben, bevor du an Codieren geht’s (es hilft)

Eine verkette Liste ist eine Sammlung von Objekte die miteinander verbunden sind!

Liste A = new Liste();

Die Klasse hat 4 Elemente, davon ist der String Daten wichtig, weil dort die Information für eine spätere Ausgabe gespeichert wird.

A.Daten = "1";

Jetzt geht es darum ein 2. Objekt zu erzeugen und vor A zu hängen!

Liste B =  new Liste();
B.Daten = "2";

A. push_front(B);

Die Funktion "push_front" erwartet ein Objekt von Typ Liste und sieht so aus:

public void push_front(Liste liste) 
{ 
     this->last = liste;
     liste.next = this;  
}

so, ich hoffe, ich könnte dir auf dem richtigen Weg bringen

remove solltest du erst schreiben, wenn du die liste hast und mit print ausgeben kannst!

GPC

Hallo,

habt ihr zwei den Sinn einer Liste denn verstanden? Ich bezweifle das gerade ein wenig, denn ich frage mich, was die ganzen Member der Liste da sollen? Denn eigentlich "besteht" eine Liste aus Listenelementen, die die Daten beinhalten.

Such doch bei Google nach ein paar Tutorials zu dem Thema, gibt genug dazu.

MfG

GPC

Leo29

habt ihr zwei den Sinn einer Liste denn verstanden? Ich bezweifle das gerade ein wenig, denn ich frage mich, was die ganzen Member der Liste da sollen? Denn eigentlich "besteht" eine Liste aus Listenelementen, die die Daten beinhalten.

hehe musste 2-mal lesen, um zu verstehen was du meinst

Das Problem scheint, dass der Name der Klasse ein wenig verwirrend ist.
Die Klase ist nicht die liste, sondern die Liste wird aus Objekte der Klasse erzeugt! Also die Elemente der liste sind Objekte von Typ "Liste"

Klar könnte man es besser machen, aber es geht nicht darum die Lösung zu schreiben oder von dem Beispiel abzuraten!

Obwohl, Java nicht gerade die richtige Sprache wäre, um mit Verkettete Listen zu arbeiten

ok ein paar Definitionen, vielleicht hilft das ja!

Verkettete Listen gehören zu den dynamischen Datenstrukturen, die eine Speicherung von einer im Vorhinein nicht bestimmten Anzahl von miteinander in Beziehung stehenden Werten einfacher oder zusammengesetzter Datentypen erlauben. Sie werden durch Zeiger auf die jeweils folgende(n) Knoten oder Speicherzellen des Arbeitsspeichers realisiert.

Doppelt (mehrfach) verkettete Liste:
Hier hat jedes Element der Liste nicht nur einen Zeiger auf das nachfolgende, sondern auch einen zusätzlichen zweiten auf das Vorgänger-Element.

Der Vorgänger-Zeiger des ersten Elementes zeigt auf ein Dummy-Element, wie auch der Nachfolger-Zeiger des letzten Elementes. Dieses besondere Element dient zum Auffinden des Anfangs und des Endes der doppelt verketteten Liste.

Vorteile

* Über die Liste kann von hinten nach vorne iteriert werden.
* Die Elemente in der zweiten Hälfte einer sortierten Liste sind schneller aufzufinden.

Nachteile

* Es wird etwas mehr Speicher für die zusätzlichen Zeiger benötigt.

GPC

Leo29 schrieb:

Das Problem scheint, dass der Name der Klasse ein wenig verwirrend ist.
Die Klase ist nicht die liste, sondern die Liste wird aus Objekte der Klasse erzeugt! Also die Elemente der liste sind Objekte von Typ "Liste"

Denke ich nicht, warum sollte ein Listenelement eine push_back Methode brauchen? Die gehört eindeutig in die Listenklasse selber. Da stimmt's einfach nicht.

Klar könnte man es besser machen, aber es geht nicht darum die Lösung zu schreiben oder von dem Beispiel abzuraten!

Den korrekten Weg aufzeigen würde schon reichen.

<Klugscheiß>
Im Übrigen hat Java "offiziell" keine Zeiger, sondern nur Referenzen, die sich aber wie C bzw. C++ Zeiger verhalten
</Klugscheiß>

Vorteile

* Über die Liste kann von hinten nach vorne iteriert werden.

Ich kann auch rückwärts über ein Array laufen.

* Die Elemente in der zweiten Hälfte einer sortierten Liste sind schneller aufzufinden.

Huh? Das hat nichts mit der Liste als Datenstruktur zu tun.

Echter Vorteil:
* Einfügen und Löschen an beliebigen Positionen ist immer gleich schnell.

Nachteile

* Es wird etwas mehr Speicher für die zusätzlichen Zeiger benötigt.

Ein weiterer Nachteil ist, dass man keinen direkten Zugriff hat, sondern immer über die Elemente itererieren muss, bis man bei einem bestimmten ist.

MfG

GPC

Leo29

Denke ich nicht, warum sollte ein Listenelement eine push_back Methode brauchen? Die gehört eindeutig in die Listenklasse selber. Da stimmt's einfach nicht.

hey, verrate doch nicht die Lösung, sonst lernt er nicht!

ok, ich werde es nicht wieder tun. Ich werde nie wieder eine Definition aus Wikipedia nehmen

GPC

Leo29 schrieb:

ok, ich werde es nicht wieder tun. Ich werde nie wieder eine Definition aus Wikipedia nehmen

Die Vor - und Nachteile stimmen schon, aber nur wenn man eine einfach verkettete mit einer doppelt verketteten vergleicht

MfG

GPC