Overview

I have a simple circularly linked list I was making for demonstration purposes (I know I should be using smart pointers, but this is a pedagogical exercise for memory and data structures).

Part of the process is to demonstrate recursion as well, and so all of the functions are written recursively.

I was having trouble when it came to freeing the memory from the circularly linked list.

Broken code

void CLL::clear() {
    if (!rear) { return; }

    clear(rear->next);
    rear = nullptr;
}

void CLL::clear(Node*& curr) {
    if (curr != rear) {
        clear(curr->next);
    }

    delete curr;
    curr = nullptr;
}

Code replacement (fixes broken code; unsure of why)

void CLL::clear() {
    if (!rear) { return; }

    clear(rear);
}

void CLL::clear(Node*& curr) {
    if (curr->next != rear) { // continue recursion if we're not at the end
        clear(curr->next);
    }

    delete curr;
    curr = nullptr;
}

GDB context

Breakpoint 1, CLL::clear (this=0x7fffffffdce8, curr=@0x55555556b6e8: 0x55555556b2b0) at CLL.cpp:36
36      if (curr != rear) {
(gdb) n
37          clear(curr->next);
(gdb) 
Breakpoint 1, CLL::clear (this=0x7fffffffdce8, curr=@0x55555556b2b8: 0x55555556b6e0) at CLL.cpp:36
36      if (curr != rear) {
(gdb) 
40      delete curr;
(gdb) 
41      curr = nullptr;
(gdb) 
42  }
(gdb) 
CLL::clear (this=0x7fffffffdce8, curr=@0x55555556b6e8: 0x8954fb37e656c2a4) at CLL.cpp:40
40      delete curr;
(gdb) 
Program received signal SIGSEGV, Segmentation fault.
0x00007ffff78a53fe in __GI___libc_free (mem=0x8954fb37e656c2a4) at ./malloc/malloc.c:3368
3368    ./malloc/malloc.c: No such file or directory.
(gdb)

Rest of code (for context)

CLL.cpp

#include "CLL.h"
#include <iostream>

using std::cout, std::endl;

// [DE]CONSTRUCTORS
CLL::~CLL() {
    clear();
}

// HELPER FUNCTIONS
void CLL::clear() {
    if (!rear) { return; }

    clear(rear->next);
    rear = nullptr;
}

void CLL::clear(Node*& curr) {
    if (curr != rear) {
        clear(curr->next);
    }

    delete curr;
    curr = nullptr;
}

void CLL::insert(int _data, size_t index) {
    if (!rear) {
        rear = new Node(_data);
        rear->next = rear;
    }   
    else { 
        insert(_data, index, rear->next);
    }   
}       
    
void CLL::insert(int _data, size_t index, Node*& curr) {
    // base case 1: insert after rear (this becomes the new rear)
    if ((index == 1) and (curr == rear))
    {
        rear->next = new Node(_data, rear->next);
        rear = rear->next;
    }
    // base case 2: insert before the rear
    else if (index == 0) {
        curr = new Node(_data, curr);
    }

    // recursive case
    else {
        insert(_data, index-1, curr->next);
    }
}

void CLL::display() const {
    display(rear->next);
    cout << "->..." << endl;
}

void CLL::display(const Node* const & curr) const {
    cout << curr->data;
    if (curr != rear) {
        cout << "->";
        display(curr->next);
    }
}

size_t CLL::size() const {
    if (!rear) { return 0u; }

    return size(rear->next);
}

size_t CLL::size(const Node* const & curr) const {
    if (curr == rear) {
        return 1;
    }
    else {
        return 1 + size(curr->next);
    }
}

CLL.h

#pragma once

#include <cstddef> //size_t

class CLL {
private:
    struct Node {
        int data;
        Node* next;

        Node(): data(0), next(nullptr) {}
        Node(int _data): data(_data), next(nullptr) {}
        Node(int _data, Node* _next):
            data(_data), next(_next) {}
    };  
        
    // HELPER FUNCTIONS
    void clear();
            
    // RECURSIVE FUNCTIONS
    void clear(Node*&);
    void insert(int, size_t, Node*&);
    void display(const Node* const &) const;
    size_t size(const Node* const &) const;
    
    Node* rear;
public:
    CLL(): rear(nullptr) {}
    CLL(const CLL &) = delete; // don't copy (for now)
    ~CLL();
    
    void insert(int, size_t);
    void display() const;
    size_t size() const;
};

main.cpp

#include "CLL.h"
#include <iostream>
#include <cstdlib> // rand(), srand(..)
#include <ctime> // time(..)
    
using std::cout, std::cerr, std::endl;
    
int main() {
    CLL list;

    srand(time(NULL));
    
    // insert randomly in list
    for (int n: {1,2}) { 
        size_t insert_index = rand() % (list.size() + 1);
        // output info
        cerr << "inserting " << n << "@" << insert_index;
        if (insert_index == list.size()) {
            cerr << " (rear)"; 
        }
        cerr << endl;
    
        list.insert(n, insert_index);
        list.display();
    }
 
    cout << '\n';
    list.display(); 
    cout << "The CLL has " << list.size() << " elements" << endl;

    return 0;
}

I tried changing the amount of data, but anything beyond one datum seems to break the code.

I think that the error has to do with order of deletion, seeing as how that's the only real difference from the original to the fixed solution. I'm not sure what causes it though.

Although the rear field gets deleted last in the fixed version, but is deleted first in the broken version, shouldn't the stack frames hold the proper addresses and free the memory correctly, regardless?

The call stack is

  clear();
   clear(rear->next);
     clear(rear->next->next);
      delete rear->next->next; [1]
      rear->next->next = nullptr
     delete rear->next; [2]
     rear->next = nullptr [3]

Note that rear->next->next points back to rear, so after you call delete rear->next->next and goes back to [2],[3], rear will point to already freed memory, when you try to delete rear->next or set rear->next to nullptr (curr = nullptr; in your code), you are actually access already freed memory.