linked list without free() in pop()

Question

I looked through many examples of singly linked list, which works as stack. They have in common the following: They always use free on popped item in pop() function, for example:

struct Node  
{  
 struct Node *Next;  
}*Head;  

void pop()  
{  
 struct Node *cur_ptr=Head;  
   ....
   Head = Head->Next;
   // do something with cur_ptr
   free(cur_ptr);  
   ....
 }   

Do I always need to use that rule? Can I pop item from list without free item in pop function? What I want achieve is to allocate list only one time when program starts and avoid deallocating and allocating memory in every time I call pop, push function. I want pop item, use item and push it (in other part of program) again to list for reuse. Is there something wrong with this approach?

Thanks i advance for your opinions and help.

Answer 1

You must make sure to free the memory allocated when you don't need them anymore, that's the point.

If, by any chance, you lose the reference to a dynamically allocated address without freeing it then you'll have a memory leak, eh:

void pop() {
  // get element from stack
  // use it
  // not call free
}

This will generate a leak if you don't store the address of the popped item anywhere.

If you want to reuse the allocated items then you are free to do it, and in this case you shouldn't free them, eg:

  void push() {
    struct Node *ptr = pop_unused_node();
    if (!ptr) // if no unused node is found then we need a new one
      ptr = malloc(sizeof(struct Node));
    *ptr = data;
    push(ptr);
  }

  void pop() {
    struct Node *ptr = pop();
    // use data
    push_unused_node(ptr);
  }

  void clearup() {
    for each node in unused list
      free(node);
    for each node in stack
      free(node);
  }

Answer 2

I would hope that all of the implementations you've looked at also allocate the node in push().

Of course you can make your own pop work any way you want; so long as you don't neglect to free Nodes when you're done with them.

Answer 3

The reason why pop() generally releases memory is because it a traditional sense the pop() operation is the last time that the linked list will have the ability to "see" an element.

Most list implementations are not intrusive, so you store some data type that you know about into a list, but the internal details of the list itself are not known. In this method, it makes sense for the list in those implementations the "housekeeping details" for that object will generally be allocated in push(), making pop() the logical place for them to be freed.

Since users may want to inspect the "next" element (without popping it off the list) most implementations have a front() (or similar) member function that allows for inspecting the next value, and pop() simply removes that item (and has no return value).

An intrusive data structure puts more constraints on what can be stored within it, but also gives more flexibility in terms of manual memory management (if that's what you're after).

Answer 4

Why would you not want to deallocate the memory? If you don't free up the memory then you'll ultimately leak memory!

Also, you should prefer new to free.

And, if you want to be all modern and C++'ish then you should think about using std::stack.

Answer 5

The reason all the implementations you've seen free when they pop a value is because they are responsible for that location in memory. If you allocate anything, it is your job to deallocate.

But this is programming. The computer will do whatever you tell it to, so if you feel this works better for you, do it. You can implement your own linked list class without memory allocation or deallocation. I certainly wouldn't recommend it, as I think you'll run into more problems with this than you would if you just let the list class allocate and deallocate like it was meant to, but, again, it's all up to you.