Diverse Operationen für eine Verkettete Liste

[Ich bin Matrix...]

Hi alle miteinander!
Meine Frage ist folgende:
Ich habe mir die Basis für eine einfach verkettete Liste erstellt (Liste, Kopfknoten, Knoten & Endknoten), funktioniert auch alles (bisher nur einfügen & anzeigen) und bisher auch ohne Templates. Nun möchte ich mir verschiedene Operationen hinzufügen, z.B. einen operator[] oder eine find() -Methode. Hier erstmal einige Ausschnitte:

class bNode
{
    public:
        virtual ~bNode() {}
        virtual bool insert(const Data&) = 0;
        virtual void print() const = 0;
};

class Node : public bNode
{
    Data* _data;
    bNode* _next;

    public:
        Node(const Data&, bNode*);

        Node(const Node&);

        ~Node();

        const Node& operator=(const Node&);

        bool insert(const Data&); //Inserts a new Element

        void print() const;
};

Data ist einfach eine Art Wrapper um einen einzelnen Integer. Wird noch durch Templates verallgemeinert.
Der Startknoten delegiert nur die Aufgaben weiter und der Endknoten macht fast gar nichts. Jetzt hatte ich mir für die find() -Methode folgendes gedacht:

int Node::find(const Data& dat, int counter) const
{
    if (dat.Value() == _data->Value())
        return counter;
    return _next->find(dat, ++counter);
}

...also das ich die ganze Liste durchgehe und direkt einen counter, der die momentane Stelle mitzählt durchreiche. Analog wäre das für alle anderen Arten von Operationen (Indexoperator, Sortierung, ...). Meine Frage jetzt: geht das noch besser? Ich finde es vom Style nicht so schön dort immer einen counter mitzugeben. Ich hätte gedacht, dass ich in jedem Knoten irgendwie seine Position speichere, aber dann müsste ich bspw. beim sortieren die ganze Liste durchgehen und nochmal alle Positionen neu setzen. Mir fehlt da grad ne Idee. Danke fürs lesen und ich würd mich über eure Antworten freuen

PS: Wenn was unklar ist: fragen, ich wollte jetzt nicht mein ganzes Projekt hier reinkopieren...

[camper]

Wozu Vererbung? Die impliziert doch, dass beine gewisse Varianz bei der Ableitung möglich ist. Dein Interface in bNode ist aber speziell nur für die eine Art Ableitung geeignet.

Ansonsten evtl einfach zu kompliziert gedacht, z.B.

int Node::find(const Data& dat) const
{
    return dat.Value() == _data->Value() ? 0 : _next == nullptr ? 1 : 1 + _next->find( dat );
}

[Werner Salomon]

Hallo Matrix,

tja - die Vererbungsfrage wolte ich auch gerade stellen, da sehe ich campers Antwort. Ja - wozu soll das gut sein.

Weiter sagst Du, dass Du einen operator[] einbauen möchtest. Dieser suggeriert aber, dass ein Anwender Deiner Liste in der Form

DeineListe l;
    // l füllen
    for( int i=0; i < n; ++i ) // n == ganzViele
        macheWasMit( l[i] );

über die Liste läuft. Dann rechne mal die Anzahl der Durchläufe auf, die von Node zu Node->next gemacht werden müssen. Das ist nämlich n^2/2. Und das ist bei großen Werten von n ganz schön viel mehr.
Eine verkette Liste ist nicht dafür gedacht, einem sogenannten 'random access'-Zugriff zu implementieren.

Schlauer wäre es doch eine (hoffentlich Standard konformen) Iterator zu implementieren. Dann löst sich nicht nur das find-Problem sofort auf - das macht nämlich std::find - sondern die Iteratoren ermöglichten auch allen anderen Standard-Algorithmen Zugriff auf die Liste.

Nächster Punkt. Was macht eigentlich Node::insert? Jetzt mal zurück gelehnt und überlegt - ein Knoten und da soll was eingefügt werden? Ist es nicht vielmehr so, dass in eine Liste etwas eingefügt wird? Und die Liste besteht aus einer Kette von Knoten - oder?

