CODEWITHSUNDEEP
c++memorylinked-listallocation
zebraman
zebraman

Reputation: 163

Linked lists implementation issue

I'm trying to make a Stack using an underlying linked list structure.

Maybe I'm wrong, but I'm having trouble with the remove() function.

int Stack::remove(){  
  node* victim = new node;  
  int popped;  
  popped = top->element;  
  victim = top;
  top = victim->next;  
  delete victim;  
  return popped;  
}

I'm getting glibc dectecting

double free or corruption (out);

Since I'm allocating new memory with victim, don't I have to delete victim, or is that something I don't have to worry about?

Upvotes: 0

Views: 147

Answers (3)

JonH
JonH

Reputation: 33163

A stack is much like a bunch of dishes that are being washed and set on top of one another. That is the first one in is the last one out (FILO data type). That is if your stack read in 2, 7, 8 then it would appear as :

8

7

2

That is first the 2 is placed in the stack, followed by the 7 and then by the 8. If you want to remove or pop the stack you need to move the head of the pointer. Your code looks a bit strange to me...

int Stack::remove()
 {
  int datum;      //to store the popped value
  node* temp=head;  //assign pointer to head of list
  datum = temp->data; //grab the data value stored at the head (or temp since they carry same reference)
  head = temp->next; //move the head pointer (in our example now it points to 7)
  delete temp;
  return datum;
 }

Upvotes: 2

Nikolai Fetissov
Nikolai Fetissov

Reputation: 84189

You don't need to allocate a node for victim. Just assign the top of the stack to it and, if it's not null, set top to its next pointer, retrieve the value from victim, and then deallocate the victim.

It's not actually a corruption, but a memory leak - you are allocating a node, and then override that pointer with victim = top; thus losing track of just allocated memory.

Upvotes: 1

Max Shawabkeh
Max Shawabkeh

Reputation: 38643

There's no reason to allocate heap memory in a remove() method as you are doing with victim. What you want is:

int Stack::remove(){  
  node* new_top = top->next;
  int popped = top->element;

  delete top;  
  top = new_top;

  return popped;  
}

Upvotes: 1

Related Questions