Doppelt Verkettete Listen

L

Lukas_g1

Grünschnabel
Hallo Leute. Langsam bin ich am verzweifeln. Ich komm einfach nicht mit doppelt verketteten Listen zurecht. Ich hab hier einen Code für einfach verketete Listen, den ich aber um schreiben will , so dass er zu Doppelt verketteten Listen wird....


public class Cons2 {

/** Creates a new instance of Cons2 */
public Object obj; // das Objekt in dieser Zelle
public Cons2 next;
public Cons2 prev;
// Verweis auf die naechste Zelle
public Cons2(Object obj) {
this.obj = obj;
next = null;
prev = null;

}

}

public class ConsList
{
private Cons head, foot; // Kopf und Fuss der Liste
public ConsList() { head = foot = null; /* neue leere Liste */ }
public boolean contains(Object obj) { return contains(head, obj); }
protected boolean contains(Cons cons, Object obj) {
if (cons == null) return false;
else if (cons.obj == obj) return true;
else return contains(cons.next, obj);
}
public void print() {
System.out.print("Liste [");
print(head); // rekursive Ausgabe der Cons-Zellen
System.out.println("]");
}
protected void print(Cons cons) {
if (cons == null) return ; // letzte Zelle erreicht
System.out.print(cons.obj); // Objekt ausgeben
if (cons.next != null) {
System.out.print(", ");
print(cons.next); // Rekursiv weiter
}
}
public void insert(Object obj) {
Cons cons = new Cons(obj); // neue Cons-Zelle
cons.next = head; // vorne anfuegen..
head = cons; // .. und Kopf der Liste anpassen
if (foot == null) foot = cons; // eventuell auch den Fuss
}
public void append(Object obj) {
Cons cons = new Cons(obj); // neue Cons-Zelle
if (foot == null) head = foot = cons; // genau eine Cons-Zelle
else { // hinten anfuegen und Fuss anpassen
foot.next = cons;
foot = cons;
}
}
public void remove(Object obj) {
if (head == null) return ;
if (head.obj == obj) {
if (head == foot) foot = head = null;
else head = head.next; // erste Cons-Zelle entfernen
} else remove(head, head.next, obj);
}
protected void remove(Cons prev, Cons cons, Object obj) {
if (cons == null) return ;
if (cons.obj == obj) {
// vorherige Cons-Zelle auf Nachfolgende zeigen lassen,
// somit faellt 'cons' aus der Liste
prev.next = cons.next;
if (foot == cons) // evtl. Fuss anpassen
foot = prev;
} else remove(cons, cons.next, obj);
}
public boolean isEmpty() { return head == null; }
public Object removeHead() {
if (head == null) return null;
Object res = head.obj;
if (head == foot) head = foot = null;
else head = head.next;
return res;
}

public static void main (String ... args) {
// Kleines Testprogramm fuer Listen:
ConsList l = new ConsList();
System.out.println("leer? " + l.isEmpty());
String s1 = "Hallo", s2 = "Welt";
l.insert(s1);
System.out.println("leer? " + l.isEmpty());
l.print();
l.insert(s2);
l.print();
l.remove(s2);
l.print();
l.append(s2);
l.print();
l.remove(s2);
l.remove(s1);
l.print();
System.out.println("leer? " + l.isEmpty());
}
}


wäre super wenn mir jemand helfen könnte, hab schon unzählige Stunden damit tot geschlagen... Danke euch um Vorraus.
 
Formatiere doch deinen Code mal mit den Code Tags dieses Forums [code=java]...[/code] und beschreib doch mal wo zur Zeit das Problem in deiner Implementierung ist. Am Besten konnte ich mir übrigens verkettete Listen immer als Waggons eines Zugs vorstellen.
 
Muss das zwingen mit verketteten Listen gemacht sein? Java bietet da die Collections an (List, Map, ArrayList, Vector usw.) die für genau solche Probleme eingesetzt werden sollen.
Warum selber machen, was schon als Bibliothek verfügbar ist?
(ausser es sei für die Ausbidung)
 
Hallo,

meiner Meinung nach du hast zu viel unnützliches Code drin.

Schau mal hier

Da weisst du vielleicht, wie man anfängt und kommt schneller voran. Du musst zuerst einfach verkettete Liste verstehen, damit du dann eine doppelt verkettete Liste programmieren kannst.

Gruß
lernen.2007
 
Kann mir jemand bitte den Code hinschreiben,... ich glaub für insert hab ich ihn aber für remove noch nicht. Tausend dank im vorraus

Java: 
public void insert(Object obj) { 
      Cons2 cons = new Cons2(obj);   // neue Cons-Zelle 
     if (head == foot) { 
            
          cons.prev = cons; 
          cons.next = foot; 
          head = cons; 
       } 
        
       cons.next = head; 
        
       if (head != foot) { 
              
       head.prev = cons; 
          head = cons; 
       cons.prev = foot; 
       } 
   }
 
Zuletzt bearbeitet:
Hi,
ich hab eine Aufgabe bekommen ein beliebiges Programm zu schreiben mit einer Datenstruktur die wir in der Vorlesung durchgenommen haben, aber dazu dürfen wir keine der Collection-Klassen nehmen und keinen Code den wir in Beispielaufgaben oder in Praktika behandelt haben. Naja und mehr als 10 Klassen sollens dann auch nicht werden.

Da hab ich mir gedacht schreibste mal ne LinkedList, da wir das nur in der Vorlesung hatten und keine Beispiele o.ä. dazu. Das ganze Programm soll eine (primitive) Studentenverwaltung werden.

Ich hab mich auch direkt mal hingesetzt und eine MyLinkedList Klasse geschreiben geschrieben.
Kann sich das mal jemand anschauen und mir evtl. Tipps geben was man besser machen kann?

