So schön die Klasse 'CArray' auch ist, sie hat einen großen Nachteil. Jede Funktion, die irgendwie die Größe des Arrays ändert, muss im Prinzip einen ganz neuen Array erstellen und danach Element für Element kopieren. Selbst wenn nur ein Element hinzugefügt wird hat dies die Erstellung eines ganz neuen Arrays zur Folge. Sofern kleine Datentypen (wie 'int') verwendet werden, ist dies nicht unbedingt ein Problem, aber sobald speicherintensive Datentypen benutzt werden, kann es ganz schnell dazu führen, dass das ewige Reservieren, Freigeben und Kopieren erheblich Zeit in Anspruch nimmt und zeitweilig ziemlich viel Speicher benötigt wird, da viele Elemente mehrfach gespeichert sind. Aus diesem Grunde ist es manchmal sinnvoll eine "verkettete Liste" einem dynamischen Array à la 'CArray' vorzuziehen. Eine "verkettete Liste" reserviert wie ein dynamischer Array den Speicher für die Elmente dynamisch. Allerdings besteht zwischen beiden genau an dieser Stelle ein großer Unterschied: Ein dynamischer Array reserviert immer soviel Speicher, dass alle Elemente, die dieser aufnehmen soll, hereinpassen. Diese werden dann alle hintereinander in dem reservierten Speicher hinterlegt. Eine verkettete Liste reserviert für jedes Element hingegen eigenen Speicher. Soll also beispielsweise ein Element entfernt werden, dann brauch nur der Speicher für dieses Element freigegeben werden. Andere Elemente werden von dieser Freigabe nicht betroffen. Die Elemente können im Speicher tatsächlich willkürlich angeordnet sein. Zwei Elemente, die sich in ihrem Index nur um eins unterscheiden, müssen im Speicher nicht unbedingt genau hintereinander abgelegt sein. Dies wiederum ermöglicht es auf ganz einfache Weise zwei Elemente zu vertauschen. Nun bleibt natürlich die Frage offen, wie man jetzt auf die einzelnen Elemente zugreift, wenn diese irgendwo gespeichert sind. Klar ist, dass zu jedem Element ein Zeiger existiert, der irgendwo gespeichert ist. Es ist nun aber nicht so, dass bei der Erstellung eines Elements einfach ein Zeiger auf dieses Element in einem dynamischen Array gespeichert wird. Stattdessen wird jedes Element zusammen mit zwei Zeigern gespeichert. Der eine Zeiger zeigt auf das vorherige, der zweite auf das nächste Element. In diesem Fall spricht man von einer "zweifach-verketteten Liste". Die Klasse speichert dann zumindest einen Zeiger, der dann nämlich auf das erste Element zeigt. In diesem Fall werde ich aber zunächst zwei Zeiger verwenden, einer wird dann auf das erste und der andere auf das letzte Element zeigen. Ziel dieser LEktion soll es sein, eine verkettete Liste erstellt zu haben, die die gleichen öffentlichen Funktionen wie 'CArray' besitzt und somit genauso verwendet werden kann.
Die Klasse wird im folgenden mit 'CLinkedList' bezeichnet. Genau wie 'CArray' ist auch sie eine Vorlagenklasse. Innerhalb der Klasse soll eine Struktur namens 'tagLISTENTRY' deklariert werden, die alle Informationen über ein Element besitzt (also die eigentlichen Daten und die zwei Zeiger auf das vorherige und auf das nächste Element). Jedes Mal wenn also ein Element hinzugefügt werden soll, dann wird eine Instanz dieser inneren Struktur erstellt anschließend mit den Daten gefüllt und schließlich in die Liste eingereiht. So könnte die Klasse 'CLinkedList' bis auf weiteres aussehen:
template <typename T>
class CLinkedList
{
private:
struct tagLISTELEMENT
{
T Data;
tagLISTELEMENT *pLast;
tagLISTELEMENT *pNext;
}*m_pFirst, *m_pLast;
int m_Length;
public:
//Konstruktor
CLinkedList(int Length = 0) : m_pFirst(0), m_pLast(0), m_Length(0)
{
}
//Kopierkonstruktor
CLinkedList(const CLinkedList& list) : m_pFirst(0), m_pLast(0), m_Length(0)
{
}
//Länge des Arrays
int GetLength(void) const {return m_Length;}
//Destruktor
~CLinkedList(void)
{
}
//Operator '='
CLinkedList<T>& operator=(const CLinkedList<T>& list)
{
return *this;
}
};
Bisher hat die Klasse nur drei eigene Member ('m_pFirst', 'm_pLast' und 'm_Length') aber noch keine wirkliche Funktionalität. Bevor wir der Klasse Funktionalität verleihen, sollten zunächst einige interne Funktionen deklariert werden, um Standardaufgaben innerhalb der Klasse ausführen zu können. Dazu gehört zuallererst eine Funktion '_InsertNewElement', die ein Element erstellt und in die Liste einreiht. Dazu wird neben den Daten angegeben, vor oder nach welchem Element dieses eingefügt werden soll. Die Implementierung könnte wie folgt aussehen:
template <typename T>
bool CLinkedList<T>::_InsertNewElement(const T* pData, tagLISTELEMENT *pElement,
bool bBefore)
{
//Element muss gültig sein
if (!pElement) return false;
//Die beiden Elemente, zwischen denen das neue eingefügt werden soll
tagLISTELEMENT *pLast, *pNext;
if (bBefore)
{
pNext = pElement;
pLast = pElement->pLast;
}
else
{
pNext = pElement->pNext;
pLast = pElement;
}
//Neues Element erstellen
tagLISTELEMENT *pNewElement = new tagLISTELEMENT;
if (!pNewElement) return false;
//Element initialisieren und in der Liste einreihen
if (pData) pNewElement->Data = *pData;
//zunächst eigene Zeiger initialisieren
pNewElement->pNext = pNext;
pNewElement->pLast = pLast;
//Zeiger von 'pNext' und 'pLast' anpassen
if (pNext) pNext->pLast = pNewElement;
if (pLast) pLast->pNext = pNewElement;
//Ist 'pNewElement' das erste Element -> 'm_pFirst' anpassen
if (!pLast) m_pFirst = pNewElement;
//Ist 'pNewElement' das letzte Element -> 'm_pLast' anpassen
if (!pNext) m_pLast = pNewElement;
//Größe anpassen
m_Length++;
return true;
}
Anhand des Parameters 'bBefore' wird zunächst bestimmt zwischen welchen beiden Elementen das neue nun eingereiht werden soll. Dazu werden die Zeiger 'pLast' und 'pNext' deklariert und abhängig von 'bBefore' initialisiert. Anschließend wird das neue Element erstellt und mit den übergebenen Daten ('pData') initialisiert (sofern überhaupt Daten zum initialisieren übergeben werden). Anschließend werden die internen Zeiger gesetzt. Dann werden die Zeiger 'pLast' und 'pNext' angepasst. So ist nun das vorherige Element von 'pNext' und umgekehrt das nächste Element von 'pLast' das neue Element 'pNewElement'. Schließlich wird noch überprüft, ob entweder 'pLast' oder 'pNext' nicht auf '0' gesetzt sind. Sollte dies der Fall sein, dann ist entweder 'pNewElement' das erste Element (im Falle 'pLast: 0') oder aber das letzte Element (im Falle 'pNext: 0') innerhalb der Liste. In diesem Fall muss entweder die Membervariable 'm_pFirst' oder aber die Membervariable 'm_pLast' angepasst werden. Zum Schluss wird noch die Arraylänge um eins erhöht. Da das Ermitteln eines Elements bei verketteten Listen nicht ganz so einfach ist, sollte noch eine interne Methode (namens '_GetListElement') implementiert werden, welche den 'tagLISTELEMENT'-Zeiger zu einem angegebenen Index ermittelt. Die Implementierung könnte wie folgt aussehen:
template <typename T>
tagLISTELEMENT* CLinkedList<T>::_GetListElement(int Index)
{
//Index überprüfen
if (Index < 0) Index = 0;
if (Index >= m_Length) Index = m_Length - 1;
//Zeiger auf gegenwärtiges Element
tagLISTELEMENT* pElement = m_pFirst;
//Von Element zu Element durch die Liste gehen
for (int iPos = 0; iPos < Index; iPos++)
{
if (!pElement) return 0;
pElement = pElement->pNext;
}
//Zeiger zurückgeben
return pElement;
}
Allerdings ist dies nicht unbedingt effizient. Angenommen es soll das letzte Element einer Liste ermittelt werden. In diesem Falle müssten alle Elemente durchlaufen werden, bis das richtiger ermittelt werden konnte. Am besten sollte zunächst überprüft werden, ob das gesuchte Element näher am ersten oder näher am letzten Element liegt. Im ersteren Falle wäre obige Implementierung noch korrekt. Im zweiten Falle sollte die Liste aber eher von hinten nach vorne durchsucht werden. Folgende Implementierung wäre also geeigneter:
template <typename T>
CLinkedList<T>::tagLISTELEMENT* CLinkedList<T>::_GetListElement(int Index)
{
//Index überprüfen
if (Index < 0) Index = 0;
if (Index >= m_Length) Index = m_Length - 1;
if (Index <= 0) return 0;
//von vorne nach hinten, oder von hinten nach vorne durchsuchen
bool bLowHigh = true;
if ((m_Length - 1 - Index) < Index) bLowHigh = false;
//Zeiger auf gegenwärtiges Element
tagLISTELEMENT* pElement = 0;
//von vorne nach hinten durchlaufen?
if (bLowHigh)
{
//Zeiger setzen
pElement = m_pFirst;
//Von Element zu Element durch die Liste gehen
for (int iPos = 0; iPos < Index; iPos++)
{
if (!pElement) return 0;
pElement = pElement->pNext;
}
}
else
{
//Zeiger setzen
pElement = m_pLast;
//Von Element zu Element durch die Liste gehen
for (int iPos = m_Length - 1; iPos > Index; iPos--)
{
if (!pElement) return 0;
pElement = pElement->pLast;
}
}
//Zeiger zurückgeben
return pElement;
}
Nun ist die Funktion durchaus effizienter. An geeigneter Stelle soll sie allerdings noch einmal überarbeitet werden. Zunächst reicht diese Variante aber aus.
Nun lässt sich zwar innerhalb der Klasse ein Element einfügen, aber bisher immer noch keine fertige Liste erstellen, geschweige denn erweitern.
Zuerst werde ich hier eine Methode zum Entfernen von Elementen implementieren, da diese dann auch zum Löschen des gesamten Arrays verwendet werden kann. Wie bereits bei der Klasse 'CArray' soll die Funktion auch hier 'Remove' heißen und auf gleiche Weise funktionieren. Die Implementierung könnte wie folgt aussehen:
//Methode zu Entfernen von Elementen
template <typename T>
bool CLinkedList<T>::Remove(int Start, int End)
{
//Im Falle eines leeren Arrays kein Entfernen möglich
if (m_Length == 0) return false;
//Indices überprüfen
if (Start > End)
{
int Index = Start;
Start = End;
End = Index;
}
if (Start < 0) Start = 0;
if (Start >= m_Length) Start = m_Length - 1;
if (End < 0) End = 0;
if (End >= m_Length) End = m_Length - 1;
//Das erste und das letzte Element, das gelöscht werden soll, ermitteln
tagLISTELEMENT *pLast, *pFirst;
pFirst = _GetListElement(Start);
pLast = _GetListElement(End);
//Bei ungültigen Ausgaben die Grenzen verwenden
if (!pFirst) pFirst = m_pFirst;
if (!pLast) pLast = m_pLast;
//Den zu löschenden Bereich zunächst aus der Liste entfernen
if (pFirst->pLast) pFirst->pLast->pNext = pLast->pNext;
if (pLast->pNext) pLast->pNext->pLast = pFirst->pLast;
//evtl. die Grenzen anpassen, wenn das erste oder das letzte Element entfernt wurde
if (!pFirst->pLast) m_pFirst = pLast->pNext;
if (!pLast->pNext) m_pLast = pFirst->pLast;
//Grenzen des zu löschenden Bereichs markieren
pFirst->pLast = pLast->pNext = 0;
//Element für Element freigeben
tagLISTELEMENT *pElement = pFirst, *pNext = pFirst->pNext;
while (pElement)
{
//Element freigeben
delete pElement;
m_Length--;
//Nächstes Element ermitteln
pElement = pNext;
if (pElement) pNext = pElement->pNext;
}
return true;
}
Zunächst werden genau wie bei der Methode von 'CArray' die Indices angepasst. Anschließend wird das erste und das letzte zu löschende Objekt ermittelt und die jeweilige Adresse in den Zeigern 'pFirst' und 'pLast' festgehalten. Anschließend werden alle zu löschenden Elemente aus der Liste ausgegliedert. Dazu muss das Element vor 'pFirst' als das vorige Element von 'pLast->pNext' ausgegeben werden. Das Element hinter 'pLast' muss dazu im Gegenzug als das nächste Element von 'pFirst->pLast' ausgegeben werden. Anschließend wird der zu löschende Bereich gänzlich von der verketteten Liste getrennt, in dem man die entsprechenden internen Zeiger von 'pFirst' und 'pLast' zurücksetzt und ihnen somit jeden weiteren Zugriff auf die verkettete Liste versperrt. Anschließend werden noch mögliche Korrekturen an den Membervariablen 'm_pFirst' und 'm_pLast' vorgenommen, wenn das erste oder das letzte Element gelöscht werden soll. Anschließend wird die zu löschende Liste durchlaufen und Element für Element freigegeben, bis der Zeiger 'pElement' auf das jeweilige Element den Wert '0' annimmt. Außerdem wird nach jedem Löschvorgang die Längenangabe um eins verringert. Um die Methode nun noch zu komplettieren, werden nun noch die beiden Überladungen durchgeführt, die bereits schon bei der Klasse 'CArray' existierten. Diese Implementierungen werden später (ebenfalls wie bei 'CArray') innerhalb der Klassendeklaration vorgenommen. Hier nun die Überladungen:
//Methode zu Entfernen eines Elements
template <typename T>
bool CLinkedList<T>::Remove(int Index)
{
return Remove(Index, Index);
}
//Methode zum Löschen aller Elemente
template <typename T>
bool CLinkedList<T>::Remove(void)
{
return Remove(0, m_Length - 1);
}
Schließlich sollte nun noch der Destruktor implementiert werden (Auch diese Implementierung wird nachher innerhalb der Klasse stattfinden):
//Destruktor
template <typename T>
CLinkedList<T>::~CLinkedList(void)
{
Remove();
}
Wie bereits bei der Klasse 'CArray' soll auch hier die entsprechende Funktion 'Create' heißen. Auch hier müssen zunächst alle Daten freigegeben werden, bevor neue erstellt werden können. Die Implementierung könnte in etwa so aussehen:
template <typename T>
bool CLinkedList<T>::Create(int Length)
{
//Zunächst alle Daten freigeben
Remove();
//Längenangabe überprüfen
if (Length < 0) Length = 0;
if (!Length) return true;
//Erstes Element erstellen
m_pFirst = m_pLast = new tagLISTELEMENT;
if (!m_pFirst) return false;
else m_Length = 1;
//interne Zeiger anpassen
m_pFirst->pLast = m_pFirst->pNext = 0;
//restliche Elemente hinzufügen
while (m_Length != Length)
{
if (!_InsertNewElement(0, m_pLast, false))
{
return false;
}
}
return true;
}
Hier wird zunächst die Methode 'Remove' aufgerufen, um alle Daten freizugeben. Anschließend wird die Längenangabe angepasst und dann wird schließlich das erste Element erstellt und initialisiert. Danach wird die Längenangabe auf eins gesetzt und schließlich wird solange eine weiteres Element hinzugefügt bis entweder ein Fehler auftritt oder aber die gewünschte Länge erreicht ist. Nun kann noch der Konstruktor angepasst werden. Da dieser auch innerhalb der Klasse implementiert wird zeige ich hier nun die gegenwärtige Klassendeklaration:
template <typename T>
class CLinkedList
{
private:
struct tagLISTELEMENT
{
T Data;
tagLISTELEMENT *pLast;
tagLISTELEMENT *pNext;
}*m_pFirst, *m_pLast;
int m_Length;
//Element einfügen
bool _InsertNewElement(const T*, tagLISTELEMENT *, bool);
//Element (tagLISTELEMENT) ermitteln
tagLISTELEMENT* _GetListElement(int);
public:
//Liste (neu) erstellen
bool Create(int);
//Methoden zu Entfernen von Elementen
bool Remove(int, int);
bool Remove(int Index) {return Remove(Index, Index);}
bool Remove(void) {return Remove(0, m_Length - 1);}
//Konstruktor
CLinkedList(int Length = 0) : m_pFirst(0), m_pLast(0), m_Length(0)
{Create(Length);}
//Kopierkonstruktor
CLinkedList(const CLinkedList& list) : m_pFirst(0), m_pLast(0), m_Length(0)
{
}
//Länge des Arrays
int GetLength(void) const {return m_Length;}
//Destruktor
~CLinkedList(void) {Remove();}
//Operator '='
CLinkedList<T>& operator=(const CLinkedList<T>& list)
{
return *this;
}
};
Nun fehlen noch die vollständigen Implementierungen der Methoden 'DataAt', 'Insert', 'Add', der Operatoren '=', '[]' und '+=' und die Implementierung des Kopierkonstrukors.
Diese Methode soll wiederum 'DataAt' heißen. Ihre Implementierung und die des Operators '[]' lautet dementsprechend wie folgt:
//Wert setzen und ermitteln
template <typename T>
T& CLinkedList<T>::DataAt(int Index)
{
return _GetListElement(Index)->Data;
}
//Operator '[]'
template <typename T>
T& CLinkedList<T>::operator[] (int Index)
{
return _GetListElement(Index)->Data;
}
Auch diese beiden Implementierungen werden nachher in die Klassendeklaration verschoben. Anzumerken wäre an dieser Stelle noch, dass die Funktion und der Operator mit Vorsicht zu genießen sind, da die von beiden aufgerufene Methode '_GetListElement' auch einen ungültigen Zeiger zurückliefern könnte. Dies geschieht im Prinzip aber nur, wenn die Länge der Liste auf '0' gesetzt ist und ein Aufruf dieser Methode und dieses Operators überhaupt nicht sinnvoll ist.
Nun endlich sollen diese entscheidenden Elemente implementiert werden. Allerdings soll auch hier zuvor eine interne Methode '_Copy' implementiert werden, die dann sowohl vom Kopierkonstruktor als auch vom Zuweisungsoperator verwendet wird. Ihre Implementierung sähe dann wie folgt aus:
//Kopiermethode
template <typename T>
void CLinkedList<T>::_Copy(const CLinkedList<T>& list)
{
//Zunächst prüfen ob die Instanz sich selbst kopieren soll
if (&list == this) return;
//Liste neu erstellen
if (!Create(list.m_Length)) return;
//Kopie überhaupt notwendig
if (!list.m_Length) return;
//Positionszeiger
tagLISTELEMENT *pTar = m_pFirst, *pSrc = list.m_pFirst;
//Element für Element kopieren
while (pTar && pSrc)
{
//Daten kopieren
pTar->Data = pSrc->Data;
//Positionszeiger anpassen
pTar = pTar->pNext;
pSrc = pSrc->pNext;
}
}
Hier wird zunächst (nach einer Überprüfung) eine ausreichend große Liste erstellt. Anschließend werden die aufrufende und die übergebene Liste Element für Element durchlaufen, bis das Ende erreicht wird. Während dieses Schleifendurchlaufs, werden dabei die Daten kopiert. Es wurden hier nicht die Methoden 'DataAt', '_GetListElement' oder der Operator '[]' verwendet, da diese nicht effizient genug sind, denn jedes Mal, wenn sie ein Element ermitteln, die Liste von neuem durchlaufen werden muss. Nun können auch Kopierkonstruktor und Zuweisungsoperator (vollständig) implementiert werden:
//Kopierkonstruktor
template <typename T>
CLinkedList<T>::CLinkedList(const CLinkedList<T>& list) : m_pFirst(0), m_pLast(0), m_Length(0)
{
_Copy(list);
}
//Zuweisungsoperator
template <typename T>
CLinkedList<T>& CLinkedList<T>::operator = (const CLinkedList<T>& list)
{
_Copy(list);
return *this;
}
Auch die Implementierung des Kopierkonstruktors wird anschließend in die Klassendeklaration verbannt. Die Klasse sieht gegenwärtig, wie folgt aus:
template <typename T>
class CLinkedList
{
private:
struct tagLISTELEMENT
{
T Data;
tagLISTELEMENT *pLast;
tagLISTELEMENT *pNext;
}*m_pFirst, *m_pLast;
int m_Length;
//Element einfügen
bool _InsertNewElement(const T*, tagLISTELEMENT *, bool);
//Element (tagLISTELEMENT) ermitteln
tagLISTELEMENT* _GetListElement(int);
//Kopiermethode
void _Copy(const CLinkedList<T>&);
public:
//Liste (neu) erstellen
bool Create(int);
//Methoden zu Entfernen von Elementen
bool Remove(int, int);
bool Remove(int Index) {return Remove(Index, Index);}
bool Remove(void) {return Remove(0, m_Length - 1);}
//Konstruktor
CLinkedList(int Length = 0) : m_pFirst(0), m_pLast(0), m_Length(0)
{Create(Length);}
//Kopierkonstruktor
CLinkedList(const CLinkedList& list) : m_pFirst(0), m_pLast(0), m_Length(0)
{_Copy(list);}
//Länge des Arrays
int GetLength(void) const {return m_Length;}
//Destruktor
~CLinkedList(void) {Remove();}
//Wert setzen und ermitteln
T& DataAt(int Index)
{return _GetListElement(Index)->Data;}
//Operator '='
CLinkedList<T>& operator = (const CLinkedList<T>&);
//Operator '[]'
T& operator [] (int Index)
{return _GetListElement(Index)->Data;}
};
Nun fehlen tatsächlich nur noch die Funktionen zum Ein- und Anfügen und der Operator '+='.
Die Methode 'Insert', die das Einfügen einer Liste unterstützen soll, könnte in der Implementierung wie folgt aussehen:
//Methode zum Einfügen mehrerer Elemente
template <typename T>
bool CLinkedList<T>::Insert(const CLinkedList<T>& list, int Index)
{
//Die Liste soll sich nicht in sich selber einfügen können
if (&list == this) return false;
//Index anpassen
if (Index < 0) Index = 0;
if (Index > m_Length) Index = m_Length;
//Elemente bestimmen zwischen denen eingefügt werden soll
tagLISTELEMENT *pFirst, *pSecond;
if (Index == 0) //vorne anfügen
{
pFirst = 0;
pSecond = m_pFirst;
}
else if (Index == m_Length) //hinten anfügen
{
pFirst = m_pLast;
pSecond = 0;
}
else //mittendrin einfügen
{
pSecond = _GetListElement(Index);
if (!pSecond) return false;
pFirst = pSecond->pLast;
}
//Zunächst eine Kopie der übergebenden Liste erstellen
CLinkedList<T> tmp = list;
//Member der temporären Liste entwenden
tagLISTELEMENT *pFirstIns, *pLastIns;
pFirstIns = tmp.m_pFirst; tmp.m_pFirst = 0;
pLastIns = tmp.m_pLast; tmp.m_pLast = 0;
int InsLength = tmp.m_Length; tmp.m_Length = 0;
//Einfügen notwendig?
if (!InsLength) return false;
//Elemente einfügen
if (!pFirst && !pSecond)
{
m_pFirst = pFirstIns;
m_pLast = pLastIns;
}
else if (!pFirst)
{
pLastIns->pNext = m_pFirst;
m_pFirst->pLast = pLastIns;
m_pFirst = pFirstIns;
}
else if (!pSecond)
{
pFirstIns->pLast = m_pLast;
m_pLast->pNext = pFirstIns;
m_pLast = pLastIns;
}
else
{
pFirst->pNext = pFirstIns;
pFirstIns->pLast = pFirst;
pSecond->pLast = pLastIns;
pLastIns->pNext = pSecond;
}
//Länge aktualisieren
m_Length += InsLength;
return true;
}
Nach einigen Überprüfungen werden hier die Zeiger 'pFirst' und 'pSecond' deklariert, die auf die Elemente zeigen, zwischen denen die übergebene Liste 'list' eingefügt werden soll. 'pFirst' wird auf '0' gesetzt, wenn die Liste vorne angefügt wird. 'pSecond' wird auf '0' gesetzt, wenn die Liste hinten angefügt werden soll. Beide Zeiger sind auf '0' gesetzt, wenn die aufrufende Instanz bisher keine Elemente besitzt. (In diesem Falle wird nichts weiter als eine Kopie erstellt.) Als nächstes wird dann eine neue Instanz ('tmp') als Kopie der übergebenen erstellt. Anschließend werden die Member dieser Instanz entwendet und stehen anschließend nur noch der Funktion nicht aber mehr der Instanz zur Verfügung. Mit der Erstellung einer neuen Instanz erspart man sich einen manuellen Kopiervorgang. Auf diese Weise kann man indirekt die Methode '_Copy' nutzen. Anschließend wird die kopierte Liste einfach in die bereits existierende eingehängt und die Länge wird angepasst. Dabei hängt es von den Zeigern 'pFirst' und 'pSecond' ab, ob die Liste einfach nur kopiert, hinten oder vorne angehängt oder aber mittendrin eingefügt wird. Das Einhängen im letzten Fall läuft genauso ab, wie in allen vorigen Methoden und bedarf eigentlich keiner weiteren Erklärung. In den anderen Fällen muss aber noch darauf geachtet werden, dass die Membervariablen ('m_pFirst' und 'm_pLast') angepasst werden. Nun kann die Methode 'Insert' noch einmal überladen, die Methode 'Add' und die Operatoren '+=' und '+' implementiert werden:
//Methode zu Einfügen eines Elements
template <typename T>
bool CLinkedList<T>::Insert(const T& el, int Index)
{
//Liste aus dem übergebenen Element erstellen
CLinkedList<T> list(1);
list[0] = el;
//Element einfügen
return Insert(list, Index);
}
//Methode zum Anfügen einer Liste
template <typename T>
bool CLinkedList<T>::Add(const CLinkedList<T>& list)
{
return Insert(list, m_Length);
}
//Methode zum Anfügen eines Elements
template <typename T>
bool CLinkedList<T>::Add(const T& el)
{
return Insert(el, m_Length);
}
//Operator '+=' zum Anfügen einer Liste
template <typename T>
CLinkedList<T>& CLinkedList<T>::operator += (const CLinkedList<T>& arr)
{
Insert(arr, m_Length);
return *this;
}
//Operator '+=' zum Anfügen eines Elements
template <typename T>
CLinkedList<T>& CLinkedList<T>::operator += (const T& el)
{
Insert(el, m_Length);
return *this;
}
//Operator '+' zum Anfügen einer Liste
template <typename T>
CLinkedList<T> CLinkedList<T>::operator + (const CLinkedList<T>& list) const
{
//Kopie der Instanz erstellen und übergebene Liste anfügen
CLinkedList<T> listrtn = *this;
listrtn.Insert(list, listrtn.m_Length);
return listrtn;
}
//Operator '+' zum Anfügen eines Elements
template <typename T>
CLinkedList<T> CLinkedList<T>::operator + (const T& el) const
{
//Kopie der Instanz erstellen und übergebenes Element anfügen
CLinkedList<T> listrtn = *this;
listrtn.Insert(el, listrtn.m_Length);
return listrtn;
}
Werden nun beide Implementierungen der Funktion 'Add' in die Klassendeklaration verschoben, dann sieht die gesamte Deklaration wie folgt aus:
template <typename T>
class CLinkedList
{
private:
struct tagLISTELEMENT
{
T Data;
tagLISTELEMENT *pLast;
tagLISTELEMENT *pNext;
}*m_pFirst, *m_pLast;
int m_Length;
//Element einfügen
bool _InsertNewElement(const T*, tagLISTELEMENT *, bool);
//Element (tagLISTELEMENT) ermitteln
tagLISTELEMENT* _GetListElement(int);
//Kopiermethode
void _Copy(const CLinkedList<T>&);
public:
//Liste (neu) erstellen
bool Create(int);
//Methoden zum Einfügen
bool Insert(const CLinkedList<T>&, int);
bool Insert(const T&, int);
//Methoden zum Anfügen
bool Add(const CLinkedList<T>& list) {return Insert(list, m_Length);}
bool Add(const T& el) {return Insert(el, m_Length);}
//Operatoren zum Anfügen
CLinkedList<T>& operator += (const CLinkedList<T>&);
CLinkedList<T>& operator += (const T&);
CLinkedList<T> operator + (const CLinkedList<T>&) const;
CLinkedList<T> operator + (const T&) const;
//Methoden zu Entfernen von Elementen
bool Remove(int, int);
bool Remove(int Index) {return Remove(Index, Index);}
bool Remove(void) {return Remove(0, m_Length - 1);}
//Konstruktor
CLinkedList(int Length = 0) : m_pFirst(0), m_pLast(0), m_Length(0)
{Create(Length);}
//Kopierkonstruktor
CLinkedList(const CLinkedList& list) : m_pFirst(0), m_pLast(0), m_Length(0)
{_Copy(list);}
//Länge des Arrays
int GetLength(void) const {return m_Length;}
//Destruktor
~CLinkedList(void) {Remove();}
//Wert setzen und ermitteln
T& DataAt(int Index)
{return _GetListElement(Index)->Data;}
//Operator '='
CLinkedList<T>& operator = (const CLinkedList<T>&);
//Operator '[]'
T& operator [] (int Index)
{return _GetListElement(Index)->Data;}
};
Nun ist die Klasse im Prinzip genauso, wie wir sie haben wollten. Alle Methoden, die wir aus der Klasse 'CArray' kennen sind auch hier implementiert. Beide Klassen lassen sich demnach genau gleich verwenden.
Der große Nachteil dieser Klasse gegenüber der Klasse 'CArray' ist die Methode 'DataAt' bzw. '_GetListElement' die ja von 'DataAt' aufgerufen wird. Während man bei 'CArray' sofort Zugriff auf ein Element erhält, muss dass Element bei 'CLinkedList' erst einmal gesucht werden. Darum kommt man zwar auch nicht drum herum, wenn man die Vorteile der verketteten Liste weiterhin behalten möchte. Allerdings wäre es wünschenswert, wenn man die Suche beschleunigen könnte. Wenn man mehrmals hintereinander eine Element ermittelt, dann liegen diese Elemente meist dicht zusammen. So könnte man eine weiteren Zeiger namens 'm_pCurrent' als Membervariable einfügen, welcher immer auf den zuletzt gewählten Listeneintrag zeigt. Zu diesem Zweck sollte die Struktur 'tagLISTELEMENT' um das Feld 'Index' erweitert werden, in dem zu jedem Element ein Index gespeichert wreden kann. Dieses Feld sollte standardmäßig auf '-1' gesetzt werden und nur durch die Zeiger 'm_pCurrent', 'm_pFirst' und 'm_pLast' mit anderen Werten belegt werden. Die Deklaration der Klasse muss zunächst wie folgt abgeändert werden:
template <typename T>
class CLinkedList
{
private:
struct tagLISTELEMENT
{
T Data;
tagLISTELEMENT *pLast;
tagLISTELEMENT *pNext;
int Index;
}*m_pFirst, *m_pLast, *m_pCurrent;
int m_Length;
/* --- Deklaration und Implementierung der Member ---
...
*/
//Konstruktor
CLinkedList(int Length = 0) : m_pFirst(0), m_pLast(0), m_Length(0), m_pCurrent(0)
{Create(Length);}
//Kopierkonstruktor
CLinkedList(const CLinkedList& list) : m_pFirst(0), m_pLast(0), m_Length(0), m_pCurrent(0)
{_Copy(list);}
/* --- Deklaration und Implementierung der Member ---
...
*/
};Nun sollten alle Methoden berändert werden, welche neue Elemente erstellen, Zeiger verändern, oder aber einfach Zeiger anderer Instanzen übernehmen:
1.) Die Methode '_InsertNewElement':
//Element einfügen
template <typename T>
bool CLinkedList<T>::_InsertNewElement(const T* pData, tagLISTELEMENT *pElement,
bool bBefore)
{
//Element muss gültig sein
if (!pElement) return false;
//Die beiden Elemente, zwischen denen das neue eingefügt werden soll
tagLISTELEMENT *pLast, *pNext;
if (bBefore)
{
pNext = pElement;
pLast = pElement->pLast;
}
else
{
pNext = pElement->pNext;
pLast = pElement;
}
//Neues Element erstellen
tagLISTELEMENT *pNewElement = new tagLISTELEMENT;
if (!pNewElement) return false;
//Element initialisieren und in der Liste einreihen
if (pData) pNewElement->Data = *pData;
pNewElement->Index = -1; //Änderung
//zunächst eigene Zeiger initialisieren
pNewElement->pNext = pNext;
pNewElement->pLast = pLast;
//Zeiger von 'pNext' und 'pLast' anpassen
if (pNext) pNext->pLast = pNewElement;
if (pLast) pLast->pNext = pNewElement;
//Ist 'pNewElement' das erste Element -> 'm_pFirst' anpassen
if (!pLast) //Änderung...
{
m_pFirst->Index = -1;
m_pFirst = pNewElement;
}
//Ist 'pNewElement' das letzte Element -> 'm_pLast' anpassen
if (!pNext) //Änderung...
{
m_pLast->Index = -1;
m_pLast = pNewElement;
}
//'m_pCurrent' ungültig //Änderung...
if (m_pCurrent)
{
m_pCurrent->Index = -1;
m_pCurrent = m_pFirst;
}
//Größe anpassen
m_Length++;
//Indices anpassen
m_pLast->Index = m_Length - 1; //Änderung...
m_pFirst->Index = 0;
return true;
}2.) Die Methode 'Create':
//Methode zum Erstellen
template <typename T>
bool CLinkedList<T>::Create(int Length)
{
//Zunächst alle Daten freigeben
Remove();
//Längenangabe überprüfen
if (Length < 0) Length = 0;
if (!Length) return true;
//Erstes Element erstellen
m_pFirst = m_pLast = new tagLISTELEMENT;
if (!m_pFirst) return false;
else m_Length = 1;
//interne Zeiger anpassen
m_pFirst->pLast = m_pFirst->pNext = 0;
//Index setzten
m_pFirst->Index m_pLast->Index = 0; //Änderung
//restliche Elemente hinzufügen
while (m_Length != Length)
{
if (!_InsertNewElement(0, m_pLast, false))
{
return false;
}
}
return true;
}3.) Die Methode 'Insert':
//Methode zum Einfügen mehrerer Elemente
template <typename T>
bool CLinkedList<T>::Insert(const CLinkedList<T>& list, int Index)
{
//Die Liste soll sich nicht in sich selber einfügen können
if (&list == this) return false;
//Index anpassen
if (Index < 0) Index = 0;
if (Index > m_Length) Index = m_Length;
//Elemente bestimmen zwischen denen eingefügt werden soll
tagLISTELEMENT *pFirst, *pSecond;
if (Index == 0) //vorne anfügen
{
pFirst = 0;
pSecond = m_pFirst;
}
else if (Index == m_Length) //hinten anfügen
{
pFirst = m_pLast;
pSecond = 0;
}
else //mittendrin einfügen
{
pSecond = _GetListElement(Index);
if (!pSecond) return false;
pFirst = pSecond->pLast;
}
//Zunächst eine Kopie der übergebenden Liste erstellen
CLinkedList<T> tmp = list;
//Member der temporären Liste entwenden
tagLISTELEMENT *pFirstIns, *pLastIns;
pFirstIns = tmp.m_pFirst; tmp.m_pFirst = 0;
pLastIns = tmp.m_pLast; tmp.m_pLast = 0;
int InsLength = tmp.m_Length; tmp.m_Length = 0;
//Einfügen notwendig?
if (!InsLength) return false;
//Elemente einfügen
if (!pFirst && !pSecond)
{
m_pFirst = pFirstIns;
m_pLast = pLastIns;
}
else if (!pFirst)
{
pLastIns->pNext = m_pFirst;
m_pFirst->pLast = pLastIns;
m_pFirst->Index = -1; //Änderung
m_pFirst = pFirstIns;
}
else if (!pSecond)
{
pFirstIns->pLast = m_pLast;
m_pLast->pNext = pFirstIns;
m_pLast->Index = -1; //Änderung
m_pLast = pLastIns;
}
else
{
pFirst->pNext = pFirstIns;
pFirstIns->pLast = pFirst;
pSecond->pLast = pLastIns;
pLastIns->pNext = pSecond;
}
//Länge aktualisieren
m_Length += InsLength;
//'m_pCurrent' ungültig //Änderung...
if (m_pCurrent)
{
m_pCurrent->Index = -1;
m_pCurrent = m_pFirst;
}
//Indices von 'm_pFirst' und 'm_pLast' anpassen
m_pFirst->Index = 0; //Änderung...
m_pLast->Index = m_Length - 1;
return true;
}4.) Die Methode 'Remove':
//Methode zum Entfernen von Elementen
template <typename T>
bool CLinkedList<T>::Remove(int Start, int End)
{
//Im Falle eines leeren Arrays kein Entfernen möglich
if (m_Length == 0) return false;
//Indices überprüfen
if (Start > End)
{
int Index = Start;
Start = End;
End = Index;
}
if (Start < 0) Start = 0;
if (Start >= m_Length) Start = m_Length - 1;
if (End < 0) End = 0;
if (End >= m_Length) End = m_Length - 1;
//Das erste und das letzte Element, das gelöscht werden soll, ermitteln
tagLISTELEMENT *pLast, *pFirst;
pFirst = _GetListElement(Start);
pLast = _GetListElement(End);
//'m_pCurrent' ungültig
if (m_pCurrent) //Änderung...
{
m_pCurrent->Index = -1;
m_pCurrent = 0;
}
//Bei ungültigen Ausgaben die Grenzen verwenden
if (!pFirst) pFirst = m_pFirst;
if (!pLast) pLast = m_pLast;
//Den zu löschenden Bereich zunächst aus der Liste entfernen
if (pFirst->pLast) pFirst->pLast->pNext = pLast->pNext;
if (pLast->pNext) pLast->pNext->pLast = pFirst->pLast;
//evtl. die Grenzen anpassen, wenn das erste oder das letzte Element entfernt wurde
if (!pFirst->pLast) m_pFirst = pLast->pNext;
if (!pLast->pNext) m_pLast = pFirst->pLast;
//Grenzen des zu löschenden Berichs markieren
pFirst->pLast = pLast->pNext = 0;
//Element für Element freigeben
tagLISTELEMENT *pElement = pFirst, *pNext = pFirst->pNext;
while (pElement)
{
//Element freigeben
delete pElement;
m_Length--;
//Nächstes Element ermitteln
pElement = pNext;
if (pElement) pNext = pElement->pNext;
}
//Grenzen anpassen
if (m_pFirst && m_pLast) //Änderung...
{
m_pFirst->Index = 0;
m_pLast->Index = m_Length - 1;
m_pCurrent = m_pFirst;
}
return true;
}5.) Die Methode '_GetListElement':
Abschließend braucht dann nur noch die Methode '_GetListElement' geändert werden. Da sie aber grundlegend verändert wird, macht es kaum Sinn jede Änderung zu markieren. Aus diesem Grunde sollte folgender Quelltext als neue Implementierung der Funktion verstanden werden:
//Element (tagLISTELEMENT) ermitteln
template <typename T>
CLinkedList<T>::tagLISTELEMENT* CLinkedList<T>::_GetListElement(int Index)
{
//Index überprüfen
if (Index < 0) Index = 0;
if (Index >= m_Length) Index = m_Length - 1;
if (Index < 0) return 0;
//'m_pCurrent' festlegen, wenn nicht vorhanden
if (!m_pCurrent || m_pCurrent->Index == -1) m_pCurrent = m_pFirst;
//von vorne nach hinten, oder von hinten nach vorne durchsuchen
bool bLowHigh = true;
//Abstand des Indexes zu 'm_pCurrent' bestimmen
int diff = Index - m_pCurrent->Index;
if (diff < 0)
{
diff = -diff;
bLowHigh = false;
}
//Element von dem die Suche gestartet werden soll
tagLISTELEMENT* pElement = m_pCurrent;
//u.U. anderes Element wählen
if (diff > Index)
{
pElement = m_pFirst;
bLowHigh = true;
diff = Index;
}
if (diff > (m_Length - 1 -Index))
{
pElement = m_pLast;
bLowHigh = false;
}
//von vorne nach hinten durchlaufen?
if (bLowHigh)
{
//Von Element zu Element durch die Liste gehen
for (int iPos = pElement->Index; iPos < Index; iPos++)
{
if (!pElement) return 0;
pElement = pElement->pNext;
}
}
else
{
//Von Element zu Element durch die Liste gehen
for (int iPos = pElement->Index; iPos > Index; iPos--)
{
if (!pElement) return 0;
pElement = pElement->pLast;
}
}
//'m_pCurrent' anpassen und zurückgeben
if (m_pCurrent != m_pFirst && m_pCurrent != m_pLast)
{m_pCurrent->Index = -1;}
m_pCurrent = pElement;
m_pCurrent->Index = Index;
return m_pCurrent;
}Im Prinzip wird diese Funktion nur dahingehend erweitert, dass zunächst überprüft wird, welcher der drei Zeiger 'm_pFirst', 'm_pLast' oder 'm_pCurrent' am nächsten am gewünschten Element liegt. Anschließend wird von dem jeweiligen Zeiger aus das gewünschte Element ermittelt. bevor dieses jedoch zurückgegeben wird, wird das ehemalige Objekt, auf das 'm_pCurrent' gezeigt hat, wieder zurückgesetzt. Dann wird 'm_pCurrent' die Adresse des neu ermittelten Elements zugewiesen und mit einem gültigen Index versehen. Somit ist der Zeiger aktualisiert und steht für den nächsten Aufruf von '_GetListElement' zur Verfügung. Sobald viele Elementzugriffe in großen Listen nötig sind, sollte man die letzte Version der ersten vorziehen. Bei kleinen Listen, wird wohl die erste Version einen Vorsprung besitzen. Allerdings ist bei kleinen Listen die benötigte Zeitdauer sowieso sehr gering. Aus diesem Grunde würde ich immer die zweite Version verwenden.
Wie bereits des öfteren erwähnt, lassen sich nun beide Klassen vollkommen gleich verwenden. Die Unterschiede stecken hier nur im Kern, d.h. in der Implementierung. Man sollte sich also überlegen welche Klasse für bestimmte Aufgaben die geeignetere ist. Verkettete Listen sind v.a. dann von großem Vorteil, wenn sich ständig die Größe der Liste verändert und der verwendete Datentyp entsprechend groß ist. Ist hingegen die Zeit, die benötigt wird, um auf ein bestimmtes Element innerhalb des Arrays zuzugreifen, entscheidender, dann wäre es wohl sinnvoller einfach den dynamischen Array zu verwenden.
Um den Zugriff auf eine verkettete Liste zu vereinfachen, könnte man neben der verketteten Liste noch einen dynamischen Array speichern, der allerdings nur jeweils die Zeiger auf die jeweiligen Elemente enthält. Somit bleibt der Zugriff auf dei Elemente weiterhin genauso schnell. Dies wiederum bietet sich aber nur bei großen Datentypen an. Wählt man beispielsweise den Datentyp 'int', dann würde für jedes Element mindestens 16 Byte verwendet werden (vier Byte für tatsächliche Daten, acht Byte für die beiden Zeiger auf das vorige und das nächste Element und vier Byte für den Zeiger innerhalb des dynamischen Arrays). Ein einfacher dynamischer Array würde hingegen nur vier Byte (nur für die tatsächlichen Daten) benötigen. Die Vorteile, die eine verkettete Liste besitzt (nämlich die einfache und schnelle Änderung der Listenlänge), wären dann auch verschwunden, weil zusätzlich der gesamte dynamische Array mit den Zeigern angepasst werden muss, was aufgrund der Größe des Datentyps 'int' genauso lange dauern dürfte, wie bei einem dynamischen Array des Datentyps 'int'. Aus diesen Gründen betone ich hier noch einmal, dass keine der Varianten eine Ideallösung ist. Jede hat ihre Vor- und ihre Nachteile. Es hängt immer davon ab, zu welchen Zwecken ein Array (hier stellvertretend für einen dynamischen Array oder für eine verkettete Liste in allen Varianten) benötigt wird. Im Zweifelsfalle probiert man einfach aus, welche die schnellste Variante ist.
Hier noch einmal der Quelltext der aktuellsten Version der Klasse 'CLinkedList':
linkedlist_src.exe (Quelltext, gepackt)
