|
1.) Listen
. Allgemeines
Eine verkettete Liste ist eine Menge von Elementen, die wie in einem Feld sequentiell organisiert sind. Bei Verwendung
von Listen ist genau zu überlegen, welche Art man verwendet. Wenn nicht unbedingt notwendig, dann sollte man auf die
doppelt bzw. zyklisch verketteten Listen verzichten, da diese mit mehr Aufwand verbunden sind.
+ es muß keine maximale Größe angegeben werden (anders als beim Array)
+ hohe Flexibilität, da Elemente recht leicht umgeordnet werden können
+ relativ einfache Operationen (Einfügen, Löschen). Bei Arrays müßte das ganze Feld verschoben werden.
. Verschiedene Arten von Listen
* einfach verkettete Listen
Jedes Element der einfach verketteten Liste besteht aus einem Datenteil und
aus einem Zeiger auf das nächste Element. Deshalb kennt jedes Element nur seinen
Nachfolger. Es wird ein Zeiger (panker) auf das erste Element der Liste gespeichert, um
die einfach verkettete Liste durchlaufen zu können. Jenes Element das (noch) keinen
Nachfolger hat, hat als Wert im next-Zeiger NULL.
|-----|--| |-----|--| |-----|--|
panker +--> | 1 | +----->| 2 | +----->| 3 | +-----> NULL
|-----|--| |-----|--| |-----|--|
Anwendung der einfach verketteten Listen z. B. Stack (LIFO)
Ein Beispiel in C++:
class STACK {
struct ELEMENT {
ELEMENT *next;
int dat;
} *anf,*hilf;
public:
STACK () {anf=new ELEMENT; anf->next = NULL;}
~STACK () {delete(anf);}
void push(int i)
{
hilf = anf;
anf = new ELEMENT;
anf->next = hilf;
anf->dat = i;
}
int pop ()
{
int d;
hilf = anf;
if(anf->next != NULL) anf=anf->next;
d = hilf->dat;
delete hilf;
return d;
}
};
void main()
{
int i;
Stack s;
s.push(1);
s.push(2);
s.push(3);
cout | | | +----->| | | +----->| | | +-----> NULL
| | 1 | | | | 2 | | | | 3 | |
NULL | | | +-----> NULL
| | 1 | | | | 2 | | | | 3 | |
NULL |-----|--| |-----|--| |-----|--|
Bei doppelt verketteten Listen: Im letzten Element der Liste wird statt einem next-Zeiger auf NULL ein Zeiger auf das erste Element gespeichert.
Im ersten Element der Liste wird statt einem prev-Zeiger auf NULL ein Zeiger auf das letzte Element gespeichert.
/---------------------------------------------------------\\
| |
| |--|-----|--| |--|-----|--| |--|-----|--| |
\\--->| | | +----->| | | +----->| | | +-----/
| | | | | | | | | | | |
panker +--->| | 1 | | | | 2 | | | | 3 | |
| | | | | | | | | | | |
/-----+ | | || | 12 | | 17 | | | | | |
|-----| \\---|-----|---|-----|---|-----|---|-----|---/
| |
| 20 |
| |
|-----| /---|-----|---|-----|---|-----|---|-----|---\\
| +--------->| | 25 | | 27 | | 28 | | | |
|-----| \\---|-----|---|-----|---|-----|---|-----|---/
| |
| 30 |
| |
|-----| /---|-----|---|-----|---|-----|---|-----|---\\
| +--------->| | 35 | | 37 | | 38 | | 40 | |
|-----| \\---|-----|---|-----|---|-----|---|-----|---/
| |
| |
| |
|-----|
| |
\\-----/
Da es sich um einen Suchbaum (sortierte Schlüsselbäume) handelt
|
