C/C++: how to clear a linked circular list

| category: Programming | author: st
Tags: ,

In the case of linked circular list you need to add some checks to avoid memory corruption.

Full example (compiled OK with GCC 8.x)

#include <iostream>
#include <cstdlib>

struct Node
{
    Node(Node* prev, int val)
        : prev(prev), next(NULL), value(val)
    { }
    Node *prev, *next;
    int value;
};

void clear_list(Node*& head)
{
    if (head != NULL)
    {
        Node* curr = head->next;
        while (curr != NULL && curr != head)
        {
            std::cout << "Deleting " << curr->value << std::endl;
            Node* temp = curr;
            curr = curr->next;
            delete temp;
        };
        delete head;
        head = NULL;
    }
}

void print_list(Node*& head)
{
    if (head != NULL)
    {
        Node* curr = head;
        do
        {
            std::cout << (curr == head ? "Head: " : "") << curr->value << std::endl;
            curr = curr->next;
        } while (curr != NULL && curr != head);
    }
}

int main()
{
    Node* head = new Node(NULL, 0);
    Node* curr = head;
    for (int i = 1; i <= 10; i++)
    {
        Node* prev = curr;
        curr = new Node(prev, i);
        prev->next = curr;
    }
    // Link end to head
    curr->next = head;
    //
    print_list(head);
    clear_list(head);
    print_list(head);
}

Result

Head: 0
1
2
3
4
5
6
7
8
9
10

Deleting 1
Deleting 2
Deleting 3
Deleting 4
Deleting 5
Deleting 6
Deleting 7
Deleting 8
Deleting 9
Deleting 10

blog comments powered by Disqus