implemetierung einer doppelt verketten liste

Swordfish

Hi!

Zu beginn sind start und stop NULL (Globale Zeiger auf T_elem? ). Beim Einfügen des ersten Elements in die Liste, wird eine T_elem -Instanz angelegt, auf die start und stop zeigen. Dieses Element bekommt den einzufügenden Wert.

Jedes weitere Element wird jetzt vorläufig "vor" dem Ersten ( start ) eingefügt ( start->prev = new T_elem ). Damit das neue Element auch weiß, wer sein nächster ist: start->prev->next = start; . Nun noch den start auf das neue Element setzen ( start = start->prev; ), den Wert zuweisen, und festlegen, dass start keinen Vorgänger hat start->prev = NULL; .

greetz, Swordfish

BTW: Schönes C++ ist das nicht...

*D*Evil

struct T_elem
{
    unsigned key;
    T_elem *prev, *next;
};

T_elem* start = NULL;
T_elem* stop = NULL;

void add_first(const unsigned data)
{
    if (start == NULL) // noch kein Element in der Liste?
    {
        start = new T_elem; // Das 1. Element belegen
        start->key = data; // Daten zuweisen
        start->prev = NULL; // 1. Element => Kein Element vorher!
        start->next = NULL; // Ende der Liste => Nächstes Element existiert nicht!
        stop = start; // Das 1. == Letzte Element in der Liste
        return;   

    }

    // das was jetzt kommt ist irgendwie doof. Er fügt in die falsche Richtung ein, aber egal ;)
    start->prev = new T_elem; // Element vor erstem einfügen
    start->prev->next = start; // das 1. Element ist nun unser neu angefügtes, d.h. das vorherige 1. ist nun das auf 1 folgende.
    start = start->prev; // das 1. Element ist unser neu angefügtes
    start->key = data; // Daten setzen
    start->prev = NULL; // start ist das 1. Element. Es gibt kein Vorheriges!
}

... So und das kann man auch ordentlich machen

template<typename _Type>
class double_list
{
    template<typename _Type>
    struct element 
    { 
        element* m_prev; 
        element* m_next;
        _Type m_data;
        element(_Type const& data) 
            : m_prev(NULL), m_next(NULL), m_data(data)
        {}
    };

    typedef element<_Type> value_type;
    typedef std::size_t size_type;

    value_type* m_first;
    value_type* m_last;
    size_type m_size;

public:
    double_list()
        : m_first(NULL), m_last(NULL), m_size(0)
    {}

    double_list(double_list const& rhs)
    {
        if (&rhs == this) return;
        for (value_type* ptr(rhs.m_first); m_size < rhs.m_size; ptr = ptr->m_next)
            push_back(ptr->m_data);    
    }

    ~double_list()
    {
        for (value_type* ptr(m_last); m_size; --m_size)
        {
            value_type* next(ptr->m_prev);
            delete ptr;
            ptr = next;
        }
    }

    double_list& operator=(double_list const& rhs)
    { 
        if (&rhs == this) return *this;
        for (value_type* ptr(rhs.m_first); m_size < rhs.m_size; ptr = ptr->m_next)
            push_back(ptr->m_data);
    }

public:
    void push_front(_Type const& data)
    {
        if (m_first == NULL)
        { m_last = m_first = new value_type(data);  ++m_size; return; }

        m_first->m_prev = new value_type(data);
        m_first->m_prev->m_next = m_first;
        m_first = m_first->m_prev;
        ++size;
    }
    void push_back(_Type const& data)
    {
        if (m_last == NULL)
        { m_last = m_first = new value_type(data); ++m_size; return; }

        m_last->m_next = new value_type(data);
        m_last->m_next->m_prev = m_last;
        m_last = m_last->m_next;
        ++m_size;
    }
};

so ... jetzt noch schnell nen Iterator dafür schreiben und du bist fertig

hustbaer

Hm. Wieso verwendet eigentlich kaum jmd. Ringlisten?

Mir ist das auf jeden Fall immer viel zu doof die ganzen Randbedingungen zu checken die sich bei "normalen" doppelt verketteten Listen ergeben, daher verwende ich eigentlich nur Ringlisten (wenn ich wirklich mal eine selbstgeschriebene Liste brauche).

Vorne/hinten einfügen oder löschen geht ja noch, richtig lustig wird's dann wenn man ein beliebiges Elemtent entfernen möchte, oder an einer beliebigen Stelle etwas einfügen.

drakon

hustbaer schrieb:

Hm. Wieso verwendet eigentlich kaum jmd. Ringlisten?

Mir ist das auf jeden Fall immer viel zu doof die ganzen Randbedingungen zu checken die sich bei "normalen" doppelt verketteten Listen ergeben, daher verwende ich eigentlich nur Ringlisten (wenn ich wirklich mal eine selbstgeschriebene Liste brauche).

Vorne/hinten einfügen oder löschen geht ja noch, richtig lustig wird's dann wenn man ein beliebiges Elemtent entfernen möchte, oder an einer beliebigen Stelle etwas einfügen.

Wie unterscheidet sich den das einfügen bzw. löschen bei Ringlisten von doppelt verketteten Listen?

Shade Of Mine

hustbaer schrieb:

Hm. Wieso verwendet eigentlich kaum jmd. Ringlisten?

Weil das mit der STL nicht ganz harmoniert. Das Problem ist: wo zeigt der end iterator hin?

Jester

