Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Verkettete Liste

Werbeanzeige

Ba'el

Alter Hase

  • »Ba'el« ist der Autor dieses Themas

Beiträge: 409

Wohnort: Erfurt

Beruf: Student (6 FS angew. Info. - Richtung Medieninformatik)

  • Private Nachricht senden

1

30.07.2008, 16:37

Verkettete Liste

Ich versuch mich mal an einem Tutorial ... ich hoffe es ist nicht zu wirr *ggg* und nicht falsch, aber ich hab's eig. getestet dürfte keine Fehler drin haben.

Willkommen zu meinem Tutorial über verkettete Listen

  1. Theorie
  2. verkettete Liste (linked list)
    1. Element an erster Stelle einfügen
    2. beliebiges sowie erstes Element holen
    3. Länge der Liste
    4. Element an erster Stelle löschen
  3. doppelt verkettete Liste (double linked list)
    1. Element an letzter Stelle einfügen und löschen
    2. Element an beliebiger Stelle einfügen und löschen
  4. Source Code

1. Theorie

//<!Statement zurückgezogen *ggg*-->

Auf jeden Fall ist dieses Tutorial eher an Anfänger gerichtet und dient auch eher dafür bestimmte Mechanismen von C++ an einem konkreten Beispiel zu sehen.
(Naja, einen praktischen Nutzen hat das Tutorial vielleicht doch, wer mit dem Gedanken spielt Informatik zu studieren, da wird sowas sicherlich drankommen. Zumindest war es bei mir so, keine Ahnung wie es an anderen Hochschulen ist.)

Am Anfang ein kleiner Theorieteil. Was sind Listen und wozu brauch ich sie?
Nun eine Liste ist eine Datenstruktur die quasi als Container für mehrere Elemente dient. Selbst als Anfänger dürfte man mindestens eine weitere Datenstruktur kennen die etwas ähnliches macht, und zwar denn Array.
Da kann man sich sicherlich Fragen wozu Listen ich hab doch Arrays. Nun eine Liste ist nicht besser als ein Array, sie ist anders und je nachdem was man machen will muss man sich entscheiden was man nutzt.

Aufwand nach Landau

Eine grobe Aufschlüsselung für was sich eine Liste und für was sich ein Array eher lohnt. Das ist wirklich sehr grob und geht immer vom „worst case“ aus. (Die Zahl in der Klammer gibt an wieviele andere Elemente der Datenstruktur maximal „angefasst“ werden müssen. n:=Gesamtzahl der Elemente)

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13

                        Liste            Array
einfügen:
       beliebig:         O(n)            O(n)
       am Anfang:        O(1)            O(n)
       am Ende:          O(1)            O(1)
löschen:
       beliebig:         O(n)            O(n)
       am Anfang:        O(1)            O(n)
       am Ende:          O(1)            O(1)
suchen:
       „normal“:         O(n)            O(n)
       über Index:       O(n)            O(1)
       mit Iterator:     O(n)            O(n)

Wie man sieht ist ein Array immer dann sinnvoll wenn man nur über Indizes sucht und nur am Ende einfügen und löschen will. Wenn man am Anfang und am Ende einfügen und löschen will und nicht so viele Suchen durchführen muss ist die Liste auf jeden Fall die bessere Lösung. Wenn man sowohl das eine wie das andere brauch, dann muss man sich überlegen wo man Abstriche machen kann und danach entscheiden.
So genug Theorie, fangen wir an. Ich werde versuchen dieses Tutorial aufbauend zu gestalten, sprich erst das Nötigste damit es Funktioniert und dann Verbesserungen und Erweiterungen einbauen.
Zwecks des objektorientierten Ansatzes wird die Liste bei mir durch eine Klasse repräsentiert. Als erstes muss man sich überlegen was man alles brauch um etwas in einer Liste zu speichern.


2. Einfach verkettete Liste

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include<cstdlib.h>

template<typename T> class List
{
    private:

        struct Item
        {
            T m_data;
        };

    public:

        inline List()
        {
        }

        inline ~List()
        {
        }
};


Für die Liste benutzte ich ich ein Template, für die die sich nicht mit Templates auskennen ist natürlich die MSDN zu empfehlen, aber als kleine Verständnishilfe ist zu sagen das dieses Template dafür sorgt das diese Liste mit allen möglichen Datentypen gefüllt werden kann. Die Liste wird dann später so initialisiert.

C-/C++-Quelltext

 
1
2
3

//[...]

List<int>* list = new List<int>();
//[...]


Und der Compiler erstzt dann jedes T in der Klasse durch, in diesem Fall, int. Die Liste kann natürlich auch für selbst definierte Datentypen erstellt werden.
Noch etwas zu dem Wörtchen „inline“, dies zeigt dem Compiler, in diesem Fall, nur an das diese Methode in die Klasse geschrieben wird und nicht außerhalb in einer cpp, die Verwendung ist ähnlich wie bei dem this-Pointer nicht zwingend notwendig, d. h. es würde auch ohne funktionieren. (Ich benutzt normalerweise weder this noch inline, aber da das ein Tutorial ist wollt ich's ma' "richtig" machen)

