Die verkettete Liste

1. Aufgabe

Rekursive Datentypen bilden gegenüber den statischen Datentypen wie Arrays und Strukturen das Fundament für Datenmengen, deren Umfang zur Laufzeit potentiell unendlich groß werden kann. Der bekannteste Vertreter dieser so genannten dynamischen Datenstrukturen ist die verkettete Liste. Der Name der Datenstruktur bezieht sich auf ihren internen Aufbau. Die einzelnen Listenelemente werden wie in einer Kette der Reihe nach miteinander verkettet. Pro Element der Liste ist neben den Nettodaten zusätzlich eine Zeigervariable erforderlich, um das nächste Element in der Liste zu identifizieren. Der Anwender einer verketteten Liste besitzt nur eine Adresse des ersten Listenelements, dieses wird in der Regel als root gekennzeichnet, siehe Abbildung 1.

Schematische Darstellung einer verketteten Liste mit ganzzahligen Elementen.

Abbildung 1. Schematische Darstellung einer verketteten Liste mit ganzzahligen Elementen.


Die Operationen einer verketteten Liste müssen ihrer internen Struktur Rechnung tragen. Um beispielsweise in einer Liste ein bestimmtes Element zu suchen, muss man die Liste Element für Element so lange traversieren, bis das Element gefunden wird. Diese Art des Zugriffs auf eine dynamische Datenstruktur ist natürlich nicht so laufzeitoptimal wie beispielsweise der indizierte Zugriff auf ein Array. Wir bezahlen diesen Preis für die Fähigkeit, eine unbestimmte Anzahl von Elementen elegant verwalten zu können.

Im folgenden betrachten wir die Realisierung einer verketteten Liste, die ganzzahlige Elemente aufnehmen kann. Ein einzelnes Element dieser Liste wird durch eine Instanz der Klasse ListItem gebildet:

01: class ListItem
02: {
03: friend class LinkedList;
04: 
05: friend ostream& operator<< (ostream&, ListItem&);
06: friend ostream& operator<< (ostream&, LinkedList&);
07: 
08: friend bool operator== (const LinkedList&, const LinkedList&);
09: 
10: private:
11:     int m_val; 
12:     ListItem * m_next;
13: 
14: public:
15:     // c'tor
16:     ListItem (int);
17: };
18: 
19: // c'tor
20: ListItem::ListItem (int val)
21: {
22:     m_val = val;
23:     m_next = (ListItem*) 0;
24: }
25: 
26: ostream& operator<< (ostream& os, ListItem& li)
27: {
28:     os << li.m_val;
29:     return os;
30: }

Beispiel 1. Die Klasse ListItem: Einzelnes Element einer verketteten Liste.


Zum Arbeiten mit einer verketteten Liste benötigt man im einfachsten Fall Methoden zum Einfügen, Löschen und Suchen einzelner Elemente. Wir legen die Methoden aus Tabelle 1 als Grundlage unserer Realisierung fest:

Methode

Beschreibung

Konstruktoren, Destruktor

LinkedList ();
LinkedList (const LinkedList&);
~LinkedList ();

Standardkonstruktor, Kopierkonstruktor und Destruktor.

Methode Size

int Size ();

Liefert die Anzahl der Elemente in der Liste zurück.

Methode IsEmpty

bool IsEmpty ();

Liefert true zurück, wenn die Liste leer ist, andernfalls wird false zurückgegeben.

Methode AddHead

bool AddHead (int val);

Fügt ein neues Element val am Anfang in der Liste ein.

Methode AddTail

void AddTail (int val);

Fügt ein neues Element val am Ende der Liste ein.

Methode Insert

bool Insert (int val, int pos);

Fügt ein neues Element val in der Liste an der durch pos spezifizierten Position ein. Der Index pos ist null-basiert.

Methode Concat

void Concat (const LinkedList& l);

Die durch den Parameter l spezifizierte Liste wird an das akuelle Listenobjekt angehängt (so genannte Konkatenation zweier Listen).

Methode Reverse

void Reverse ();

Die Reihenfolge der Elemente im akuellen Listenobjekt wird umgedreht.

Methode Contains

bool Contains (int val);

Sucht das spezifizierte Element val in der Liste. Ist das Element nicht in der Liste enthalten, lautet der Rückgabewert false, andernfalls wird true zurückgegeben.

Methode RemoveItemAtPosition

bool RemoveItemAtPosition (int pos);

Entfernt ein Element an der spezifizierten Position pos in der Liste. Spezifiziert pos eine ungültige Position, lautet der Rückgabewert false, andernfalls wird true zurückgegeben.

Methode RemoveItem