Und Rekursion ist auch eine prima Sache - aber irgendwann ist der Stack am Ende - viel schneller als der Heap.

Gruß
Werner

[Ich bin Matrix...]

Wozu Vererbung? Die impliziert doch, dass beine gewisse Varianz bei der Ableitung möglich ist. Dein Interface in bNode ist aber speziell nur für die eine Art Ableitung geeignet.

Ich hab Startnode und Endnode auch von bNode abgeleitet, damit ich in Node::_next nicht nur einen Verweis auf einen normalen Knoten, sondern auch auf einen Endknoten speichern kann. Bzw. im Startknoten auch einen Verweis auf den Endknoten speichern kann.

Eine verkette Liste ist nicht dafür gedacht, einem sogenannten 'random access'-Zugriff zu implementieren.

Ok, ich werds mir merken.

Was macht eigentlich Node::insert?

Ich weiß nicht, wie man das sonst machen kann, aber insert wird von der Liste aus aufgerufen und fügt, wenn der Benutzer es braucht bei Bedarf neue Knoten an die Liste an.

Ist es nicht vielmehr so, dass in eine Liste etwas eingefügt wird? Und die Liste besteht aus einer Kette von Knoten - oder?

Ist doch eine Verkettete Liste, oder hab ich da komplett was verpeilt?

sondern die Iteratoren ermöglichten auch allen anderen Standard-Algorithmen Zugriff auf die Liste.

Ja, das wäre eine Möglichkeit, aber mir dient das ganze eher zur Übung, weshalb ich mir diverse Funktionen, die es auch schon in <algorithm> u.ä. gibt selbst schreiben werde.
Aber wenn eine solche Liste nicht für random-Access geeignet ist, wars das eigentlich schon mit der Frage

[Werner Salomon]

Ich bin Matrix... schrieb:

Wozu Vererbung? Die impliziert doch, dass beine gewisse Varianz bei der Ableitung möglich ist. Dein Interface in bNode ist aber speziell nur für die eine Art Ableitung geeignet.

Ich hab Startnode und Endnode auch von bNode abgeleitet, damit ich in Node::_next nicht nur einen Verweis auf einen normalen Knoten, sondern auch auf einen Endknoten speichern kann. Bzw. im Startknoten auch einen Verweis auf den Endknoten speichern kann.

interessant - d.h., dass Start- und Endknoten von unterschiedlichem Typ sind. Ich unterstelle mal, dass der Endknoten keinen Data*-Pointer hat. Aber man kann trotzdem auf ihm z.B. insert aufrufen. Was soll dann passieren?

Ich bin Matrix... schrieb:

Was macht eigentlich Node::insert?

Ich weiß nicht, wie man das sonst machen kann, aber insert wird von der Liste aus aufgerufen und fügt, wenn der Benutzer es braucht bei Bedarf neue Knoten an die Liste an.

Das war eine rhetorische Frage - was ich meine ist, dass das insert eine Methode der Liste sein sollte. Wenn man ein neues Element in eine verkettet Liste einfügt, so muss man sich um den Vorgänger, den Nachfolger und den einzufügenden Knoten in irgendeiner Weise kümmern.
Und dazu braucht man dann keine Methode Node::insert mehr, sondern vielmehr einen Zugriff auf die Verlinkung der Knoten untereinander.

Aber bevor ich weiter spekuliere - der Member next eines Knotens zeigt doch auf den Nachfolger des Knotens. Wo wird dann nach einem insert der neue Knoten eingefügt?

Ich bin Matrix... schrieb:

sondern die Iteratoren ermöglichten auch allen anderen Standard-Algorithmen Zugriff auf die Liste.

Ja, das wäre eine Möglichkeit, aber mir dient das ganze eher zur Übung, weshalb ich mir diverse Funktionen, die es auch schon in <algorithm> u.ä. gibt selbst schreiben werde.

