I want to make a queue using linked lists. There are numerous algorithms out there for that. But what i'm curious in is how to make a relative priority queue.
Maybe there is a special name for this type of queue, but i don't know it, and i haven't had any luck googling for the solution.
Anyways, let's say i have this struct, which will represent the Node of my list.
struct Node {
int value;
Node* next;
}
if i want to create a priority queue (where the element with the least value is first), when i insert for example 5 7 1 8 2, my list should look like this:
1 -> 2 -> 5 -> 7 -> 8
It's not really hard to implement that. What i want to do is - when i insert the first element, other elements should have value relative to the previous element. So, in my example, the list/queue would contain the following values:
1 -> 1 -> 3 -> 2 -> 1
I'm not really sure how i would implement that? Would the following idea be applicable:
in the Node struct i add another field, which would represent the original value. i find the position of the node i'm inserting the same way i would do when creating an ordinary linked list, and then i just say
temp->value = temp->originalValue - previous->originalValue;