So jetzt können schon Daten in der Liste gespeichert werden, aber wir bekommen sie noch nicht in die Liste, also brauchen wir eine Methode die Liste mit Elementen zu füllen. Als erstes versuchen wir ein Element vorne in die Liste einzufügen.

2.1 Element an erster Stelle einfügen

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8

    public:
        //[...]

        inline bool pushFront(T& _data)
        {
            Item* current = new Item();

            current->m_data  = _data;
        }


So jetzt können wir zwar neue Elemente erstellen aber das ist nicht wirklich eine Liste, denn die Items haben keinen Bezug zu einander. Um dieses Problem zu lösen müssen wir uns Pointer zu nutzte mache. Wir geben einfach jeden Element der List seinen Nachfolder mit und schon hat man eine verkettete Liste (LinkedList).

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

    private:

        struct Item
        {   //[...]

            Item* m_succ;   //NEU successor =  Nachfolger

        };

    public:
        //[...]

        inline bool pushFront(T& _data)
        {
            Item* current = new Item();

            current->m_data  = _data;
            current->m_succ = ?;//NEU

        }


Und schon tit sich das nächste Problem auf, woher soll das Element wissen welches Element der Liste nun sein Nachfolger ist? Die beste Lösung ist es ein erstes Element zu definieren, somit hat man auch immer einen Einstiegspunkt in die Liste.

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

    private:

        //[...]

        Item* m_first;//NEU


    public:

        inline List()
        {
            this->m_first = NULL;//NEU

        }
        //[...]

        inline bool pushFront(T& _data)
        {
            Item* current = new Item();

            current->m_data  = _data;
            current->m_succ = this->m_first;//NEU

            this->m_first = current;//NEU

            return true;
        }


Das aktuelle erste Element wird zum Nachfolger des neu Eingefügten, und dieses danach zum ersten Element der Liste gemacht.
So wir können nun endlich Elemente in der Liste speichern und die Liste ist auch schon ein Konstrukt welches man wirklich Liste nennen kann. Nur Elemente reinschaufel nützt uns relativ wenig, man muss sie natürlich wieder irgendwie aus der Liste auslesen können, darum kümmern wir uns jetzt.

2.2 beliebiges sowie erstes Element holen

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

    private:

        inline Item* get(unsigned int _index)//NEU

        {
            Item* current = this->m_first;
            if(current == NULL || _index >= this->m_length) return NULL;

            for(int i = 0; i < _index; i++)
            {
                current = current->m_succ;
            }

            return current;
        }

    public:

        //[...]

        inline T get(int _index)//NEU

        {
            Item* temp = this->getItem(_index);
            if(temp == NULL)    return NULL;

            return temp->m_data;
        }

        inline T getFirst()//NEU

        {
            if(this->m_first == NULL)   return NULL;

            return this->m_first->m_data;
        }


Da Listenelemente nicht direkt über Indizes angesprochen werden können muss man vom ersten Element zum Nächsten gehen und das solange bis man an dem Element ist welches man haben will. Um die Vorzüge der Liste zu nutzen habe ich gleich noch eine Methode geschrieben die mir das erste Element der Liste liefert.

2.3 Länge der Liste

Einen Wert den man sicherlich gut gebrauchen kann ist die Länge der Liste. Man könnte das ähnlich wie die Methode „get(int)“ was bei jedem Aufruf eine Traversion der gesamten Liste zur folge hätte. Oder man legt in der Liste eine neue Variable an in der man die Länge speichert, dass hat 4 Byte zusätzlicher Speicherplatzverbrauch und eine weiter Rechenoperation pro Einfügen oder Löschen eines Elements zur folge. Ich bevorzuge die zweite Variante.

Methode 1

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

    public:
        //[...]

        inline int length()//alternativ

        {
            Item* current = this->m_first;
            int count = 0;

            while(current != NULL)
            {
                current = current->m_succ;
                count++;
            }

            return count;
        }


Methode 2

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

    private:
        //[...]

        unsigned int m_length;//NEU


    public:

        inline List()
        {
            //[...]

            this->m_length = 0;//NEU

        }
        //[...]

        inline unsigned int length()//NEU

        {
            return this->m_length;
        }

        inline void pushFront(T& data)
        {
            //[...]

            this->m_length++;//NEU

        }


Die ersten Methode funktioniert wie ich schon sagt nach dem Prinzip der get-Methode nur läuft die Schleife nicht bis zu einem bestimmten vorher übergebenen Wert sondern solange bis das Element NULL ist, zurückgegeben wird die Anzahl der Schleifendurchläufe -> Anzahl der Elemente die nicht NULL sind.
In der zweiten Methode wird durch aufrufen von length() die Membervariable length zurückgeben, damit diese Variable die aktuelle Länge der Liste beinhaltet muss sie bei jedem hinzufügen eines Elements erhöht und bei jedem löschen erniedrigt werden.