Hier der Code:

Java: 
package studentenverwaltung.list;

import java.util.NoSuchElementException;


public class MyLinkedList<E>{
	private MyLink<E> start;
	int size;
	
	public MyLinkedList() {
		start = new MyLink<E>(null,null,null);
		start.setNext(start);
		start.setPrev(start);
		size = 0;
		
	}
	/**
	 * Gibt das erste Element der Liste zurück.
	 * @return Das erste Element der Liste
	 * @throws NoSuchElementException wenn die Liste keine Elemente enthält
	 */
	public E getFirst(){
		if(size==0)
			throw new NoSuchElementException();
		return start.getNext().getO();
	}
	/**
	 * Gibt das letzte Element der Liste zurück.
	 * @return Das letzte Element der Liste
	 * @throws NoSuchElementException wenn die Liste keine Elemente enthält
	 */
	public E getLast(){
		if(size==0)
			throw new NoSuchElementException();
		return start.getPrev().getO();
	}
	
	/**
	 * Löscht das erste Element aus der Liste und gibt das Element zurück.
	 */
	public E removeFirst(){
		if(isEmpty())
			throw new NoSuchElementException();
		
		MyLink<E> ml = start.getNext();
		ml.getNext().setPrev(start);
		ml.getPrev().setNext(ml.getNext());			
		size--;
		return ml.getO();
	}
	/**
	 * Löscht das letzte Element aus der Liste und gibt das Element zurück.
	 */
	public E removeLast(){
		if(isEmpty())
			throw new NoSuchElementException();
		
		MyLink<E> ml = start.getPrev();
		ml.getNext().setPrev(ml.getPrev());
		ml.getPrev().setNext(start);			
		size--;
		return ml.getO();
	}
	
	/**
	 * Fügt das übergebene Element an das Ende der Liste.
	 * Äquivalent zu {@link #addLast}
	 * @param o Das einzufügende Element
	 */
	public void add(E o){
		MyLink<E> ml = new MyLink<E>(o,start.getPrev(),start);
		start.getPrev().setNext(ml);
		start.setPrev(ml);
		size++;
	}
	/**
	 * Fügt das übergebene Element an den Anfang der Liste.<br/>
	 * @param o Das einzufügende Element
	 */
	public void addFirst(E o){
		MyLink<E> ml = new MyLink<E>(o,start,start.getNext());
		start.getNext().setPrev(ml);
		start.setNext(ml);
		size++;
	}
	/**
	 * Fügt das übergebene Element an das Ende der Liste.<br/>
	 * Äquivalent zu {@link #add}
	 * @param o Das einzufügende Element
	 */
	public void addLast(E o){
		add(o);
	}
	/**
	 * Gibt die Position des übergebenen Elementes (den ersten Fund) in der Liste zurück.<br/>
	 * Falls das Element nicht in der Liste enthalten ist wird -1 zurückgegeben.
	 * @param o Das zu suchende Element
	 * @return Der Index des zu suchenden Elementes
	 */
	public int indexOf(E o){
		if(isEmpty())
			return -1;
		
		int count = 0;
		MyLink<E> tmp = start;
		while(count < size){
			tmp = tmp.getNext();
			if(tmp.getO().equals(o))return count;
			count++;
		}
		return -1;
	}
	/**
	 * Prüft ob die Liste leer ist.
	 * @return true falls Liste leer sonst false
	 */
	public boolean isEmpty(){
		return size==0;
	}
	/**
	 * Gibt die Größe der Liste zurück.
	 * @return Anzahl der Listenelemente
	 */
	public int size(){
		return size;
	}
	/**
	 * Löscht alle Elemente aus der Liste.
	 */
	public void clear(){
		start.setNext(start);
		start.setPrev(start);
		size = 0;
	}
	
	
	/**
	 * Gibt das Element des übergebenen Indexes zurück.
	 * @param index Der Index des Elementes
	 * @return Das Element
	 * @throws IndexOutOfBoundsException wenn Index nicht im Wertebereich
	 */
	public E get(int index){
		if(index < 0 || index >= size)
			throw new IndexOutOfBoundsException();
		
		int i = -1;
		MyLink<E> ml = start;
		while(i < size && index != i){
			ml = ml.getNext();
			i++;
		}
		return ml.getO();
	}
	
	/**
	 * Prüft ob sich solch ein Element in der Liste befindet.<br/>
	 * Gibt beim ersten Fund true zurück.
	 * @param o das Element wonach gesucht werden soll
	 * @return true falls Element enthalten sonst false
	 */
	public boolean contains(E o){
		return indexOf(o) != -1;
	}
	
	public E remove(int index){
		if(index < 0 || index >= size)
			throw new IndexOutOfBoundsException();
		
		int i = -1;
		MyLink<E> ml = start;
		while(i < size && index != i){
			ml = ml.getNext();
			i++;
		}
		ml.getPrev().setNext(ml.getNext());
		ml.getNext().setPrev(ml.getPrev());
		size--;
		return ml.getO();
	}
}


Dazu noch die Klasse MyLink:
Java: 
package studentenverwaltung.list;

public class MyLink<E> {
	private E o;
	private MyLink<E> prev;
	private MyLink<E> next;
	
	public MyLink(E o,MyLink<E> prev,MyLink<E> next){
		this.o = o;
		this.prev = prev;
		this.next = next;
	}

	public E getO() {
		return o;
	}

	public MyLink<E> getPrev() {
		return prev;
	}

	public MyLink<E> getNext() {
		return next;
	}

	public void setO(E o) {
		this.o = o;
	}

	public void setPrev(MyLink<E> prev) {
		this.prev = prev;
	}

	public void setNext(MyLink<E> next) {
		this.next = next;
	}
	
}
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück