Search code examples
c++memorylinked-listallocation

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?

Solution

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