Verkette Listen

Archiv Algorithmik II
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

Verkette Listen
Hab mich mal an verketteten Listen versucht, folgendes ist dabei herausgekommen…
Vielleicht interessierts ja jemanden.

[code]
class ListElem
{
public Object obj;
public ListElem next;

//Konstruktoren
public ListElem(){}
public ListElem(Object obj, ListElem next)
{
	this.obj = obj;
	this.next = next;
}

}

class IllegalPositionIndexException extends Exception {
String fehlermeldung;

public IllegalPositionIndexException()
{
	fehlermeldung = new String("Es ist ein Fehler aufgetreten!");
}
public IllegalPositionIndexException(String s)
{
	this.fehlermeldung = s;
}

public String getFehlermeldung()
{
	return fehlermeldung;
}

}

public class linkList
{
class Head {}
private ListElem head, act;
private int length;

public linkList()
{
	head = new ListElem(new Head(), null);
	act = head;
	length = 0;
}

//Funktion, die den act-Pointer auf das an pos stehende Element setzt
private void setAct(int pos)
	throws IllegalPositionIndexException
{
	if(pos < 0 || pos >= length)
		throw new IllegalPositionIndexException("Falsche Position! " + pos +
			  "\nMax. erlaubte Position: " + (length -1));
	else
	{
		act = head;
		for(int i = 0; i <= pos; i++)
			act = act.next;
	}
}

public int length() { return length; }

//Funktion, die das Objekt an einer gegebenen Position ermittelt
public Object itemAt(int pos) 
{
	try {
		setAct(pos);
		return act.obj;
		} catch (IllegalPositionIndexException e) 
			{ e.getFehlermeldung(); 
			  return null;
			}
}
	
		
//Funktion, die Objekte am Ende in die Liste einfügt
public void append(Object obj)
{
	act = head;
	while(act.next != null)
		act = act.next;
		
	act.next = new ListElem(obj, null);
	length++;
}

//Funktion, die eine gegebene Liste an das Ende haengt
public void append(linkList lst)
{
	act = head;
	while(act.next != null)
		act = act.next;
	
	if(this == lst)
	{
		linkList lst2 = (linkList)lst.clone();
		act.next = lst2.head.next;
		length += lst2.length;	
	}
	else
	{
		act.next = lst.head.next;
		length += lst.length;
	}
}

//Funktion, die ein Element an eine beliebige Stelle setzt
public void insert(int pos, Object obj)
	throws IllegalPositionIndexException
{
	if(pos < 0 || pos > length)
		throw new IllegalPositionIndexException("Fehler in Methode " +
			"insert(int pos, Object obj)!\n" + "Position " + pos +
			" nicht verfuegbar!");
	else
	{
		act = head;
		for(int i = 0; i < pos; i++)
			act = act.next;
		
		act.next = new ListElem(obj, act.next);
		length++;
	}
}

// Lösche Eintrag an Position pos
public void delete(int pos)
{		
		if(length == 1)
		{
			head.next = null;
			length--;
		}
		else
		{
			if(pos == 0)
			{
				head.next = head.next.next;
				length--;
			}
			else
			{
				try {
				setAct(pos-1);
				act.next = act.next.next;
				length--;
				} catch(IllegalPositionIndexException e)
				{
				System.out.println("Fehler in Methode delete()");
				System.out.println(e.getFehlermeldung());
				}
			}
		}
	}


// Funktion zum clonen des Objekts
// Notwendig für append(linkList lst)
public Object clone()
{
	linkList l = new linkList();
	act = head;
	
	for(int i = 0; i < this.length; i++)
	{
		act = act.next;
		l.append(act.obj);
	}
	return l;
}

// Ersetzt Objekte an Position pos
public void replace(int pos, Object obj)
{
	try {
		setAct(pos);
		act.obj = obj;			
	} catch(IllegalPositionIndexException e)
		{
			System.out.println("Fehler in Methode replace(int pos, " +
				"Object obj)\n" + e.getFehlermeldung());
		}
}

	
// Swapt zwei Listenfelder
public void swap(int pos1, int pos2)
{
	if(pos1 >= length || pos1 < 0 || pos2 >= length || pos2 < 0)
	{
		System.out.println("Ungueltige Positionen, kann nicht Swappen!");
	}
	else
	{
	Object temp = itemAt(pos1);
	replace(pos1, itemAt(pos2));
	replace(pos2, temp);
	}
}
public void printList()
{
	System.out.println("Laenge: " + length);
	act = head;
	for(int i = 0; i < length; i++)
	{	
		act = act.next;
		System.out.println("Das " + i + ". Element ist ein: " + act.obj.toString());
	}
}



public static void main(String[] args)
{
	linkList l = new linkList();
	linkList l2 = l;
	try{
	l.insert(0, new Character('c'));
	l.insert(0, new Character('d'));
	l.append(new Integer(5));
	l.append(new Float(10));
	l.append(l2);
	l.insert(4, new Integer(4));
	l.printList();
	l.swap(0, 20);
	l.printList();
	l.delete(-9);
	l.delete(3);
	l.printList();
	l.swap(0, 5);
	l.swap(3,2);
	l.printList();
	} catch(Exception e) {}
	
	
	
}

}

			[/code]

Verbesserungsvorschläge wilkommen!

3

Die “Philosophie” hinter verketteten Listen sieht eigentlich keinen Random-Access (also per Index) vor, sondern nur, entweder alle Elemente zu durchlaufen oder von einem Element das nächste (evtl. auch vorherige) zu erhalten.

4

guck dir mal die klasse exception selber an. die macht per se schon alles das, was du implementiert hast!