implement a Linked List Priority Queue in C

How would you go about implementing a priority queue using a linked list in C?

The typical linked list consists of head pointing to an element which points to another element(s), which eventually ends by NULL or the linked list's tail. Example:

(Linked List | Head) ----> (Element | Next) ----> (Element | Next) ----> Null

In the basic scenario, new elements are added to the list by using the First-In First-Out (add to the end of the list, remove from the front of the list) FIFO approach.

In my case however, a priority value must be taken into consideration. More specifically, each element can be assigned priority of 1, 2 or 3. Elements with the highest priority are added towards the front of the list while those with lower priority are added towards the back. Insertions into the list maintain the FIFO order of each priority.

So, if one is to enqueue the following elements one at a time:

a 3, b 1, c 2, d 3, e 2

The output should be: a 3, d 3, c 2, e 2, b 1 (ordered by priority as well as the order of being added instead of the standard First-In First-Out approach which disregards the priority).

Here is what I have, but it DOES NOT feature priority. How would you go about implementing a priority queue?

http://codepad.org/BMeuSgNBxd

One way would be to use a sorting/priority algorithm. Besides the algorithm, some of the major unknowns/confusion for me is how and where the priority would be stored, would it be within the actual element such as:

(Linked List | Head) ----> (a | 1 | Next) ----> (b | 2 | Next) ----> Null

or

  q_enqueue(&q, "a", "1");
  q_enqueue(&q, "b", "2");

and how would I go about comparing the priorities while working with the pointers to create the sorting开发者_StackOverflow中文版 algorithm.

If you have only three values of priority (or in more general - fixed range of priorities) why can't you implement three separate queues and write a wrapper functions that depending on the priority add/remove the element to certain queue?

Whenever you add/move an element within the list, using a sorting algorithm to reorder the elements in the list based on their priority. It may be slow, but it works.

You should consider implementing a double linked list.

Basically this is like a simple linked list, but there is also a tail node that points to the end of the list, and every element in the list has a pointer forwards and backwards in the list.

So high priority nodes get added to the front,and low priority nodes get added to the end. Both these operations are very efficient with this data structure.

I am not sure where priority 2 nodes get added :)

The overhead above a normal linked list should be negligible.

Doubly linked list - Wikipedia