bool RemoveItem (int val);

Entfernt ein Element val in der Liste. Ist das Element nicht in der Liste enthalten, lautet der Rückgabewert false, andernfalls wird true zurückgegeben.

Methode RemoveAll

void RemoveAll ();

Entfernt alle in der Liste enthalten Elemente.

Tabelle 1. Methoden der Klasse LinkedList.


Neben den Methoden zählen auch eine Reihe von Operatoren zu einem gelungenen Klassendesign, um die Anwenderschnittstelle der Klasse intuitiver zu gestalten. In Tabelle 2 finden Sie eine Beschreibung aller Operatoren der Klasse LinkedList vor:

Operator

Beschreibung

+

friend LinkedList operator+ (const LinkedList& l1, const LinkedList& l2);

Konkatenation zweier verketteter Listen. Die durch das Anhängen von l2 an l1 entstehende verkettete Liste ist in einem neuem Objekt als Resultat zurückzuliefern.

+=

friend LinkedList& operator+= (LinkedList& l1, const LinkedList& l2);

Operatorenschreibweise für die Methode Concat: Das Resultat kommt im ersten Objekt l1 zu liegen.

+=

friend LinkedList& operator+= (LinkedList& l, int val);

Operatorenschreibweise für die Methode AddTail: Der durch val spezifizierte int-Parameter ist am Ende der Liste l anzuhängen.

-=

friend LinkedList& operator-= (LinkedList& l, int val);

Operatorenschreibweise für die Methode RemoveItem: Das durch val spezifizierte int-Element ist aus der Liste l zu entfernen.

==

friend bool operator== (const LinkedList& l1, const LinkedList& l2);

Test zweier verketteter Listen auf Gleichheit. Zwei verkettete Listen sind genau dann gleich, wenn sie dieselbe Länge besitzen und an jeder Position dasselbe Datenelement vorhanden ist.

==

friend bool operator!= (const LinkedList& l1, const LinkedList& l2);

Test zweier verketteter Listen auf Ungleichheit.

=

LinkedList& operator= (const LinkedList& l);

Wertzuweisung zweier verketteter Listen.

<<

ostream& operator<< (ostream&, LinkedList&);

Gibt eine verkettete Liste in der Form „[1, 2, 3]“ auf dem Ausgabestrom aus.

Tabelle 2. Operatoren der Klasse LinkedList.


Zum Testen Ihrer Realisierung finden Sie nachstehend einen Vorschlag vor.

void main ()
{
    LinkedList l;

    // test insert
    for (int i = 0; i < 5; i ++)
        l.AddHead (2*i);

    // test << operator
    cout << l << endl;

    // test insert at a specified position
    l.Insert (98, 5);
    cout << l << endl;

    // AddTail element
    l.AddTail (99);
    cout << l << endl;

    // test find
    cout << "searching number 13: " << l.Contains (13) << endl;
    cout << "searching number 98: " << l.Contains (98) << endl;

    // test remove
    l.RemoveItemAtPosition (6);
    cout << l << endl;

    l.RemoveItemAtPosition (0);
    cout << l << endl;

    // testing copy c'tor
    LinkedList l2 (l);
    cout << "l:  " << l << endl;
    cout << "l2: " << l2 << endl;

    // testing assignment operator
    l2.AddHead (50);
    l2.AddHead (51);
    l2.AddHead (52);
    cout << "l2: " << l2 << endl;

    l = l2;
    cout << "l:  " << l << endl;
    
    l.RemoveAll ();
    cout << l << endl;
}

Ausgabe:

[8,6,4,2,0] (5 elements)
[8,6,4,2,0,98] (6 elements)
[8,6,4,2,0,98,99] (7 elements)
searching number 13: 0
searching number 98: 1
[8,6,4,2,0,98] (6 elements)
[6,4,2,0,98] (5 elements)
l:  [6,4,2,0,98] (5 elements)
l2: [6,4,2,0,98] (5 elements)
l2: [52,51,50,6,4,2,0,98] (8 elements)
l:  [52,51,50,6,4,2,0,98] (8 elements)
[] (0 elements)

2. Lösung

Eine Umsetzung der Listenspezifikation aus Tabelle 1 und Tabelle 2 finden Sie in Listing 1 und Listing 2 vor. Die Klasse LinkedList ist die Realisierung der Liste, ihre einzelnen Elemente sind vom Typ ListItem:

