Search code examples
clistdata-structuresqueuebsd

Why BSD queue.h LIST called a list?


My "mothertongue" is Java, and I need to write a project in C in educational purposes. I try to understand the queue.h library. In Java by default you add() an item to the end of the List, however in queue.hthere is only LIST_INSERT_HEAD macro that doesn't accept other members. In fact, a small test shows that it inserts to the HEAD (when traversing with LIST_FOREACH it goes from the last inserted element to the first). So, doen't this should be called FILO queue (that means a stack)?


Solution

  • List in Java corresponds to the List ADT: "an ordered sequence of values, where the same value may occur more than once".

    LIST in queue.h is also a List ADT, in which you can see the implementation details (it is implemented as a doubly linked list). It is LIFO, as the very queue.h file states (though quite murkily). And yes, one way to implement a Stack ADT is by using a linked list.