Mittwoch, 10. März 2010

 

Verkettete Listen

Folgendes Bild stellt das Prinzip der verketteten Listen dar. Wir benötigen einen Anker (pAnker), der auf das erste Element "zeigt". Jedes Element "zeigt" auf einen Nachfolger. Nur das letzte Element hat keinen Nachfolger und enthält daher null.

In Java könnte das etwa so formuliert werden:

class Element {
Element next;
int data;
Element(int data) {
this.data = data;
}
}

Element anker = null; // leere Liste

Element n = new Element(1);
n.next = anker;
anker = n;

n = new Element(2);
n.next = anker;
anker = n;

n = new Element(3);
n.next = anker;
anker = n;

System.out.println("liste");
for (Element e = anker; e != null; e = e.next) {
System.out.println(e.data);
}

// 1. Element entfernen
anker = anker.next;
System.out.println("liste");
for (Element e = anker; e != null; e = e.next) {
System.out.println(e.data);
}


Folgendes Listing zeigt eine mögliche Implementierung einer einfach verketteten Liste sowie die Verwendung einer solchen Liste als Stack. Neue Elemente werden einfach vorne eingefügt:

public class Liste {

private class Element {
Element next;
int data;

Element(int data) {
this.data = data;
}
}

private Element anker = null;

// private Element ende = null;

public void append(int data) {
if (anker == null) {
anker = new Element(data);
} else {
// suche Ende
Element e = anker;
while (e.next != null) {
e = e.next;
}
// e ist das letzte Element (Ende)
e.next = new Element(data);
}
}

public void insertFirst(int data) {
Element n = new Element(data);
n.next = anker;
anker = n;
}

public void deleteFirst() {
assert (anker != null);
anker = anker.next;
}

public void printList() {
System.out.print("[");
for (Element e = anker; e != null; e = e.next) {
System.out.print(e.data + " ");
}
System.out.println("]");
}

public void push(int data) {
insertFirst(data);
}

public int pop() {
assert (anker != null);
Element e = anker;
anker = anker.next;
return e.data;
}

public boolean isEmpty() {
return anker == null;
}

/**
* @param args
*/
public static void main(String[] args) {
Liste liste = new Liste();
liste.printList();
// liste.insertFirst(1);
// liste.insertFirst(2);
// liste.insertFirst(3);
liste.append(1);
liste.append(2);
liste.append(3);
liste.printList();
liste.deleteFirst();
liste.printList();

Liste stack = new Liste();
stack.push(23);
stack.push(3);
while (!stack.isEmpty()) {
System.out.println(stack.pop());
}
}

}

Da bei obigem Beispiel in der Methode append() immer das Ende der Liste gesucht wird, ist das Anhängen von Elementen etwas aufwändig, vor allem, wenn die Liste schon länger ist. Dies kann man verbessern, indem man auch das Ende der Liste mitspeichert.
Es folgt nun eine etwas andere Implementierung von Elementen (Node) und einer Liste (Liste), welche als Stack oder als Queue verwendet werden kann. Hier werden immer Objekte vom Typ Node in der Liste manipuliert.

public class Node {
Node next;
String data;

public Node(String data) {
this.data = data;
}
public Node() {
data = null;
}
public String toString() {
return data;
}
}

Als Daten werden einfach Strings verwendet.

public class Liste {
private Node anker = null;
private Node last = null;

/**
* hängt Knoten n am Ende der Liste an (für Queue).
*
* @param n
* neuer Knoten
*/
public void put(Node n) {
if (last == null) { // erstes Element
anker = n;
last = n;
} else {
last.next = n;
last = n;
}
}

/**
* liefert erstes Element und entfernt dieses aus der Liste
*
* @return erster Knoten oder null
*/
public Node get() {
Node ret = null;
if (anker != null) {
ret = anker;
anker = anker.next;
if (anker == null) { // war das das letzte Element?
last = null;
}
}
return ret;
}

/**
* pop() für Verwendung als Stack.
*
* @return erstes Element
*/
public Node pop() {
return get();
}

/**
* fügt Knoten vorne ein (für Stack).
*
* @param n
* neuer Knoten
*/
public void push(Node n) {
if (anker == null) {
anker = n;
last = anker;
} else {
n.next = anker;
anker = n;
}
}

/**
* liefert Liste als String.
*
* @return "[erstes,zweites,...]", "[]" bei leerer Liste (KEINE Leerzeichen)
*/
public String toString() {
String ret = "[";
Node n;
for (n = anker; n != null && n.next != null; n = n.next) {
ret += n + ",";
}
if (n != null) {
ret += n;
}
ret += "]";
return ret;
}
}

Das Anhängen von Elementen ist hier effizienter gelöst durch die Verwendung von last, einer Referenz auf das letzte Element.

Labels: ,


Kommentare:

Kommentar veröffentlichen

Abonnieren Kommentare zum Post [Atom]





<< Startseite

This page is powered by Blogger. Isn't yours?

Abonnieren Posts [Atom]