1

when the destructor of 'class LL' ~LL() gets called for this circular singly linked-list, the program crashes instead of freeing up the heap space of the pointer. How can I solve this problem?

class Node {
public:
  int data;
  Node *next;
};

class LL {
private:
  Node *head, *tail;

public:
  LL() {
    head = NULL;
    tail = NULL;
  }
  // destructor
  ~LL() {
    Node *p = head;
    while (p->next != head) {
      p = p->next;
    }

    while (p != head) {
      p->next = head->next;
      delete head;
      head = p->next;
    }

    if (p == head) {
      delete head;
      head = nullptr;
    }
  }

  // circular singly Linked list

  void createLL() {
    int n, x;
    cin >> n;

    for (int i = 0; i < n; i++) {
      cin >> x;

      Node *t = new Node;
      t->data = x;
      t->next = NULL;

      if (head == NULL) {
        head = tail = t;
      } else {
        tail->next = t;
        tail = t;
      }
    }
    tail->next = head;
  }
t.niese
  • 39,256
  • 9
  • 74
  • 101
Adnan Sparrow
  • 25
  • 2
  • 8
  • 3
    Try to run your program in a debugger and step line by line through your code. What's the error message? What's the stack trace after the crash? – Thomas Sablik Jun 17 '20 at 18:22
  • Also draw pictures. Nothing helps to visualize what should be going on in a linked list quite like pictures. The pictures then serve as your expected when stepping through with the debugger. As soon as you catch the program doing something you didn't draw, you've found a bug. – user4581301 Jun 17 '20 at 18:24
  • If its a singley linked circular list... why do you have a `tail` member? – Mooing Duck Jun 17 '20 at 18:36
  • 1
    First of all, you don't need `head` if a list is circular - it's _always_ `head == tail->next` if both exist, or else both are `NULL`. – CiaPan Jun 17 '20 at 18:39
  • 1
    @MooingDuck The tail pointer is necessary for _append_ to not scan the whole list. – CiaPan Jun 17 '20 at 18:41
  • 2
    @CiaPan No it's not. The list is circular. You use one of: head, tail, or sentinal. You do not need more than one. – sweenish Jun 17 '20 at 18:50
  • @sweenish Haven't you forgotten the list is singly linked, i.e. unidirectional? If you have the head pointer only, you'll be unable to step back from head node to the tail node, so you need to iterate around the whole circle to append a new node at the end of a list. – CiaPan Jun 17 '20 at 19:34
  • @armagedescu That's what I wrote [above](https://stackoverflow.com/questions/62435720/destructor-for-circular-linked-list-in-c#comment110422185_62435720), isn't it? – CiaPan Jun 17 '20 at 19:51

3 Answers3

1

There are a few issues with the linked list.

  1. The linked list's destructor assumes that head isn't null, when there is a possibility that it could be. Make sure to check that head isn't null before trying to clean up memory. Once that is done, it looks like your original destructor should work.
  2. The function createLL will invoke undefined behavior if the user enters a size less than or equal to 0. Specifically this line tail->next = head;
  3. TreateLL is a misnomer as it doesn't actually 'create' a new list in the expected sense. The contents aren't cleared, and thus n elements are appended to the end of the current list.
  4. Also, a circularly linked list can be created with just a single tail pointer.

However, getting your implementation of a circular linked list to work looks like this

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
};
class LL {
private:
    Node* head, * tail;
public:
    LL() : head(nullptr),
        tail(nullptr) {
    }
    ~LL() {
        if (head) {
            Node* p = tail;

            while (p != head) {
                p->next = head->next;
                delete head;
                head = p->next;
            }
            if (p == head) {
                delete head;
                head = nullptr;
            }
        }
    }

    void storeUserInput() {
        int n, x;
        cin >> n;
        if (n <= 0) {
            return; //no input to retrieve.
        }
        for (int i = 0; i < n; i++) {
            cin >> x;
            Node* t = new Node;
            t->data = x;
            t->next = nullptr;

            if (head == nullptr) {
                head = tail = t;
            }
            else {
                tail->next = t;
                tail = t;
            }
        }
        tail->next = head;
    }

};
int main() {
    LL l;
    l.storeUserInput();

    char response;
    std::cin >> response;
}

It seems that you have access C++ 11 or above compiler, if so then you should be using nullptr in place of NULL as it is a definitive pointer type. See more here

Rabster
  • 933
  • 1
  • 7
  • 11
0

You can do it in two steps:

  • Make the list non-circular. This has two sub-steps:
    • Detect the loop. There are published algorithms to do this. Edit: Your list has a tail pointer, so there is no need to search for it in your case.
    • Point the back referencing node to null (or sentinel)
  • Delete the list which is now non-circular in a loop. This is trivial.
eerorika
  • 232,697
  • 12
  • 197
  • 326
  • 2
    Also, he doesn't need to make it non-circular. He can just repeatedly delete `head` until the list is empty. – Mooing Duck Jun 17 '20 at 18:45
  • 1
    @MooingDuck But then they would have to update tail->next on every deletion so that it isn't left dangling. Faster to set next it first, and look for what you set it to. – eerorika Jun 17 '20 at 18:53
0

While trying to delete in a loop your circular reference will lead to deleted memory and will have undefined behavior. So first consider breaking the circulatiry:

tail->next = 0;

Then delete in a loop

Node* p = head;
while(p)
{
    Node* temp = p;
    p = p->next;
    delete temp;
}

By the way. tail->next will always point to the head. So you always will have both, the head and the tail in the same pointer. So you can clean the memory like this:

Node* p = tail->next; //this is head
tail->next = 0;
while(p)
{
    Node* temp = p;
    p = p->next;
    delete temp;
}
armagedescu
  • 1,758
  • 2
  • 20
  • 31