2.4 Element an erster Stelle löschen

Apropos löschen, wir können ja noch gar nix aus der Liste entfernen, dass werden wir jetzt implementieren. Als erstes werden wir das Löschen des erste Elements einer Liste annehmen, indem wir uns das erste Element holen, dann den Nachfolger zum ersten Element machen und zum Schluss das temporäre Element, welches die Informationen des alten ersten Elements beinhaltet, löschen.

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

    private:
        //[...]

        inline ~List()
        {
            while(this->m_first!=NULL)//NEU

            {
                this->popFront();
            }
        }

        inline bool popFront()
        {
            Item* current = this->m_first;
            if(current==NULL) return false;

            this->m_first = current->m_succ;
            delete current;
            current = NULL;
            this->m_length--;

            return true;
        }


So, jetzt haben wir schon eine funktionierende Liste, wir können vorn einfügen und löschen, sowie uns ein Element an beliebiger Stelle geben lassen. Aber das Konstrukt bietet immer noch nicht alle die Vorteile die ich am Anfang erwähnte.
Um das Bestmögliche aus einer einfach verketteten Liste zu holen können wir uns das letzte Element der Liste speichern, ebenso wie wir es mit dem ersten Element gemacht haben.

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

    private:
        //[...]

        Item* m_last;//NEU


    public:

        inline List()
        {
            this->m_first =  this->m_last = NULL;//NEU

        }
        //[...]

        inline void pushFront(T& _data)
        {   //[...]

            if(current->m_succ == NULL)//NEU

            {
                 this->m_last = current;
            }
            //[...]

        }

        inline void popFront()
        {   //[...]

            this->m_first = current->m_succ;
            if(current->m_succ == NULL)//NEU

            {
                this->m_last = NULL;
            }
            //[...]

        }

        inline T getLast()//NEU

        {
            if(this->m_last == NULL)    return NULL;

            return this->m_last->m_data;
        }


So nun wird das letzte Element gespeichert, damit das geschieht müssen wir bei pushFront() prüfen ob das Element das wir einfügen wollen das erste Element ist (current->succ == NULL), wenn das der Fall ist ist dieses Element sowohl erstes als auch letztes Element der Liste.
Wo wir jetzt schon das letzte Element speichern können, was ist mit dem Einfügen oder Löschen eines Elements am Ende? Dies ist ja eines der Vorteile von Arrays. Probieren wir es einfach mal