01: class LinkedList
02: {
03: friend ostream& operator<< (ostream&, LinkedList&);
04: 
05: private:
06:     // member data
07:     ListItem * m_root;
08:     int m_count;
09: 
10: public:
11:     // c'tors and d'tor
12:     LinkedList ();
13:     LinkedList (const LinkedList&);
14:     ~LinkedList ();
15: 
16:     // public interface
17:     void AddHead (int);              // insert item at begin of list
18:     void AddTail (int);              // insert item at end of list
19:     bool Insert (int, int);          // insert item at a specified position
20:     bool RemoveItemAtPosition (int); // remove item at specified position
21:     bool RemoveItem (int);           // remove specified item
22:     void RemoveAll ();               // remove all items
23:     bool Contains (int);             // find item
24:     int  Size ();                    // retrieve length of linked list
25:     bool IsEmpty ();                 // is list empty
26:     void Concat (const LinkedList&); // concatenation of two lists
27:     void Reverse ();                 // reverse list
28: 
29:     // additional operators
30:     friend LinkedList operator+ (const LinkedList&, const LinkedList&);
31:     friend LinkedList& operator+= (LinkedList&, const LinkedList&);
32:     friend LinkedList& operator+= (LinkedList&, int);
33:     friend LinkedList& operator-= (LinkedList&, int);
34: 
35:     // comparison operators
36:     friend bool operator== (const LinkedList&, const LinkedList&);
37:     friend bool operator!= (const LinkedList&, const LinkedList&);
38: 
39:     // assignment operator
40:     LinkedList& operator= (const LinkedList&);
41: };

Beispiel 1. Einfache Realisierung einer verketteten Liste für int-Variablen: Schnittstelle.