das kannst Du ja gerne tun, aber warum nicht mit Hilfe von Iteratoren. Auch das ist eine prima Übung.
Der Vorteil ist, dass Du verschiedene Container mit verschiedenn Algorithmen kombinieren kannst.

Im Übrigen ist das Konzept 'Iterator' ein sehr mächtiges und es lohnt sich, sich damit zu beschäftigen.

Gruß
Werner

[Ich bin Matrix...]

interessant - d.h., dass Start- und Endknoten von unterschiedlichem Typ sind. Ich unterstelle mal, dass der Endknoten keinen Data*-Pointer hat. Aber man kann trotzdem auf ihm z.B. insert aufrufen. Was soll dann passieren?

Sein insert liefert einfach false zurück, und weist somit den Knoten davor an, die Daten hinter sich zu plazieren, somit werden neue Daten immer bis zum Ende durchgereicht und hinter das letzte Element - also vor Endnode angebracht.

Aber bevor ich weiter spekuliere - der Member next eines Knotens zeigt doch auf den Nachfolger des Knotens. Wo wird dann nach einem insert der neue Knoten eingefügt?

Ganz einfach: Die Liste hat eine Methode insert und die Addresse des Startknotens gespeichert, welchem sie in ihrem Konstruktor erstellt - genauso wie den Endknoten, dessen Addresse beim Erstellen der Liste in _next vom Startknoten gespeichert werden. Am Anfang speichert also die Liste die Addy des Startknotens, welcher als Nachfolger den Endknoten hat - eine leere Liste. Auch die Liste hat natürlich eine Methode insert, welche wie gesagt vom Startknoten ausgehend die Daten bis zum Ende durchreicht. Hier mal ein wenig mehr Code, vllt wird es dir dann klarer, wie ich mir das gedacht hab.

bool Node::insert(const Data& dat)
{
    /*if (*_data < dat) //if the current element is smaller then the given one, the function returns false
        return false; //which means that the element has to be put between this and the last Node
    if (!_next->insert(dat)) //which is done here -> if insert is false for the current node, the element
        _next = new Node(dat, _next); // is smaller then the next one but bigger or equal this one
                                      // tho it is inserted as the new one relatively to the current node
                                      // or as the one before relatively to the next node
                                      //(which has returned false)
    return true;*/

    if (!_next->insert(dat)) //if insert returns false for the next node (can only happen if next node is
        _next = new Node(dat, _next/*, _position+1*/); // end node, because Node::insert always returns true) insert is
    return true; //called for the next node -> all nodes are added directly before the end node
}

Node::Node(const Data& dat, bNode* next/*, int pos*/)
        : _data(new Data(dat)), _next(next)//, _position(pos)
{
}

class List
{
    Startnode* _start;

    public:

        List();
        List(const List&);
        ~List();
        const List& operator=(const List&);
        void insert(const Data&);
        void print() const;
};

List::List()
    : _start(new Startnode(new Endnode))
{
}

void List::insert(const Data& dat)
{
    _start->insert(dat);
}

class Startnode : public bNode
{
    bNode* _next;

    public:

        Startnode(bNode*);
        Startnode(const Startnode&);
        ~Startnode();
        const Startnode& operator=(const Startnode&);
        bool insert(const Data&);
        void print() const {_next->print();}
};

Startnode::Startnode(bNode* next)
           : _next(next)
{
}

bool Startnode::insert(const Data& dat)
{
    if (!_next->insert(dat))
        _next = new Node(dat, _next);
    return true;
}

class Endnode : public bNode
{
    public:

        ~Endnode() {std::cout << "Destructor of class Endnode\n";}
        bool insert(const Data& dat) {return false;}
        void print() const {}
};

Sry, wenns zuviel Code ist :x

das kannst Du ja gerne tun, aber warum nicht mit Hilfe von Iteratoren. Auch das ist eine prima Übung.

Gut, ok, das wäre dann mein nächster Schritt.