C-/C++-Quelltext

 
1
2
3
4
5
6
7

        inline void pushBack(T& _data)
        {
            Item* current = new Item();

            current->m_data  = _data;
            current->m_succ = NULL;
            //this->m_last = current;


So, wir erstellen ein neues Element und sagen der Nachfolger ist NULL, nun haben wir aber ein Problem. Wir müssen dem Element welches vorher das Letzte war mitteilen das es nicht mehr das Letzte ist sonst würden wir es überschreiben und zudem müssen wir eine Verbindung zwischen dem letzten und dem neuen letzten Element schaffen. Ein ähnliches Problem hatten wir am Anfang schon mal, beim Einfügen am Anfang der Liste. Um uns zu behelfen haben wir dem Element seinen Nachfolger gegeben, also müsste uns jetzt das Speichern des Vorgängers weiterhelfen. Und damit hätten wir eine ...


3. Doppelt verkettete Liste

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

    private:

        struct Item
        {
            //[...]

            Item* m_pred;   //NEU predessor =  Vorgänger

        };
        //[...]

    public:
        //[...]

        inline bool pushFront(T& _data)
        {
            Item* current = new Item();

            current->data  = _data;
            current->m_pred = NULL;//NEU

            current->m_succ = this->m_first;

            if(current->m_succ == NULL)
            {
                 this->m_last = current;
            }
            else//NEU

            {
                current->m_succ->m_pred = current;
            }

            this->m_first = current;
            this->m_length++;

            return true;
        }

        inline void popFront()
        {
            Item* current = this->m_first;
            if(current==NULL) return false;

            this->m_first = current->m_succ;
            
            if( current->m_succ == NULL)
            {
                this->m_last = NULL;
            }
            else//NEU

            {
                current->m_succ->m_pred = NULL;
            }

            delete current;
            current = NULL;
            this->m_length--;

            return true;
        }


So, der Predessor ist implementiert und die schon vorhandenen Methoden die dieses verwenden wurden dementsprechend erweitert. Beim pushFront() wird der Vorgänger auf NULL gesetzt und wenn schon Elemente in der Liste sind müssen wir dem Nachfolger des gerade eingefügten Elements sagen das dieses nun sein Vorgänger ist(current->m_succ->m_pred = current;). Sieht komisch aus, ist aber so *ggg*. Bei popFront() müssen wir dem neuen ersten Element nur mitteilen das er keinen Vorgänger mehr hat(current->m_succ->m_pred = NULL;).
Nun können wir uns endlich der push-/popBack()-Methoden annehmen.

3.1 Element an letzter Stelle einfügen und löschen

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

        inline bool pushBack(T& _data)//NEU

        {
            Item* current = new Item();

            current->m_data  = _data;
            current->m_pred =  this->m_last;
            current->m_succ = NULL;

            if(current->m_pred == NULL)
            {
                this->m_first = current;
            }
            else
            {
                current->m_pred->m_succ = current;
            }

            this->m_last = current;
            this->m_length++;

            return true;
        }

        inline bool popBack()//NEU

        {
            Item* current = this->m_last;
            if(current==NULL) return false;

            this->m_last = current->m_pred;
            
            if(current->m_pred == NULL)
            {
                this->m_first = NULL;
            }
            else
            {
                current->m_pred->m_succ = NULL;
            }

            delete current;
            current = NULL;
            this->m_length--;

            return true;
        }


In pushBack() wird ein neues Element erstellt, der Vorgänger ist das letzte Element, der Nachfolger ist NULL. Wenn der Vorgänger, sprich das letzte Element, NULL ist wird dieses Element zum ersten Element der Liste. Wenn nicht wird dieses Element zum Nachfolger seines Vorgängers gemacht und schlussendlich wird das Element zum letzten Element der Liste gemacht. Die Methode popBack() ist genauso aufgebaut wie popFront(), nur wurden „first“ und „last“ ausgetauscht, sowie „pred“ und „succ“.

3.2 Element an beliebiger Stelle einfügen und löschen

Um die Implementierung der Liste zu vervollständigen fehlt eigentlich nur noch das Einfügen und Löschen an einer beliebigen stelle.

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

        inline bool push(T& _data, unsigned int _index)
        {
            if(_index > this->m_length) return false;

            if(_index == 0)
            {
                this->pushFront(_data);
            }
            else if(_index == this->m_length)
            {
                this->pushBack(_data);
            }
            else
            {
                Item* current = new Item();

                Item* temp = this->getItem(_index);

                current->m_data  = _data;
                current->m_pred = temp->m_pred;
                current->m_succ = temp;

                temp->m_pred->m_succ = current;
                temp->m_pred = current;
                this->m_length++;
            }

            return true;
        }

        inline bool pop(unsigned int _index)
        {
            Item* current = this->getItem(_index);
            
            if(current == NULL) return false;

            if(current->m_pred == NULL)
            {
                this->m_first = current->m_succ;
            }
            else
            {
                current->m_pred->m_succ = current->m_succ;
            }

            if(current->m_succ == NULL)
            {
                this->m_last = current->m_pred;
            }
            else
            {
                current->m_succ->m_pred = current->m_pred;
            }

            delete current;
            current = NULL;
            this->m_length--;

            return true;
        }


Bei push() und pop() bin ich zur Veranschauung mal zwei verschiedene Wege gegangen, bei push() benutze ich bei passenden Fällen die schon vorhandenen Implementierungen pushFront()/-Back() und pop() ist komplett neu implementiert.
In der push()-Methode prüfe ich als erstes ob der Index an dem ich das Element einfügen will größer ist als die aktuelle Länge der Liste, wenn das der Fall ist liefert die Methode ein false zurück, da in einer verketteten Liste keine Lücke sein kann. Man könnte in diesem Fall auch einfach hinten anfügen, was ich aber persönlich als irreführend einstufen würde.
Danach wird geprüft ob der Index gleich 0 ist wenn das der Fall ist wird pushFront() aufgerufen.
Im zweiten Fall Index gleich Länge der Liste kann einfach pushBack() aufgerufen werden, denn das letzte Element der Liste ist ja an Position m_legth-1.
Der letzte Fall behandelt den eigentlichen Sinn dieser Methode, ein Element irgendwo in der Mitte der Liste zu platzieren. Das könnte recht tricky werden, da wir aber durch die ersten beiden Fälle schon durch sind wissen wir auf jeden Fall schon das die Liste mindestens zwei Elemente beinhaltet und das das Element das wir einfügen wollen nicht das erste und auch nicht das letzte Element der Liste sein wird und somit wird das Problem wieder ganz einfach.
Ich denke diesen Fall beschreibe ich mit einem Beispiel. Stellen wir uns vor das die Liste schon zwei Elemente beinhaltet, an Index 0 und 1 (logischerweise). Nun wird die Methode mit dem Paramenter Index = 1 aufgerufen, somit würden alle if-Bedinungen nicht erfüllt und schließlich der letzte else-Zweig ausgeführt. Das erste was gemacht werden muss ist sich das Element zu holen welches aktuell an der Position Index ist, dieses wird nun zum Nachfolger des Neuen Elements und dessen Vorgänger wird zum Vorgänger des Neuen. Danach muss dem Vorgänger des alten Elements mitgeteilt werden das sein Nachfolger nicht mehr das alte sondern das neue Element ist. Zum Schluss muss dem Alten nur noch gesagt werden das dessen Vorgänger nun das neue Element ist und schon haben wir wieder eine komplette doppelt verkettete Liste mit drei Elementen.
Ich hab da auch gleich mal spontan was vorbereitet:


(Link)


Fehlt nur noch die pop()-Methode, dort wird erst einmal das Element der Liste gesucht welches gelöscht werden soll, wenn dies aus irgendeinem Grund NULL ist, Index zu groß oder ein anderer Fehler, wird false zurückgegeben. Als erstes wird geprüft ob der Vorgänger des Elements NULL ist wenn ja wissen wir das wir das erste Element haben und so müssen wir den Nachfolger des Elements zum First-Element der Liste machen. Wenn das nicht der Fall ist hat des Element irgendeinen Vorgänger und diesem muss mitgeteilt werden das sein Nachfolger nicht mehr das Element ist, sondern der Nachfolger des Elements. Im zweiten if-else-Block prüfen wir ob der Nachfolger des Elements NULL ist, wenn ja wissen wir das wir das letzte Element haben und genau umgedreht zum First-Pointer müssen wir in dem Fall den Vorgänger des Elements zum Last-Element der Liste machen. Wenn das nicht der Fall ist müssen wir dem Nachfolger des Elements mitteilen das dessen Vorgänger nun nicht mehr das Element ist sondern der Vorgänger des Elements. Somit wären alle nötigen Pointer „umgebogen“ und wir können das Element löschen ohne das die Kette auseinander gerissen würde.

Im Anschluss folgen die kompletten Listings.

4. Source Code

Listing der LinkedList

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

#pragma once

#include<cstdlib.h>

template<typename T> class List
{
    private:

        struct Item
        {
            T m_data;
            Item* m_succ;   //successor =  Nachfolger

        };

        Item* m_first;
        Item* m_last;
        unsigned int m_length;

    private:

        inline T get(unsigned int _index)
        {
            Item* current = this->m_first;
            if(current == NULL || _index >= this->m_length) return NULL;

            for(int i = 0; i < _index; i++)
            {
                current = current->m_succ;
            }

            return current->m_data;
        }

    public:

        inline List()
        {
            this->m_first = this->m_last = NULL;
            this->m_length = 0;
        }

        inline ~List()
        {
            while(this->m_first!=NULL)
            {
                this->popFront();
            }
        }

        inline bool pushfront(T& _data)
        {
            Item* current = new Item();

            current->m_data  = _data;
            current->m_succ = this->m_first;

            if(current->m_succ == NULL)
            {
                 this->m_last = current;
            }
            else
            {
                current->m_succ->m_pred = NULL;
            }

            this->m_first = current;
            this->m_length++;

            return true;
        }

        inline bool popFront()
        {
            Item* current = this->m_first;
            if(current==NULL) return false;

            this->m_first = current->m_succ;

            if(current->m_succ == NULL)
            {
                this->m_last = NULL;
            }

            delete current;
            current = NULL;
            this->m_length--;

            return true;
        }

        inline T get( unsigned int _index)
        {
            Item* temp = this->getItem(_index);
            if(temp == NULL)    return NULL;

            return temp->m_data;
        }

        inline T getFirst()
        {
            if(this->m_first == NULL)   return NULL;

            return this->m_first->m_data;
        }

        inline T getLast()
        {
            if(this->m_last == NULL)    return NULL;

            return this->m_last->m_data;
        }

        inline unsigned int length()
        {
            return this->m_length;
        }
};

Listing der DoubleLinkedList

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228

#pragma once

#include<cstdlib.h>

template<typename T> class List
{
    private:

        struct Item
        {
            T m_data;
            Item* m_succ;   //successor =  Nachfolger

            Item* m_pred;   //predessor =  Vorgänger

        };

        Item* m_first;
        Item* m_last;
        unsigned int m_length;

    private:

        inline T get( unsigned int _index)
        {
            Item* current = this->m_first;
            if(current == NULL || _index >= this->m_length) return NULL;

            for(int i = 0; i < _index; i++)
            {
                current = current->m_succ;
            }
            return current->m_data;
        }

    public:

        inline List()
        {
            this->m_first = this->m_last = NULL;
            this->m_length = 0;
        }

        inline ~List()
        {
            while(this->m_first!=NULL)
            {
                this->popFront();
            }
        }

        inline bool pushFront(T& _data)
        {
            Item* current = new Item();

            current->m_data  = _data;
            current->m_pred = NULL;
            current->m_succ = this->m_first;

            if(current->m_succ == NULL)
            {
                 this->m_last = current;
            }
            else
            {
                current->m_succ->m_pred = current;
            }

            this->m_first = current;
            this->m_length++;

            return true;
        }

        inline bool popFront()
        {
            Item* current = this->m_first;
            if(current==NULL) return false;

            this->m_first = current->m_succ;

            if(current->m_succ == NULL)
            {
                this->m_last = NULL;
            }
            else
            {
                current->m_succ->m_pred = NULL;
            }

            delete current;
            current = NULL;
            this->m_length--;

            return true;
        }

        inline bool pushBack(T& _data)
        {
            Item* current = new Item();

            current->m_data  = _data;
            current->m_pred =  this->m_last;
            current->m_succ = NULL;

            if(current->m_pred == NULL)
            {
                this->m_first = current;
            }
            else
            {
                current->m_pred->m_succ = current;
            }

            this->m_last = current;
            this->m_length++;

            return true;
        }

        inline bool popBack()
        {
            Item* current = this->m_last;
            if(current==NULL) return false;

            this->m_last = current->m_pred;
            
            if(current->m_pred == NULL)
            {
                this->m_first = NULL;
            }
            else
            {
                current->m_pred->m_succ = NULL;
            }

            delete current;
            current = NULL;
            this->m_length--;

            return true;
        }

        inline bool push(T& _data, unsigned int _index)
        {
            if(_index > this->m_length) return false;

            if(_index == 0)
            {
                this->pushFront(_data);
            }
            else if(_index == this->m_length)
            {
                this->pushBack(_data);
            }
            else
            {
                Item* current = new Item();

                Item* temp = this->getItem(_index);

                current->m_data  = _data;
                current->m_pred = temp->m_pred;
                current->m_succ = temp;

                temp->m_pred->m_succ = current;
                temp->m_pred = current;
                this->m_length++;
            }

            return true;
        }

        inline bool pop(unsigned int _index)
        {
            Item* current = this->getItem(_index);
            
            if(current == NULL) return false;

            if(current->m_pred == NULL)
            {
                this->m_first = current->m_succ;
            }
            else
            {
                current->m_pred->m_succ = current->m_succ;
            }

            if(current->m_succ == NULL)
            {
                this->m_last = current->m_pred;
            }
            else
            {
                current->m_succ->m_pred = current->m_pred;
            }

            delete current;
            this->m_length--;

            return true;
        }

        inline T get(unsigned int _index)
        {
            Item* temp = this->getItem(_index);
            if(temp == NULL)    return NULL;

            return temp->m_data;
        }

        inline T getFirst()
        {
            if(this->m_first == NULL)   return NULL;

            return this->m_first->m_data;
        }

        inline T getLast()
        {
            if(this->m_last == NULL)    return NULL;

            return this->m_last->m_data;
        }

        inline unsigned int length()
        {
            return this->m_length;
        }
};



Listing Test-Main

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

#include"List.h"
#include<iostream>

int main()
{
    List<int>* l = new List<int>();

    int i = 1;

    l->pushFront(i);
    i=2;
    l->pushFront(i);

    std::cout<<l->getFirst()<<" "<<l->getLast()<<std::endl;

    l->popFront();

    std::cout<<l->get(0)<<std::endl;
    std::cout<<l->getFirst()<<" "<<l->getLast()<<std::endl;

    l->popFront();

    std::cout<<l->length()<<std::endl;

    //DoubleLinkedList

    i=3;
    l->pushBack(i);

    i=4;
    l->pushBack(i);

    i=5;
    l->push(i, 1);
    
    std::cout<<l->getFirst()<<" "<<l->getLast()<<std::endl;

    l->pop(2);

    std::cout<<l->length()<<std::endl;
    std::cout<<l->getFirst()<<" "<<l->getLast()<<std::endl;
    
    l->popBack();

    std::cout<<l->length()<<std::endl;
    std::cout<<l->getFirst()<<" "<<l->getLast()<<std::endl;

    l->pop(0);

    std::cout<<l->length()<<std::endl;

    delete l;
    l = NULL;

    return 0;
}



so das war's erstmal, die Liste könnte man noch um einen Iterator erweitern, welcher die Liste noch Vorteilhafter machen würde ... ma' sehen vielleicht mach ich demnächst noch 'n Update

wenn das hier gut angenommen wird würd' ich in nächster Zeit ein mehrteiliges Tutorial über Bäume verfassen, momentan geplant:
binärer Baum, arithmetischer Baum und Rot-Schwarz-Baum
ob ich 2-3-4-Bäume auch mitmache weis ich noch nicht ... ma' sehen wie viel Zeit ich locker machen kann ;)[list=][/list][list=][/list][list=][/list]
aktuelle Projekte:
Ruby on Rails
XNA &amp; Touchless
Progr. mobiler Endgeräte (GPS Trekking)

David_pb

Community-Fossil

Beiträge: 3 886

Beruf: 3D Graphics Programmer

  • Private Nachricht senden

2

30.07.2008, 16:54

Re: Verkettete Liste

Zitat von »"Ba'el"«


Ein Satz gleich vorne Weg eine selbst programmierte Liste im eigenen Projekt zu benutzen ist in der Regel nicht sinnvoll, da diese Liste nie so performant sein wird wie die Listen in den verschiedenen Bibliotheken


Wieso denn?
@D13_Dreinig

Anonymous

unregistriert

3

30.07.2008, 16:56

So hab dann mal den Thread verschoben.

Ich hab das Tutorial noch nicht gelesen, aber ich werds heut abend mit großer Wahrscheinlichkeit mal tun. Was mir beim "Überfliegen" jedoch aufgefallen ist, möchte ich dir jedoch noch nicht vorenthalten. :D

1. Das Tutorial ist sehr lang, da ist meiner Meinung nach ein Inhaltsverzeichnis/Gliederung sehr schön. Kannst dir ja eines aus meinen Tutorials hier abkupfern. :)