001: #include <iostream>
002: using namespace std;
003: 
004: #include "ListItem.h"
005: #include "LinkedList.h"
006: 
007: // c'tors and d'tor
008: LinkedList::LinkedList ()
009: {
010:     m_root = (ListItem*) 0;
011:     m_count = 0;
012: }
013: 
014: LinkedList::LinkedList (const LinkedList& l)
015: {
016:     m_root = (ListItem*) 0;
017:     m_count = 0;
018: 
019:     ListItem* item = l.m_root;
020:     while (item != (ListItem*) 0)
021:     {
022:         AddTail (item -> m_val);
023:         item = item -> m_next;
024:     }
025: }
026: 
027: LinkedList::~LinkedList ()
028: {
029:     RemoveAll ();
030: }
031: 
032: // public interface
033: void LinkedList::AddHead (int val)
034: {
035:     // create a new node
036:     ListItem* node = new ListItem (val);
037: 
038:     if (m_root == (ListItem*) 0)
039:     {
040:         m_root = node;
041:     }
042:     else
043:     {
044:         node -> m_next = m_root;
045:         m_root = node;
046:     }
047: 
048:     // increment node counter
049:     m_count ++;
050: }
051: 
052: bool LinkedList::Insert (int val, int pos)
053: {
054:     // verify params
055:     if (pos < 0 || pos > m_count)
056:         return false;
057: 
058:     // create a new node
059:     ListItem* node = new ListItem (val);
060: 
061:     if (pos == 0)
062:     {
063:         node -> m_next = m_root;
064:         m_root = node;
065:     }
066:     else // i >= 1
067:     {
068:         ListItem* current = m_root;
069:         while (pos - 1 > 0)
070:         {
071:             current = current -> m_next;
072:             pos --;
073:         }
074: 
075:         node -> m_next = current -> m_next;
076:         current -> m_next = node;
077:     }
078: 
079:     // increment node counter
080:     m_count ++;
081: 
082:     return true;
083: }
084: 
085: void LinkedList::AddTail (int val)
086: {
087:     // create a new node
088:     ListItem* node = new ListItem (val);
089: 
090:     if (m_root == (ListItem*) 0)
091:     {
092:         m_root = node;
093:     }
094:     else
095:     {
096:         // search end of list
097:         ListItem* last = m_root;
098:         while (last -> m_next != (ListItem*) 0)
099:             last = last -> m_next;
100: 
101:         // append node
102:         last -> m_next = node;
103:     }
104:     
105:     // increment node counter
106:     m_count ++;
107: }
108: 
109: bool LinkedList::RemoveItemAtPosition (int pos)
110: {
111:     if (pos < 0 || pos >= m_count)
112:         return false;
113: 
114:     if (pos == 0)
115:     {
116:         // store root pointer temporary
117:         ListItem* item = m_root;
118: 
119:         // move pointer root to second element
120:         m_root = m_root -> m_next;
121: 
122:         // delete first element
123:         delete item;
124:     }
125:     else
126:     {
127:         // move temporary pointer to predecessor of element to be removed
128:         ListItem* pred = m_root;
129:         for (int i = 0; i < pos - 1; i ++)
130:             pred = pred -> m_next;
131: 
132:         // need pointer for later removal of list element
133:         ListItem* item = pred -> m_next;
134: 
135:         // link predecessor and successor of questionable element together
136:         pred -> m_next = pred -> m_next -> m_next;
137: 
138:         // now release list element
139:         delete item;
140:     }
141: 
142:     // decrement node counter
143:     m_count --;
144: 
145:     return true;
146: }
147: 
148: bool LinkedList::RemoveItem (int val)
149: {
150:     // search specified item
151:     int pos = 0;
152:     ListItem* current = m_root;
153:     while (current != (ListItem*) 0)
154:     {
155:         if (current -> m_val == val)
156:             break;
157: 
158:         pos ++;
159:         current = current -> m_next;
160:     }
161: 
162:     // element not found
163:     if (current == (ListItem*) 0)
164:         return false;
165: 
166:     RemoveItemAtPosition (pos);
167:     return true;
168: }
169: 
170: void LinkedList::RemoveAll ()
171: {
172:     ListItem* item = m_root;
173: 
174:     // delete each single element
175:     while (item != (ListItem*) 0)
176:     {
177:         // store current node pointer
178:         ListItem* current = item;
179: 
180:         // advance to next node
181:         item = item -> m_next;
182: 
183:         // delete 'current' node pointer
184:         delete current;
185:     }
186: 
187:     // reset instance data of list
188:     m_root = (ListItem*) 0;
189:     m_count = 0;
190: }
191: 
192: bool LinkedList::Contains (int val)
193: {
194:     ListItem* current = m_root;
195:     while (current != (ListItem*) 0)
196:     {
197:         if (current -> m_val == val)
198:             return true;
199: 
200:         current = current -> m_next;
201:     }
202: 
203:     // element not found
204:     return false;
205: }
206: 
207: int LinkedList::Size ()
208: {
209:     return m_count;
210: }
211: 
212: bool LinkedList::IsEmpty ()
213: {
214:     return m_count == 0;
215: }
216: 
217: // assignment operator
218: LinkedList& LinkedList::operator= (const LinkedList& l)
219: {
220:     // delete current instance data of this object
221:     RemoveAll ();
222: 
223:     // make a copy of the provided object
224:     m_root = (ListItem*) 0;
225: 
226:     ListItem* item = l.m_root;
227:     while (item != (ListItem*) 0)
228:     {
229:         AddTail (item -> m_val);
230:         item = item -> m_next;
231:     }
232: 
233:     return *this;
234: }
235: 
236: void LinkedList::Concat (const LinkedList& l)
237: {
238:     // search last item to avoid recursion
239:     ListItem* item = l.m_root;
240:     ListItem* last = (ListItem*) 0;
241: 
242:     while (item != (ListItem*) 0)
243:     {
244:         last = item;
245:         item = item -> m_next;
246:     }
247: 
248:     // append second list to current list
249:     item = l.m_root;
250:     while (item != (ListItem*) 0)
251:     {
252:         AddTail (item -> m_val);
253: 
254:         // end of original list reached
255:         if (item == last)
256:             break;
257: 
258:         // advance to next node
259:         item = item -> m_next;
260:     }
261: }
262: 
263: void LinkedList::Reverse ()
264: {
265:     // create a new root node
266:     ListItem* root = (ListItem*) 0;
267: 
268:     // traverse current list and build reverse list
269:     ListItem* item = m_root;
270:     while (item != (ListItem*) 0)
271:     {
272:         ListItem* node = new ListItem (item -> m_val);
273:         
274:         if (root == (ListItem*) 0)
275:         {
276:             root = node;
277:         }
278:         else
279:         {
280:             node -> m_next = root;
281:             root = node;
282:         }
283: 
284:         item = item -> m_next;
285:     }
286: 
287:     // release current list
288:     int count = m_count;
289:     RemoveAll ();
290: 
291:     // switch to new list
292:     m_root = root;
293:     m_count = count;
294: }
295: 
296: // additional operators
297: LinkedList operator+ (const LinkedList& l1, const LinkedList& l2)
298: {
299:     LinkedList item = l1;
300:     item.Concat (l2);
301:     return item;
302: }
303: 
304: LinkedList& operator+= (LinkedList& l1, const LinkedList& l2)
305: {
306:     l1.Concat (l2);
307:     return l1;
308: }
309: 
310: LinkedList& operator+= (LinkedList& l, int val)
311: {
312:     l.AddTail (val);
313:     return l;
314: }
315: 
316: LinkedList& operator-= (LinkedList& l, int val)
317: {
318:     l.RemoveItem (val);
319:     return l;
320: }
321: 
322: bool operator== (const LinkedList& l1, const LinkedList& l2)
323: {
324:     ListItem* item1 = l1.m_root;
325:     ListItem* item2 = l2.m_root;
326: 
327:     while (item1 != (ListItem*) 0 && item2 != (ListItem*) 0)
328:     {
329:         if (item1 -> m_val != item2 -> m_val)
330:             return false;
331: 
332:         item1 = item1 -> m_next;
333:         item2 = item2 -> m_next;
334:     }
335: 
336:     if (item1 == (ListItem*) 0 && item2 == (ListItem*) 0)
337:         return true;
338: 
339:     return false;
340: }
341: 
342: bool operator!= (const LinkedList& l1, const LinkedList& l2)
343: {
344:     return ! (l1 == l2);
345: }
346: 
347: // output operator
348: ostream& operator<< (ostream& o, LinkedList& l)
349: {
350:     ListItem* item = l.m_root;
351: 
352:     o << "[";
353:     while (item != (ListItem*) 0)
354:     {
355:         if (item != l.m_root)
356:             o << ",";
357: 
358:         // o << item -> m_val;
359:         o << *item;
360:         item = item -> m_next;
361:     }
362:     o << "] (" << l.m_count << " elements)";
363: 
364:     return o;
365: }

