1

I have been trying to write a shortest path algorithm, dijkstras algorithm, finding the shortest path for the first two vertices works just fine. I run into the problem while trying to clear a linked list and a priority queue.

class llNode {
public:
    int id;
    int source;
    int weight;
    llNode* next;
    llNode(int key, int distance, int from) {
        id=key;
        weight=distance;
        source=from;
        next = NULL;
    }
};


class lList {
private:
    llNode* root;
    llNode* end;

    void clearAll(llNode* toClear);


public:
    lList() {
        root = NULL;
    }

    void add(llNode* toAdd) {
        if ( root == NULL) {
            root = toAdd;
            end = toAdd;
            return;
        }

        end->next = toAdd;
        end=end->next;
    }

    bool isFound(int key) {
        for(llNode* ii= root; ii != NULL ; ii=ii->next) {
            if ( ii->id == key) {
                return true;
            }
        }

        return false;
    }

    void clearAll();

};

void lList::clearAll() {
clearAll(root);
}

void lList::clearAll(llNode* toClear) {
if(toClear == NULL) {
    return;
}

clearAll(toClear->next);

toClear=NULL;

}

Along with these clear methods I tried to simply set root to NULL and I also tried traversing through the list and using the delete on each element. I am having to luck with any of these methods. Root keeps getting set to an invalid location and I get access violation errors.

Is there something simple that I am just not seeing? How would I go about deleting every element from a linked list?

braX
  • 11,506
  • 5
  • 20
  • 33
Beamer180
  • 1,501
  • 5
  • 19
  • 25

2 Answers2

5

You need to go over each element and delete it Pseudo Code

Set pointer to root
While(pointer !=null)
{
  temp=pointer->next;
  delete[] pointer;
  pointer = temp;
}
Pepe
  • 6,360
  • 5
  • 27
  • 29
-3

Setting root to NULL will delete the whole list.

void lList::clearAll() {
     root = NULL;
}

You said you tried this. How is your access violation happening in this scenario?

Beware: my code probably contains a memory leak! You will probably want to walk through the list and deallocate each item, unless their memory is recovered using some other mechanism.

Keith Randall
  • 22,985
  • 2
  • 35
  • 54
  • How does setting root to NULL delete the list! – Pepe Apr 06 '12 at 21:32
  • It makes the list empty. As in `isFound` will return `false` for any input. – Keith Randall Apr 06 '12 at 21:35
  • 7
    This is absolutely the wrong answer. You've left dangling pointers and memory leaks and all sorts of nasty stuff here just by losing a reference to the root of your list, not to mention the word "delete" is incorrect. You've more precisely LOST your list – devshorts Apr 06 '12 at 21:36
  • 1
    The OP's problem is an access violation, not a memory leak. Let's try to solve that problem first before we fix everything else that's wrong. In any case, until someone shows me the allocation point for `llNode`s, I can't solve the memory leak correctly. – Keith Randall Apr 06 '12 at 21:38
  • You're right, the OP is about an access violation, however to say that the right way to delete a list is by dropping the root node isn't correct and leads to bad practices and future issues down the road. – devshorts Apr 06 '12 at 21:56
  • @devshorts: it all depends on how `llNode`s are allocated, and in particular who is responsible for deleting them. I'm a fan of keeping allocations and deletes together, which means I don't like having this code `delete` the `llNode`s because it didn't `new` them. The caller should handle that, or it should be explicitly delegated to this code as part of the API. Maybe the caller allocated a chunk of them with `new[]`? You can't do it right without making assumptions about code we can't see. That's what my Beware: comment is about. – Keith Randall Apr 06 '12 at 22:09
  • You're right, you should keep allocation and deleting localized, HOWEVER, dropping the root means you've lost the rest of your list. That's the problem. – devshorts Apr 06 '12 at 22:20
  • @devshorts: *this* code has lost the rest of the list. That doesn't mean the caller has lost all references. If the caller has delegated deletion to this class, then yes, you need to walk the list and delete all the elements. But maybe the caller has some statically allocated `llNode`s? Maybe they were allocated in a memory pool and that will be released after he's done using the list? Maybe the `llNode` is just a field in a larger structure, and those structures are kept in some other data structure? The possibilities are endless... – Keith Randall Apr 06 '12 at 22:27
  • My point is that he definitely has to worry about deallocation, but given the code I've seen I can't tell him how to do that. I can just warn him that he needs to think about it. – Keith Randall Apr 06 '12 at 22:28