2. Der erste Code-Block ist sehr wirr, wirf noch mal einen blick auf die Formatierung.

3.

C-/C++-Quelltext

 
1
2
3

#include <stdlib.h>

template <typename T>class List
bitte cstdlib benutzen und zwischen > und class ein leerzeichen, das sieht irgendwie lieblos aus.

4.

C-/C++-Quelltext

 
1
2
3
4
5
6
7

        inline List()
        {
        }

        inline ~List()
        {
        }
bitte inline wegmachen, es ist das selbe. Sofern wie ich glaube gelesen zu haben, sind alle Methoden aus Templates inline. Die big 3, sollte man sowieso nie inline machen.

5.

C-/C++-Quelltext

 
1
2

            if(temp == NULL)    return NULL;
            return temp->m_data;
das erste return überließt man sehr gern und denkt es wird m_data zurück gegeben, anstatt NULL.

6.

C-/C++-Quelltext

 
1
2
3
4
5

            if(current==NULL) return false;

            this->m_first = current->m_succ;
           
            if( current->m_succ == NULL)

Irgendwie macht die Sache mit deiner Code-Formatierung alles irgendwie wirr. z. B. oben machst du zwischen klammer und Text kein Leerzeichen, unten jedoch nach der Klammer. Dies kann über den ganzen Quelltext verfolgen. Hier solltest du etwas mehr einheitlichkeit zeigen. Dein Code repräsentiert ja dich, also sollte er nicht uneinheitlich sein - das könnte als "konfus" gelten. :D