Beispiel 2. Einfache Realisierung einer verketteten Liste für int-Variablen: Implementierung.


Die Algorithmen aus Listing 2 erfordern viel Sorgfalt im Umgang mit Zeigern. Für das Löschen eines Elements in der Liste ist zunächst der Vorgänger des zu löschenden ListItem-Objekts zu lokalisieren. Nun kann das m_next-Element des Vorgänger-Objekts mit der Adresse des Nachfolgeobjekts des zu löschenden Objekts überschrieben werden. Wir erkennen in Abbildung 2, dass das zu löschende ListItem-Objekt nach dem Umhängen des Zeigers in der Liste nicht mehr enthalten ist – wenngleich das ListItem-Objekt im Speicher als solches noch existiert. Es ist nun die Aufgabe des delete-Operators, diesen Speicherplatz wieder freizugeben.

Das Löschen eines Listenelements (hier: ListItem-Objekt mit der Zahl 2) erfolgt durch das Umhängen einer Zeigervariablen.

Abbildung 2. Das Löschen eines Listenelements (hier: ListItem-Objekt mit der Zahl 2) erfolgt durch das Umhängen einer Zeigervariablen.


Das Einfügen eines neuen Elements in eine verkettete Liste erfolgt nach einem ähnlichen Prinzip. Es ist wiederum zunächst die Position in der Liste zu lokalisieren, an der das neue Element einzufügen ist. Nun sind, wie in Abbildung 3 gezeigt wird, zwei Zeigervariablen anzupassen, und das Element ist in der Liste eingeklinkt.

Das Einfügen eines neuen Listenelements (hier: ListItem-Objekt mit der Zahl 2) erfordert das Umhängen zweier Zeigervariablen.

Abbildung 3. Das Einfügen eines neuen Listenelements (hier: ListItem-Objekt mit der Zahl 2) erfordert das Umhängen zweier Zeigervariablen.


Eine Methode aus Listing 2 bedarf noch einer zusätzlichen Erläuterung. Die Realisierung von Concat in den Zeilen 236 bis 261 sieht auf den ersten Blick vergleichsweise umständlich aus. Warum tut es eine einfachere Implementierung, etwa in der Gestalt

void LinkedList::Concat (const LinkedList& l)
{
    // append second list to current list
    ListItem* item = l.m_root;
    while (item != (ListItem*) 0)
    {
        this -> AddTail (item -> m_val);
        item = item -> m_next;
    }
}

nicht auch? Das Problem besteht einzig und allein bei einem Aufruf dieser Methode in der Form

LinkedList l;
...
l.Concat (l);

Erkennen Sie das Problem? Beim Anhängen einer Liste an sich selbst gerät die vorgestellte Concat-Implementierung in eine Endlosschleife! Es wird zwar eine neue Liste, ausgehend von dem temporären Wurzelelement item aufgebaut. Die sukzessiven Aufrufe von AddTail am selben Listenobjekt führen aber dazu, dass dieses Objekt pro Iterationsschritt (in der while-Schleife) um ein Element länger wird und so das Ende-Kriterium niemals erreicht werden kann. In der Realisierung von Listing 2 wird deshalb vor dem Eintritt in die while-Schleife das letzte Listenelement ermittelt, um so einen zusätzlichen Wächter (guard) für das korrekte Ende der Wiederholungsschleife zu besitzen.