Destruktor für einfache Linked List, Speicherverwaltung



  • Hallo.
    Ich habe vor kurzem damit angefangen, C++ zu lernen und habe eine einfache linked list geschrieben. Alles läuft wie es soll, nur habe ich völlig den Überblick verloren, was den dynamische Speicherverwaltung angeht. Um alle Elemente in der Liste zu löschen, gehe ich die gesamte Liste durch und gebe für jedes Element den Speicher wieder frei. Sorgt dieser Vorgang dafür, dass alle reservierten Speicherbereiche freigegeben werden? Soweit ich das verstanden habe, muss ich für jeden "new" Befehl, auch einen "delete" Befehl verwenden.

    So sieht die Klasse aus:

    class linked_list
    {
    private:
        struct Node  //struct that holds the values, data type can be changed at will
        {
            int data;
            Node *next_node;
        };
        Node *first, *last;
        unsigned int length;  //length can't be negative so type is unsigned
    public:
        linked_list() //constructor, used to create a new list
        {
            first = NULL;   //initial list is empty, both pointers set to NULL
            last = NULL;
            length = 0;
        }
        ~linked_list();
        void insertBack(int n); //inserts a value into the back of the list
        void insertFront(int n); //inserts a value into the front of the list
        void insert(int index, int n); //inserts a value at the specified location, 0 corresponds to first element while length - 1 is the last
        void displayList(void) const; //displays the contents of the list
        void clearList(void); //traverses the list and deletes all entries
        int getLength(void) const; //returns the length of the list as an integer
    };
    

    und hier die Funktionen zum Einfügen der Elemente:

    void linked_list::insertBack(int n)
    {
        Node *p_temp = new Node; //allocate new memory on heap for new node
        p_temp -> data = n;      //set data variable of node to given argument
        p_temp -> next_node = NULL;  //new node is the last element, so next node is NULL
    
        if(first == NULL)  //if the list is empty...
        {
            first = p_temp;  //first and last point the the only element
            last = p_temp;
            length++;
        }
        else
        {
            last -> next_node = p_temp; //otherwise next pointer of last node will point to new node
            last = p_temp;
            length++;              //last now points to "new" last node
        }
    }
    
    void linked_list::insertFront(int n)
    {
        Node *p_temp = new Node;
        p_temp -> data = n;
        p_temp -> next_node = NULL;
    
        if(first == NULL)  //if the list is empty...
        {
            first = p_temp;  //first and last point to the only element
            last = p_temp;
            length++;
        }
        else
        {
            p_temp -> next_node = first; //otherwise next pointer of new node points to initial first node
            first = p_temp;  //new node becomes the first node (first points to new node now)
            length++;
        }
    }
    
    void linked_list::insert(int index, int n)
    {
        Node *p_temp = new Node;
    
        if(index > length || index < 0) //
        {
            std::cout << "Specified location " << index << " is out of bounds."
                      << "Call getLength() to find possible locations." << std::endl
                      << std::endl;
        }
    
        else if(index == length)  //insert into back
        {
            p_temp -> data = n;
            last -> next_node = p_temp;
            last = p_temp;
            p_temp -> next_node = NULL;
            length++;
        }
    
        else if(first == NULL) //insert into front
        {
            p_temp -> data = n;
            p_temp -> next_node = NULL;
            first = p_temp;
            last = p_temp;
            length++;
        }
    
        else if(index  == 0) //insert into front
        {
                p_temp -> data = n;
                p_temp -> next_node = first;
                first = p_temp;
                length++;
        }
    
        else
        {
            p_temp = first;
            for(int i = 0; i < index; i++)  //traverse list until specified location is encountered
            {
                if(i == index - 1)
                {
                    Node *p_temp_n = new Node;   //node that holds specified data n
                    Node *p_temp_y = new Node;   //stores node that comes after inserted node
                    p_temp_n -> data = n;
                    p_temp_y = p_temp -> next_node;
                    p_temp -> next_node = p_temp_n;
                    p_temp_n -> next_node = p_temp_y;
                    length++;
                }
                else
                    p_temp = p_temp -> next_node;
    
            }
        }
    }
    

    Zum Löschen der Liste:

    void linked_list::clearList(void)
    {
        if(first == NULL)
        {
            std::cout << "The list is already empty." << std::endl;
        }
        else
        {
            Node *p_temp = new Node;
            while(first != NULL)
            {
                p_temp = first;   //set temporary pointer to first node
                first = first -> next_node;  //move first pointer to next node
                delete p_temp; //delete temporary pointer and the associated node
            }
            length = 0;              //set length and first pointer to zero after successful traversal
            first = NULL;
            last = NULL;
            std::cout << "List deleted.\n";
        }
    }
    

    Meine Frage lautet nun: Gibt die clearList() Funktion den gesamten reservierten Speicher frei?

    Bedanke mich im vorraus für jede Art von Hilfe!



  • Du brauchst in diesem Beispiel kein Speicher allocieren. Du benutzt nirgendswo ein Array, dass dynamische Speicherverwaltung bedingt. Daher musst du nirgends Speicher wieder frei geben. Der verwendete Speicher für Elemente von Node werden ohnehin wieder freigegeben. Den Destruktor könntest du dir auch sparen in dem Beispiel.



  • @TristanS sagte in Destruktor für einfache Linked List, Speicherverwaltung:

    Du benutzt nirgendswo ein Array, dass dynamische Speicherverwaltung bedingt

    Ein Array beding keine dynamische Speicherverwaltung.



  • @alfons19 sagte in Destruktor für einfache Linked List, Speicherverwaltung:

    Node *p_temp = new Node;

    in clearList? Warum? Der Speicher ist schon mal verloren.

    @alfons19 sagte in Destruktor für einfache Linked List, Speicherverwaltung:

    Meine Frage lautet nun: Gibt die clearList() Funktion den gesamten reservierten Speicher frei?

    Wenn du vorher alles richtig gemacht hast: ja, scheint korrekt zu sein (aber siehe oben).

    Das ganze sieht mehr nach 1998 als nach 2019 aus. Ein aktuelles Buch wäre vielleicht hilfreich.



  • length can't be negative so type is unsigned

    Das ist kein guter Grund, unsigned zu verwenden. Als Faustregel: Verwende nur unsigned, wenn Du die speziellen Eigenschaften benötigst (overflow, oder für Bit-Operationen), oder wenn Dich die tolle Standardbibliothek mit ihrem size_t dazu nötigt. Grund: Wenn z. B. eine negative Zahl ein fehlerhafter Wert wäre, könntest Du dies bei signed erkennen und darauf reagieren. Bei unsigned wird aber der Fehler sozusagen "vertuscht". Es gibt noch weitere Gründe, z.B. wird es nicht schön, wenn Du in Berechnungen signed und unsigned vermischen tust, dann kann auch z. B. ein eigentlich negativer Wert nach unsigned konvertiert werden.

    Ich verstehe natürlich den Zweck von Übungsaufgaben zum Lernen, aber Du solltest wissen, dass Listen v. A. auf modernen Prozessoren praktisch immer ineffizient sind im Vergleich zu kontinuierlichem Speicher (fixed/dynamic sized arrays). Selbst ein std::vector mit Zeigern auf die Knoten ist meist schneller als eine Liste aus den Knoten. Das hat vor Allem mit den Eigenschaften der Cacheverwaltung zu zun, was auf die Performance einen sehr großen Einfluss hat (da meist die CPU sehr viel schneller als der RAM ist und auf Speicherzugriffe warten muss).

    cout<< etc. kann man natürlich zum Debuggen einfügen, sollten aber im echten Code niemals z. B. ein einem Destruktor, insert etc. stehen, das passt da nicht hin.

    Der Ansatz in deiner clearList() ist im Prinzip richtig, aber Du machst den Fehler einen neuen Node zu allokieren, nur damit Du einen temp Zeiger hast. Das brauchst Du nicht, es reicht folgendes:

    while (first != nullptr) {
        Node *temp = first;  // Variablen so lokal wie möglich halten; Hungarian Notation vermeiden (das sind Altlasten von früher)
        first = first->next_node;
        delete temp;
    }
    

    void linked_list::insert(int index, int n) sieht beispielsweise auch nicht so 100% korrekt aus.



  • @manni66 sagte in Destruktor für einfache Linked List, Speicherverwaltung:

    Ein aktuelles Buch wäre vielleicht hilfreich.

    Das.



  • @HarteWare sagte in Destruktor für einfache Linked List, Speicherverwaltung:

    Das ist kein guter Grund, unsigned zu verwenden. Als Faustregel: Verwende nur unsigned, wenn Du die speziellen Eigenschaften benötigst (overflow, oder für Bit-Operationen), oder wenn Dich die tolle Standardbibliothek mit ihrem size_t dazu nötigt. Grund: Wenn z. B. eine negative Zahl ein fehlerhafter Wert wäre, könntest Du dies bei signed erkennen und darauf reagieren. Bei unsigned wird aber der Fehler sozusagen "vertuscht".

    Wer hat Dir den Unfug beigebracht? Wenn ich nur positive Werte gebrauchen kann, nehme ich einen unsigned Typ und ich muß nie überprüfen, ob mir ein Penner einen negativen Wert übergeben hat:

    void func( unsigned wert )
    {
       assert( wert < was auch immer );
    }
    

    statt

    void func( signed wert )
    {
       assert( wert >= 0 && wert < was auch immer );
    }
    

    mfg Martin



  • @mgaeckler ließ mal einen unsigned von einem Stream du Held.

    mfg blubb



  • @Swordfish Ja und? Wo siehst Du da einen Widerspruch?



  • @mgaeckler Deine Beispiele sind m. E. nach ziemlich nichtssagend:

    unsigned area(unsigned a, unsigned b) {
        return a*b;
    }
    
    /// ...
    std::cout << "area: " << area(-5, 1) << '\n'; // area: 4294967291  <-- Das Ergebnis stimmt natürlich
    

    Wenn man hier einen signed nimmt, kann man solche Fehler abfangen und handhaben, anstatt still und heimlich weitermachen, bis es irgendwann knallt.

    Der hier ist auch immer gut:

    int main() {
    	int x = -5;
    	unsigned y = 5;
    	std::cout << "-5 * 5 = " << x * y << '\n'; // -5 * 5 = 4294967271
    }
    


  • @HarteWare

    Warnung 126 warning C4365: "Argument": Konvertierung von "int" in "unsigned int", signed/unsigned-Konflikt. C:\CRESD\Source\GAK_CLI\TOOLS\mirror.cpp 1459 1 mirror

    Das andere Beispiel habe ich jetzt nicht ausprobiert.



  • Danke für die Antworten.

    Ich lerne mithilfe von 2 Büchern (Accelerated C++ und C++ primer plus). Was gibt es denn für aktuelle Alternativen?

    Ich weiß, dass man besser Funktionen der Standard Library verwenden sollte, ich wollte die Liste nur so als Übung schreiben.

    Was die cout's angeht, wie sonst signalisiert man dem Nutzer, dass was schief gelaufen ist? Boolean als Rückgabewert?



  • @alfons19 Mit Exceptions z. B. so:

    void machwas() {
        throw std::runtime_error{"Error"};
    }
    
    int main()
    try {
        machwas();
    } catch (const std::runtime_error& e) {
        std::cerr << e.what() << '\n';
        return 1;
    } catch (...) {
        std::cerr << "An unknown error has occured.\n";
        return 2;
    }
    

    Kommt auch immer ein bisschen darauf an, was für Fehler es sind.
    Ganz wichtig: Im Destruktor keine Exceptions werfen!
    "The list is already empty." und "List deleted.\n" würde ich jetzt auch nicht als Fehler bezeichnen.
    @mgaeckler

    Warnung 126 warning C4365: "Argument": Konvertierung von "int" in "unsigned int", signed/unsigned-Konflikt. C:\CRESD\Source\GAK_CLI\TOOLS\mirror.cpp 1459 1 mirror

    Na siehste, hättest da einen int statt unsigned genommen, wär die lästige Warnung nicht da :o)



  • @alfons19

    Ich lerne mithilfe von 2 Büchern (Accelerated C++

    Aus 2000?



  • @HarteWare sagte in Destruktor für einfache Linked List, Speicherverwaltung:

    @mgaeckler

    Warnung 126 warning C4365: "Argument": Konvertierung von "int" in "unsigned int", signed/unsigned-Konflikt. C:\CRESD\Source\GAK_CLI\TOOLS\mirror.cpp 1459 1 mirror

    Na siehste, hättest da einen int statt unsigned genommen, wär die lästige Warnung nicht da :o)

    Ich nehme jetzt einfach mal an, daß Du nur einen Spaß machen wolltest.



  • @mgaeckler sagte in Destruktor für einfache Linked List, Speicherverwaltung:

    Warnung 126 warning C4365: "Argument": Konvertierung von "int" in "unsigned int", signed/unsigned-Konflikt

    Kommt bei uns im Code paar Millionen mal vor, third party libs nicht eingerechnet (Google achtet z.B. überhaupt nicht drauf). Da achtet keiner mehr drauf.



  • @Mechanics Das ist natürlich schlecht. Sollte nicht sein.



  • @mgaeckler sagte in Destruktor für einfache Linked List, Speicherverwaltung:

    @Swordfish Ja und? Wo siehst Du da einen Widerspruch?

    Probiers doch einfach aus inkl. Verifikation. Ich drück' dir alle drei Daumen die ich habe.



  • @Swordfish Ich sehe trotzdem keinen Widerspruch. Ich habe ja nicht behauptet, daß man IMMER unsigned nehmen soll.



  • @mgaeckler sagte in Destruktor für einfache Linked List, Speicherverwaltung:

    @Swordfish Ich sehe trotzdem keinen Widerspruch. Ich habe ja nicht behauptet, daß man IMMER unsigned nehmen soll.

    ließ es, god damnit!


Log in to reply