7. Die Grafik: Gut Photoschop hätte man nicht benutzen müssen, aber damit das nicht so gekritzelt aussieht: Öffne PowerPointer oder ein anderen Präsentationsprogramm und mach da alles mit Pfeilen und Kästchen. Schwupp hast du eine sehr schöne klare Grafik, die man sich gerne anguckt. :)

Ansonsten vermiss ich noch paar kommentare und am Ende ein download des ganzen Codes als ZIP.

Wie schon gesagt, vom Inhalt her kann ich noch nichts sagen, aber ich werd das Tutorial noch auseinanderrupfen und hoffe du kannst mit den 7 - 8 Punkten Kritik schon was anfangen. :)

David_pb

Community-Fossil

Beiträge: 3 886

Beruf: 3D Graphics Programmer

  • Private Nachricht senden

4

30.07.2008, 17:05

Zitat von »"unsigned long"«


4.

C-/C++-Quelltext

 
1
2
3
4
5
6
7

        inline List()
        {
        }

        inline ~List()
        {
        }
bitte inline wegmachen, es ist das selbe. Sofern wie ich glaube gelesen zu haben, sind alle Methoden aus Templates inline. Die big 3, sollte man sowieso nie inline machen.


Alle Methoden die in einer Klassendefinition definiert werden sind automatisch inline. Aber das die "Big 3" nie "inline" deklariert werden sollten ist mir unverständlich! Dann dürfte man die Definition auch nie direkt in die Klassendefinition schreiben!

