help with linked lists implementation

Question

Hi, 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?

Answer 1

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;  
}

Answer 2

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.

Answer 3

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;
 }