1

I am currently writing a C code for a doubly linked list(dll) around which I want to write wrapers for implementing stack, queues etc. instead of writing separate codes for all of them.

I'll be using void * for making it possible for the doubly linked list to work with any data type. The idea is basically the same as this implementation of stack using pointers in my github.

I am thinking of 2 different designs

  • Placing the size of elements alongwith the maintenance data. That would make coding easier but any instance of dll would be able to use only a particular data type.
  • Placing the size of element in the nodes. That would make it more general but I have concerns whether this approach would be easier to use?

This is the confusion that I wanted to clear before implementing any particular one. If there is any confusion regarding what I am trying to implement then please ask and I'll clarify.

  • Switching to STL and C++ is not on the menu, right? – Deer Hunter Aug 11 '13 at 17:00
  • @DeerHunter Currently no. – Aseem Bansal Aug 11 '13 at 17:02
  • 2
    You do realize that implementing a stack, queues, etc around doubly linked lists on average performs worse than implementing the same around arrays that get reallocated when they get too big? – btilly Aug 11 '13 at 19:38
  • @btilly Worse than array implementations? Why? I understand that it will be worse than implementing them using pointers directly but worse than array implementations? Delete operations would be worse in case of array implementation because of shifting all elements. Wouldn't they? – Aseem Bansal Aug 12 '13 at 6:38
  • @AseemBansal It has to do with saving space (because of no pointers) and locality of reference. As for the shift problem, just keep track of where the front of the list is. Then a delete can be done by just incrementing that counter. – btilly Aug 12 '13 at 17:31
2

Let me start by answering your question:

Storing the element size per-node or per-list isn't going to make the code any more or less complex one way or the other. The only real difference will be that anyone calling to add a node will have to pass a size once or each time, and the amount of storage required for each node may grow by an extra size_t's worth of bytes. The tradeoff between using less memory and having less flexibility versus using more memory and having more flexibility is something you'd have to evaluate on a case-by-case basis.

Let me finish by suggesting an alternative:

If you're implementing this to be general-purpose tools along the lines of the STL or Java's generic containers, I would suggest taking a completely different tack and not trying to do anything with the pointers you're given. Just store them in your list and return them as it's traversed.

Your allocate-and-copy approach goes on the assumption that what's being stored are simple structures, which has a couple of pitfalls:

  • My structure may have additional pointers to allocated memory. If I'm using your list as primary storage for my data and you take it upon yourself to free() it when I call your cleanup() function, there's no opportunity for me to free any of the additional memory unless I traverse the entire thing beforehand and do my own cleaning up. If that's going to be the case, I might as well just do a traversal and remove the nodes one at a time. You could work around this by providing a disposal hook, which you'd call anytime you wanted to de-allocate a node.

  • The pointer I hand you may not be a pointer to a structure. For example, I may have a large block of memory and want to store a list of place markers or something which involves simply pointing at various places in the block. Your implementation requires that I give you a place to copy data from/to during push, pop and peek operations. I'd have to define another structure with a single member to hold my pointer value. That's awkward and inconvenient. (You could, however, write a wrapper that does allocate-and-copy and uses the pointers-only implementation.)

  • "I would suggest taking a completely different tack and not trying to do anything with the pointers you're given." - What do you mean by not doing anything with the pointers? The void * for the information? What should I not do? Not store them? I am not sure what you meant by this. Good point about your nodes having additional allocated memory. Hadn't considered that. How about using a separate function for freeing the nodes along the line of compare function used in qsort and bsearch functions in stdlib.h? – Aseem Bansal Aug 12 '13 at 6:57
  • I am not sure about your second suggestion. The pointer has to be of something. Otherwise what are you handing my implementation via the function calls? My implementation requires you to pass a pointer to the memory and the size of the the memory. It does not require you to give any other space. I'll be using memcpy so no need for defining any structure because memcpy handles memory as memory not as struct. – Aseem Bansal Aug 12 '13 at 7:00
  • @AseemBansal: I meant don't try to allocate more memory and copying what was pointed at into it, just store the pointer itself. A qsort()-style function to free the value is exactly what I was talking about, although you still have to handle the case in my second suggestion where there isn't anything for you to copy. – Blrfl Aug 12 '13 at 12:17
  • I stored the pointer itself in the stack implementation whose link I provided. Can you elaborate the second case. I still don't understand what you are saying in that. Can you give an example? – Aseem Bansal Aug 12 '13 at 13:17
  • @AseemBansal: You don't store the pointer, you allocate new memory (line 33) and copy what was pointed to into that memory (line 48). That's not the same as simply taking the pointer value passed in and storing it. – Blrfl Aug 12 '13 at 14:15
2

Perhaps you should take a look at the intrusive linked list implementation used in the Linux kernel. The source can be browsed here.

An intrusive design has the advantage that any type can be placed into a list just by including a list element in the structure definition.

Disadvantages include slightly more cumbersome syntax (a matter of personal preference, of course) and the requirement to include multiple members of the same type when your data needs to go into more than one list.

Intrusive lists are mostly useful when you only need a small number of lists and especially when your module/app are focused on adding and removing nodes from one list. A different design might be more suitable if your code needs to deal with local or disposable lists. The former consideration is true for most uses of lists in the kernel.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.