Listen

Listen sind in der Datenverarbeitung so verbreitet, dass es sogar eine Programmiersprache gibt, die sie im Namen trägt: LISP (LISt Progcessing). So weit geht's in C++ zwar nicht, aber trotzdem werden die üblichen Dinge angeboten: die STL hält einfach und zweifach verkettete Listen bereit.

Video

Quellcode

#include <list>
#include <forward_list>
#include <iostream>

template <typename T> class FList
{
    struct ListNode
    {
        T value;
        ListNode *next;
        
        ListNode(T const &v)
            : value(v), next(nullptr)
        {
        }
    };
    
    ListNode *start;
    
public:
    
    class iterator
    {
        ListNode *ln;
        
        friend class FList;
        
    public:
        iterator(ListNode *l)
            : ln(l)
        {
        }
        
        iterator &operator++()
        {
            ln = ln->next;
            return *this;
        }
        
        iterator &operator++(int)
        {
            iterator tmp(*this);
            ln = ln->next;
            return tmp;
        }
        
        T &operator*()
        {
            return ln->value;
        }
        
        bool operator!=(iterator const &other)
        {
            return ln != other.ln;
        }
        
        bool operator==(iterator const other)
        {
            return ln == other.ln;
        }
    };
    
    FList()
        : start(nullptr)
    {
    }
    
    FList(std::initializer_list<int> const &init)
        : start(nullptr)
    {
        for (int i : init) {
            push_back(i);
        }
    }
    
    ~FList()
    {
        auto ln = start;
        while (ln != nullptr)
        {
            auto tmp = ln;
            ln = ln->next;
            delete tmp;
        }
    }
    
    iterator begin() const
    {
        return iterator(start);
    }
    
    iterator end() const
    {
        return iterator(nullptr);
    }
    
    void push_back(T const &value)
    {
        if (start == nullptr) {
            start = new ListNode(value);
        }
        else {
            ListNode *ln = start;
            while (ln->next != nullptr) {
                ln = ln->next;
            }
            ln->next = new ListNode(value);
        }
    }
    
    iterator erase_after(iterator it)
    {
        auto tmp = it.ln->next;
        it.ln->next = it.ln->next->next;
        delete tmp;
        return ++it;
    }
};

int main()
{
    std::list<int> l { 1, 2, 3, 4, 5 };
    std::forward_list<int> l2 { 8, 9, 0, 3, 1 };
    FList<int> l3 { 8, 6, 4, 2 };

    std::cout << "list:\n";
    for (auto rit = l.rbegin(); rit != l.rend(); ++rit) {
        std::cout << *rit << " ";
    }
    std::cout << std::endl;
    
    std::cout << "forward_list:\n";
    for (int i : l2) {
        std::cout << i << " ";
    }
    std::cout << std::endl;
    
    std::cout << "FList:\n";
    for (int i : l3) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    auto it = l3.begin();
    ++it;
    l3.erase_after(it);
    std::cout << "FList erase:\n";
    for (int i : l3) {
        std::cout << i << " ";
    }
    std::cout << std::endl;
}

Erklärung

Die Verwendung von Listen in C++ ist genau wie bei allen anderen Containern geregelt: passenden Header einbinden und die entsprechenden Klassen stehen als Template zur Verfügung. std::list ist hierbei eine zweifach verkettete Liste. Sie kann also vor- und rückwärts durchlaufen werden. Dafür braucht sie aber auch (in der naheliegenden Implementierung) mindestens zwei Pointer pro Listenelement. Je nach Plattform und Listentyp kann das schon einen gehörigen Overhead bedeuten. Für die Fälle, wo das umgekehrte Durchlaufen einer Liste nicht notwendig ist, gibt es die etws einfachere std::forward_list. Durch diese einfach verkettete Liste spart man sich einen Pointer pro Element, kann aber dafür auch nur vorwärts durchlaufen.

Die Konstruktion einer einfach verketteten Liste hat tiefgreifenden Einfluss auf deren Schnittstelle. Normalerweise beherrscht jeder Container Funktionen wie erase, die anhand eines Iterators Elemente aus dem Container entfernen kann. In std::forward_list kann diese Funktionalität prinzipbedingt nicht effizient realisiert werden. Um nämlich ein Element aus der Liste zu löschen, muss der Nachfolger des Vorgängerelementes auf den Nachfolger des zu löschenden Elementes gesetzt werden (und damit das zu löschende Element quasi "umgangen"). Problem: in einer einfach verketteten Liste kennt ein Element seinen Vorgänger nicht und kann daher auch diesen Vorgang nicht effizient durchführen. Die einzige Möglichkeit, die bleibt, wäre, die Liste von Anfang an zu durchsuchen, bis ein Element gefunden ist, dessen Nachfolger das zu löschende Element ist. Das ist allerdings in O(n) und damit nicht mehr sonderlich effizient. std::forward_list geht daher einen anderen Weg und bietet die Methode erase_after an: statt einen Iterator zu löschen wird dessen Nachfolger gelöscht. Das ist effizient möglich, wird aber ein wenig anders verwendet, als das klassische erase. std::list ist hier wieder anders: durch die doppelte Verkettung ist der Vorgänger problemlos zu erreichen und erase kann effizient implementiert werden.