Zitat


binärer Baum, arithmetischer Baum und Rot-Schwarz-Baum


Ein RB Tree, ist doch ein Binärbaum! :-p Oder meintest du einen Binären Suchbaum?

Achja: Bitte verstärkt auf Const-Correctness achten!

Aber! Auf jedenfall aber ein schönes Tutorial.
@D13_Dreinig

Ba'el

Alter Hase

  • »Ba'el« ist der Autor dieses Themas

Beiträge: 409

Wohnort: Erfurt

Beruf: Student (6 FS angew. Info. - Richtung Medieninformatik)

  • Private Nachricht senden

5

30.07.2008, 17:16

@unsigned long
zu 3. und 6., das sind Tippfehler ... hab teilweise in OpenOffice programmiert *ggg*, werd es noch ma' durchschauen ... das Bild hatt' ich schon kurz danach geändert ^^
und den Rest werd' ich mir noch anschauen

@David_pb
ja bessere Formulierung wäre gewesen
Binäre Bäume und die Spezialfälle arithmetischer Baum und Rot-Schwarz-Baum

(da ein rbTree ein sich einigermaßen selbstbalancierenter binärer Baum ist)

edit:

hab ich glatt übersehe

Zitat von »"David_pb"«

Zitat von »"Ba'el"«


Ein Satz gleich vorne Weg eine selbst programmierte Liste im eigenen Projekt zu benutzen ist in der Regel nicht sinnvoll, da diese Liste nie so performant sein wird wie die Listen in den verschiedenen Bibliotheken


