Programming - C Advanced Lists and Queues

 

   After talking about Basic Linked Lists and Queues that are implemented using them let's take a look today at more Advanced Lists and Queues. We will talk about Double Linked Lists, Circular Linked Lists and Priority Queues in C Language. If you want haven't seen it yet here the post I uploaded that explains the Basic Linked List Structures. Now, without further do, let's get started!

Double Linked Lists:

    As we already know a basic Linked Lists contains Nodes from which one called head points to all the Items of the List. Every Node has a pointer to the next Item in the List. Our struct was defined like that:

typedef struct Node{
    int val;
    struct Node *next;
}Node;

    All that changes from going into Double Linked Lists is that we also point to our previous Item. So, now our struct contains also a Pointer called prev like this:

typedef struct Node{
    int val;
    struct Node *next;
    struct Node *prev;
}Node;

    So, now we can find our previous Item in an much easier way and our Delete Function will become much easier and we will also don't need an Recursion to print our List backwards!

All the Functions that we used last time will work again, except that we now have to tweak some stuff on our prev pointer to! 


The Way we insert a new Node looks like this:

Node *nn;
// create our new node
nn = (Node*)malloc(sizeof(Node));
nn->val = val;
nn->next = NULL;
nn->prev = NULL;


Now let's take a look at all functions:

Node *insertFirst(Node *head, int val){
 Node *nn;
 // create our new node
 nn = (Node*)malloc(sizeof(Node));
 nn->val = val;
 nn->next = NULL;
 nn->prev = NULL;
 // check if list is empty
 if(head == NULL){
     // return pointer to nn
     return nn;
 }
 // set head to be our next pointer
 nn->next = head;
 // return pointer to nn
 return nn;  
}


Node *insertLast(Node *head, int val){
 Node *nn, *cur;
 // create our new node
 nn = (Node*)malloc(sizeof(Node));
 nn->val = val;
 nn->next = NULL;
 // check if list is empty
 if(head == NULL){
     // return pointer to nn
     return nn;
 }
 // set cur to point to our list
 cur = head;
 // use a while loop to find the last Item
 while(cur->next != NULL){
     // set cur to next Item
     cur = cur->next; 
 }
 // next of last Item will be our new node
 cur->next = nn;
 // prev of nn will be our cur pointer
 nn->prev = cur;
 // return head
 return head;    
}


DeleteFirst() doesn't change!


Node* deleteLast(Node *head){
 Node *cur;
 // check if list is empty
 if(head == NULL){
     // simply return it back after printing
     printf("Empty List!");
     return head;
 }
 // check if first Item is the only Item
 if(head->next == NULL){
     // make the list NULL
     return NULL;        
 }
 // set cur to point to our list
 cur = head;
 // use a while loop to find the last Item
 while(cur->next != NULL){
     // set cur to next Item
     cur = cur->next; 
 }
 // set the prev pointer's next pointer to NULL
 cur->prev->next = NULL;
 // return head
 return head;
}


Tweaking some things we can make the previous function work for specific value deletion like this:

Node* deleteVal(Node *head, int val){
 Node *cur;
 int found = 0;
 // check if list is empty
 if(head == NULL){
     // simply return it back after printing
     printf("Empty List!");
     return head;
 }
 // check if first Item is the only Item
 if(head->next == NULL){
     //check if value is the same
     if(head->val == val){
         return NULL;
     }       
     printf("%d was not found!\n", val);
     return head;    
 }
 // set cur to point to our list
 cur = head;
 // use a while loop to find the Item
 while(cur->next != NULL){
     // check val
     if(cur->val == val){
         found = 1;
         break;
     }
     // set cur to next Item
     cur = cur->next; 
 }
 // check if not found
 if(found == 0){
     printf("%d was not found!\n", val);
     return head;
 }   
 // set the prev pointer's next pointer 
 // to the next pointer of Node to be deleted
 cur->prev->next = cur->next;   
 // return head
 return head;
}


SearchList() doesn't change and we can do our Printing and Reverse Printing the same way we did before. We can also go to the last item and start going back for reverse printing!


