Mittwoch, 25. März 2009

 

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());
}
}

}

Labels: ,


Kommentare:

Kommentar veröffentlichen

Abonnieren Kommentare zum Post [Atom]





<< Startseite

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

Abonnieren Posts [Atom]