Wieso denn?


naja wie soll ich sagen, weil man es eben kaum schafft ... wenn du es schaffst ... dann ... dann geb ich dir 'n Kaffee aus^^
ein Dozent von mir, der leider nicht mehr an meiner FH ist, hat letztens erzählt das er das mal versucht hat, ich weis jetzt nicht ob mit 'ner Liste oder mit 'nem Baum, auf jeden Fall hat er das komplett in Assembler geschrieben ... und seins war trotzdem langsamer,
und er ist ein guter Programmierer, arbeitet nicht umsonst grad als lead programmer
aktuelle Projekte:
Ruby on Rails
XNA &amp; Touchless
Progr. mobiler Endgeräte (GPS Trekking)

ToxiCore

Treue Seele

Beiträge: 131

Beruf: Student

  • Private Nachricht senden

6

30.07.2008, 17:35

Müsste es bei den Landau-Symbolen nicht O(1) antatt O(0) heißen, wenn der Aufwand konstant ist?

Ich hab es es bisher auch nur kurz überflogen, aber so auf den ersten Blick sieht es schonmal ganz gut aus. Ich werds mir mal genauer ansehen wenn ich mehr Zeit habe. :)
http://www.sysprofile.de/sysprofile.png

David_pb

Community-Fossil

Beiträge: 3 886

Beruf: 3D Graphics Programmer

  • Private Nachricht senden

7

30.07.2008, 17:40

Zitat von »"Ba'el"«


naja wie soll ich sagen, weil man es eben kaum schafft ... wenn du es schaffst ... dann ... dann geb ich dir 'n Kaffee aus^^
ein Dozent von mir, der leider nicht mehr an meiner FH ist, hat letztens erzählt das er das mal versucht hat, ich weis jetzt nicht ob mit 'ner Liste oder mit 'nem Baum, auf jeden Fall hat er das komplett in Assembler geschrieben ... und seins war trotzdem langsamer,
und er ist ein guter Programmierer, arbeitet nicht umsonst grad als lead programmer


Assembler ist kein garant für schnellen Code! :) Aber auch die Listen aus "diversen" Bibliotheken wurden "nur" programmiert. Und häufig sind das möglichst allgemeine Implementationen die für Spezialfälle z.T. extrem optimiert werden können.

Edit:
Hab mal einen schnellen Vergleich meiner Implementation mit std::list<> gemacht. Getestet hab ich die verfügbaren Operationen (push_back, push_front, insert, pop_back, ...). (Threasupport, Checked Iteratoren usw hab ich ausgeschaltet)

Und tataaaa... Meine Liste ist im Schnitt 23% schneller also std::list! :-p
@D13_Dreinig

Ba'el

Alter Hase

  • »Ba'el« ist der Autor dieses Themas

Beiträge: 409

Wohnort: Erfurt

Beruf: Student (6 FS angew. Info. - Richtung Medieninformatik)

  • Private Nachricht senden

8

30.07.2008, 17:52

Zitat von »"ToxiCore"«

Müsste es bei den Landau-Symbolen nicht O(1) antatt O(0) heißen, wenn der Aufwand konstant ist?


oh stimmt ... noch mehr Tippfehle :roll: ^^
aktuelle Projekte:
Ruby on Rails
XNA &amp; Touchless
Progr. mobiler Endgeräte (GPS Trekking)

Ba'el

Alter Hase

  • »Ba'el« ist der Autor dieses Themas

Beiträge: 409

Wohnort: Erfurt

Beruf: Student (6 FS angew. Info. - Richtung Medieninformatik)

  • Private Nachricht senden

9

30.07.2008, 18:42

Zitat von »"David_pb"«

Zitat von »"Ba'el"«


Edit:
Hab mal einen schnellen Vergleich meiner Implementation mit std::list<> gemacht. Getestet hab ich die verfügbaren Operationen (push_back, push_front, insert, pop_back, ...). (Threasupport, Checked Iteratoren usw hab ich ausgeschaltet)


Und tataaaa... Meine Liste ist im Schnitt 23% schneller also std::list! :-p


nich' schlecht, wir ham nur mal so 'nen Test mit Java gemacht, und keine Implementation im Seminar war schneller als die java.util.LinkedList ...
(kannst du mal den Code deiner "Test-Main" posten will ma' meine Testen^^)
aktuelle Projekte:
Ruby on Rails
XNA &amp; Touchless
Progr. mobiler Endgeräte (GPS Trekking)

Deviloper

Community-Fossil

Beiträge: 2 872

  • Private Nachricht senden

10

30.07.2008, 18:44

Gibt es nen Grund, dass der Konstruktor nicht explicit is?
Devil Entertainment :: Your education is our inspiration
Der Spieleprogrammierer :: Community Magazin
Merlin - A Legend awakes :: You are a dedicated C++ (DirectX) programmer and you have ability to work in a team? Contact us!
Siedler II.5 RttR :: The old settlers-style is comming back!

Also known as (D)Evil

Werbeanzeige