Das frage ich mich auch immer. Leider gibt es einige Bücher, die nur die Null-Terminierung vorstellen. Außerdem beziehen glaube ich viele ihre Kenntnisse aus Tutorials und die werden meist von Leuten geschrieben, die die Ringlistenimplementierung ebenfalls nicht kennen.

Shade Of Mine schrieb:

Das Problem ist: wo zeigt der end iterator hin?

In meinem jugendlichen Leichtsinn, sag ich jetzt einfach mal, der zeigt auf das Element, das als Nachfolger das Start-Element hat. Zumindest habe ich das in den paar Ringlisten, die ich mal gemacht, so gelöst. Allerdings waren die nicht STL-konform.

Grüße Joe_M.

Fellhuhn

Der end-Iterator zeigt ja eben nicht auf das letzte Element in der STL, sondern dahinter.
Somit müsstest du ja auf das Element hinter dem verweisen das vor dem Start-Element ist. Also wieder auf das Start-Element...

Jester

Shade Of Mine schrieb:

hustbaer schrieb:

Hm. Wieso verwendet eigentlich kaum jmd. Ringlisten?

Weil das mit der STL nicht ganz harmoniert. Das Problem ist: wo zeigt der end iterator hin?

na auf das dummy-element, das den ring schließt. Es liegt damit gleichzeitig vor dem ersten Element und hinter dem letzten. du warst doch auf dem forum-treffen vor zwei Jahren???

btw, mal in deine stl-implementierung reingeschaut? -- die meisten benutzen eine ringliste.

nieselfriem

Ich habs!!!!!!!!!!!!!!!!!!!

Alles klar verstanden

Danke & Gruß niesel

hustbaer

drakon schrieb:

hustbaer schrieb:

Hm. Wieso verwendet eigentlich kaum jmd. Ringlisten?

Mir ist das auf jeden Fall immer viel zu doof die ganzen Randbedingungen zu checken die sich bei "normalen" doppelt verketteten Listen ergeben, daher verwende ich eigentlich nur Ringlisten (wenn ich wirklich mal eine selbstgeschriebene Liste brauche).

Vorne/hinten einfügen oder löschen geht ja noch, richtig lustig wird's dann wenn man ein beliebiges Elemtent entfernen möchte, oder an einer beliebigen Stelle etwas einfügen.

Wie unterscheidet sich den das einfügen bzw. löschen bei Ringlisten von doppelt verketteten Listen?

Dadurch dass man bei Ringlisten keine "ifs" braucht.

drakon

hustbaer schrieb:

drakon schrieb:

hustbaer schrieb:

Hm. Wieso verwendet eigentlich kaum jmd. Ringlisten?

Mir ist das auf jeden Fall immer viel zu doof die ganzen Randbedingungen zu checken die sich bei "normalen" doppelt verketteten Listen ergeben, daher verwende ich eigentlich nur Ringlisten (wenn ich wirklich mal eine selbstgeschriebene Liste brauche).

Vorne/hinten einfügen oder löschen geht ja noch, richtig lustig wird's dann wenn man ein beliebiges Elemtent entfernen möchte, oder an einer beliebigen Stelle etwas einfügen.

Wie unterscheidet sich den das einfügen bzw. löschen bei Ringlisten von doppelt verketteten Listen?

Dadurch dass man bei Ringlisten keine "ifs" braucht.

- Was meinst du damit?

In eine Liste was einfügen geht ja einfach mit pusch_back () und löschen mit erase (iterator). Ok, beim löschen gibt es einen iterator, aber ich denke mal nicht, dass eine Ringliste ohne einen auskommt.

*D*Evil

Vllt. solltest du (drakon) mal eine Liste Implementieren ... dann weißt du evtl. was er meint

drakon

(D)Evil schrieb:

Vllt. solltest du (drakon) mal eine Liste Implementieren ... dann weißt du evtl. was er meint

- Da ist es noch nicht über den reinen Gedanken gekommen.

Ich habe es auf die Benutzung bezogen.

hustbaer

Vielleicht solltest du dir deine sonstwohin tun.
Klar rede ich hier von der Implementierung, in dem Thread geht es ja auch um die Implementierung. Was auch nicht schwer herauszufinden sein sollte. Der Thread-Titel "implemetierung einer doppelt verketten liste" hilft IMO ungemein.
Ein oder 2 Postings lesen hilft auch sehr.

drakon

Um das mal klar zu stellen, ich habe mich immer auf diesen Post bezogen:

hustbaer schrieb:

Hm. Wieso verwendet eigentlich kaum jmd. Ringlisten?

Mir ist das auf jeden Fall immer viel zu doof die ganzen Randbedingungen zu checken die sich bei "normalen" doppelt verketteten Listen ergeben, daher verwende ich eigentlich nur Ringlisten (wenn ich wirklich mal eine selbstgeschriebene Liste brauche).

Vorne/hinten einfügen oder löschen geht ja noch, richtig lustig wird's dann wenn man ein beliebiges Elemtent entfernen möchte, oder an einer beliebigen Stelle etwas einfügen.

Und da du von verwenden gesprochen hast, bin ich davon mit meiner Frage ausgegangen.

hustbaer

Hehe, ok.
"Ringlisten verwenden" im Sinn von das Konzept Ringliste verwenden um eine Implementierung zu basteln.
Sorry, war zugegebenermassen etwas unklar.

drakon

Ok.
Was mit den if's gemeint ist, habe ich oben auch mal noch gesehen. Aber wenn ich das also richtig sehe, gibt es in der Verwendung keinen grossen Unterschied.