Die neuen bzw. abgeänderten Teile des folgenden Quelltextes erscheinen (hoffentlich) im Fettdruck.

Beachten Sie, dass die Freigabe des für die Liste allocierten Speichers implizit erfolgt. Es wird nämlich am Ende der main-Funktion der Destruktor von TsList aufgerufen, weil dort das Objekt List entfernt wird.

Zur Erinnerung:
Es soll eine Klasse TsList zur Verwaltung einer einfach verketteten Liste erstellt werden.
Diese soll folgendes zur Verfügung stellen:
einen Konstruktor, einen Destruktor sowie die Kommunikationsschnittstellen empty, append und zur Abfrage der Datenelemente getItem, optional getFirstItem, getNextItem

Includes und Definition der Datenstruktur eines Listenelementes
#include <stdio>
#include <iostream>
#include <conio>

// Einfachstes Element zur Zusammenstellung einer einfach verketteten Liste
typedef struct SsListItem
{
 int Value;
 struct SsListItem *Succ;
} TsListItem;
Deklaration der Klasse TsList
class TsList
{
 public:
  // Konstruktor
  TsList(){First = Last = NULL;}
  // Destruktor
  ~TsList();
  
  // Kommunikationsschnittstellen
  // empty liefert 1 bzw. true, wenn die Liste leer ist, ansonsten 0 bzw. false
  int empty(){return First==NULL;}
  // append hängt an das Listenende ein neues Element mit dem importierten Datenwert (int)
  int append(int);
  // getItem liefert einen Zeiger auf das per Positionsnummer angeforderte Datenelement
  // bzw. NULL, wenn dieses nicht existiert
  TsListItem *getItem(unsigned int);

 private:
  // Die Zeiger auf das erste und das letzte Listenelement
  TsListItem *First, *Last;
};
Implementationen der Member-Functions von TsList

TsList::~TsList()
{
 TsListItem *Temp;
 while (First)
 {
  Temp = First->Succ;
  delete First;
  First = Temp;
 }
}

int TsList::append(int Value)
{
 TsListItem *Temp = new TsListItem;  // Neues Element anlegen
 if (Temp)               // Steht Speicherplatz zur Verfügung?
 {
  Temp->Value = Value;   // Wert zuweisen
  Temp->Succ = NULL;     // Terminierung mit dem NULL-Zeiger
  if (empty()) First = Last = Temp;
  else
  {
   Last->Succ = Temp;
   Last = Temp;
  }
  return 1;
 }
 else return 0;
}

TsListItem *TsList::getItem(unsigned int n)
{
 if (empty()) return NULL;
 TsListItem *Temp = First;
 unsigned int i = 0;
 while (Temp && (i++<n))
  Temp = Temp->Succ;
 return Temp;
}
Die Hauptfunktion
int main()
{
 int Value, oK;
 TsList List;
 cout << "Eingegebene Ganzzahlen werden in einer einfach verketteten Liste verwaltet."
  << "\n\nGeben Sie Ganzzahlen ein und schliessen Sie diese mit einer 0 ab."
  << endl;
 // Eingabe der Ganzzahlenfolge
 do
 {
  cin >> Value;
  if (Value) oK = List.append(Value);
 } while (Value && oK);
 cout << "\nAusgabe der eingegebenen Ganzzahlen:" << endl;
 // Ausgabe der Ganzzahlenfolge
 unsigned int i = 0;
 TsListItem *Current;
 do
 {
  Current = List.getItem(i++);
  if (Current) printf("%8i",Current->Value);
 } while (Current);

 getch();
 return 0;
}

Die Performanceschwäche im Durchlaufen aller Listenelemente (main-Funktion) liegt auf der Hand. Mit List.getItem(i++) wird ein Listenelementezeiger an der i-ten Stelle geholt. Dabei wird in TsListItem* TsList::getItem(unsigned int n) immer vom Anfang der Liste ausgehend der n-te Elementezeiger geholt.

Deutlich besser ist ein Verfahren, in welchem zuerst der erste Elementezeiger und dann sukzessive alle nachfolgenden Elementezeiger geholt werden. Dies wird z.B. möglich durch zwei weitere Elementefunktionen TsListItem* TsList::getFirstItem() und TsListItem* TsList::getNextItem().

Implementation und Anwendung können Sie auf der nächsten Seite nachlesen.