Circular Linked Lists:

    A Circular List is a Linked List where the last Item points to the First Item and so we can go round and round. I won't go very deep into them, but to let you know it is pretty easy to insert cause when inserting first we set the last item to point to the item just inserted and when inserting last we set this item to point to our head.

    The problem comes in the functions is that we could iterate infinitely if we don't do it right. The best way I think is to check if the head and the current Item are the same in a do-while loop, so that it iterates the first time, but when we get to it again we will stop. This can work with every function we talked about in our Basic Linked List Tutorial. We could also make it be a Double Linked List, to make things easier in some parts (like deleting).


Priority Queues:

    We already know how to set up a Queue using Linked Lists and Arrays, cause we talked about them in previous posts. When going into priorities we will have to define what kind of priority we want to give. In Java we used a Priority Queue, for example, that putted the Items in priority using the alphabetic or natural ordering of the String Representations.

    We could do it in an similar way in C again, by having each Item inserted have a priority "number" (that doesn't have to be a variable, cause as we saw in Java we just used a variable of the Object itself) that puts the Item inserted in the right spot in the Queue directly or have the Queue sort itself after inserting using an ordering/sorting algorithm that puts the Items in order. 

    When getting an Item from the Queue we then get the Item that has the biggest priority by simply getting the Item in the front.

    Let's get into some Coding now. We will use an Linked List Implementation and our Node struct will contain an priority variable that we will declare when inserting it in the queue using our Enqueue function that I will leave for last. So, our structs look like this:

typedef struct Node{ 
 int val;
 int priority;
 struct Node *next;
}Node;

typedef struct Queue{
 Node *front;
 Node *rear;
}Queue;

 The dequeue and print functions will be exactly the same as last time.

int dequeue(Queue *Q){
 int val;
 // check if empty
 if(Q->front == NULL){
     return -1;
 }
 // get value in front
 val = Q->front->val;
 // check if one item inside
 if(Q->front == Q->rear){
     Q->front = Q->rear = NULL;
 }
 // basic case
 else{
     // make front point to next
     Q->front = Q->front->next;
 }
 //return the value 
 return val; 
}


void print(Queue Q){
 int val;
 // check if empty
 if(Q.front == NULL){
     printf("Queue is Empty!\n");
     return;
 }
 // call dequeue as long as there are items
 while((val= dequeue(&Q)) != -1){
     printf("%d ", val);
 }   
 printf("\n");
}

    Now into the new Stuff: Our Enqueue function will find the right spot by sorting our List based on priority after each insertion. To make it easier and faster we will insert our new Node at the Front and afterwards sort our Queue.

void enqueue(Queue *Q, int val, int priority){
    Node *cur, *nn, temp;
    // create new node
    nn = (Node*)malloc(sizeof(Node));
    nn->val = val;
    nn->priority = priority;
    nn->next = NULL;
    // check if empty
    if(Q->front == NULL){
 Q->front = Q->rear = nn;
 return;
    }
    // insert new Node at front
    nn->next = Q->front;
    Q->front = nn;
 
    // order using priorities
    cur = Q->front;
    while(cur->next != NULL){
 // check priorities
 if(cur->priority < cur->next->priority){
     // swap Node values and priorities
     temp = *cur;
     cur->val = cur->next->val;
     cur->priority = cur->next->priority;
     cur->next->val = temp.val;
     cur->next->priority = temp.priority;
 }
 cur = cur->next;
    }
}


Last but not least here a programm that uses those functions:

int main(){
 // initialize Queue
 Queue Q;
 Q.front = Q.rear = NULL;
 print(Q);
 // add 5 to queue
 enqueue(&Q, 5, 2);
 print(Q);
 // add 10 to queue
 enqueue(&Q, 10, 5);
 print(Q);
 // add 3 to queue
 enqueue(&Q, 3, 1);
 print(Q);
 // remove from queue
 int val;
 val = dequeue(&Q);
 if(val == -1){
     printf("Queue is Empty!\n");
 }
 else{
     printf("%d\n", val);
 }
 print(Q);       
}


That was the end of today's post. Hope you enjoyed it! :)

H2
H3
H4
3 columns
2 columns
1 column
3 Comments