algo2_linked_lists.cpp

#include <iostream>    // cin, cout, endl
#include <string>    // string

using namespace std;
using uint = unsigned int;


// Verkettete Liste mit Elementen des Typs T.
template<typename T>
struct List
{
    // Knoten einer solchen Liste.
    struct Node
    {
        T elem;    // Element.
        Node *next;    // Zeiger auf den nächsten Knoten oder Nullzeiger.

        // Initialisierung mit Element e und Verkettungszeiger n.
        Node(T e, Node *n) : elem(std::move(e)), next(n)
        {}
    };

    // Zeiger auf den ersten Knoten oder Nullzeiger.
    Node *head;

    // Initialisierung als leere Liste.
    List() : head(nullptr)
    {}

    // Element x zur Liste hinzufügen (und zwar am Anfang).
    void add(T x)
    {
        head = new Node(x, head);
    }

    // i-tes Element der Liste (gezählt ab 0) über den Referenz-
    // parameter x zurückliefern, falls vorhanden.
    // Resultatwert true genau dann, wenn es ein i-tes Element gibt.
    bool get(uint i, T &x)
    {
        for (Node *p = head; p; p = p->next, i--)
        {
            if (i == 0)
            {
                x = p->elem;
                return true;
            }
        }
        return false;
    }

    // Das erste Element x aus der Liste entfernen, falls vorhanden.
    // Resultatwert true genau dann, wenn Element x vorhanden war.
    // Bei Verwendung dieser Funktion muss es einen Operator == zum
    // Vergleich zweier Objekte des Typs T geben. Bei Bedarf kann so
    // ein Operator passend definiert werden, vgl. § 1.4.9.
    bool remove(T x)
    {
        Node *q = nullptr;
        for (Node *p = head; p; q = p, p = p->next)
        {
            if (p->elem == x)
            {
                if (q) q->next = p->next;
                else head = p->next;
                delete p;
                return true;
            }
        }
        return false;
    }

    int removeAll(T x)
    {
        Node *tempNode;
        int counter = 0;
        while (head != nullptr && head->elem == x)
        {
            counter++;
            tempNode = head;
            head = head->next;
            delete tempNode;
        }

        Node *anotherTempNode = head;
        if (anotherTempNode != nullptr)
        {
            while (anotherTempNode->next != nullptr)
            {
                if (anotherTempNode->next->elem == x)
                {
                    counter++;
                    tempNode = anotherTempNode->next;
                    anotherTempNode->next = anotherTempNode->next->next;
                    delete tempNode;
                } else
                {
                    anotherTempNode = anotherTempNode->next;
                }
            }
        }
        return counter;
    }

    bool removeLast(T x)
    {
        Node *tempNode = nullptr;
        Node *currentNode = head;

        while (currentNode != nullptr)
        {
            if (currentNode->elem == x)
            {
                tempNode = currentNode;
            }
            currentNode = currentNode->next;
        }

        if (tempNode != nullptr)
        {
            Node *nodeToRemove = head;
            while (nodeToRemove->next != tempNode)
            {
                nodeToRemove = nodeToRemove->next;
            }
            nodeToRemove->next = tempNode->next;
            tempNode->next = nullptr;
            delete tempNode;
            return true;
        }
        return false;
    }

    void invert()
    {
        Node *currentNode = head;
        Node *prevNode = nullptr;
        Node *tempNode;

        while (currentNode != nullptr)
        {
            tempNode = currentNode->next;
            currentNode->next = prevNode;
            prevNode = currentNode;
            currentNode = tempNode;
        }
        head = prevNode;
    }

    List<T> copy()
    {
        return internal_copy(true);
    }

    List<T> reverse()
    {
        return internal_copy(false);
    }

private:
    List<T> internal_copy(const bool invert)
    {
        List<T> newList;
        Node *currentNode = head;

        while (currentNode != nullptr)
        {
            newList.add(currentNode->elem);
            currentNode = currentNode->next;
        }
        if (invert)
        {
            newList.invert();
        }
        return newList;
    }
};

int main()
{
    // Liste von Zeichenketten.
    List<string> ls;

    // Hilfsvariablen.
    string cmd, elem;

    // Befehle von der Standardeingabe lesen und verarbeiten:
    // + elem -> elem zur Liste hinzufügen
    // ? i -> i-tes Element der Liste ausgeben
    // - elem -> elem aus der Liste entfernen
    // -- elem -> Delete all <elem> elements from list
    // cp -> copies the existing list
    // rev -> returns a new list in reversed order
    // inv -> reverses the current list inplace
    // q -> Programm beenden

    while (cout << "cmd: ", cin >> cmd)
    {
        if (cmd == "+")
        {
            cin >> elem;
            ls.add(elem);
        } else if (cmd == "?")
        {
            uint i;
            cin >> i;
            if (ls.get(i, elem)) cout << elem;
            cout << endl;
        } else if (cmd == "-")
        {
            cin >> elem;
            ls.remove(elem);
        } else if (cmd == "q")
        {
            break;
        } else if (cmd == "--")
        {
            cin >> elem;
            cout << "Deleted " << ls.removeAll(elem) << " items" << endl;
        } else if (cmd == "dl")
        {
            cin >> elem;
            std::cout << "Deleted last elem: " << elem << " " << std::boolalpha << ls.removeLast(elem) << std::endl;
        } else if (cmd == "cp")
        {
            ls = ls.copy();
        } else if (cmd == "inv")
        {
            ls.invert();
        } else if (cmd == "rev")
        {
            ls = ls.reverse();
        }
    }
}