Beginner Codes
C Beginner Codes
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! :)
C Language
Basics
Beginner Arrays
C Beginner Arrays
Pointers, Strings and Files
C Pointers, Strings and Files
Dynamic Memory Allocation
C Dynamic Memory Allocation
Structs and Switch Case
C Structs and Switch Case
Datastructures
Recursive Algorithms
C Recursive Algorithms
Linked Lists
C Linked Lists
Binary Trees
C Binary Trees
Queues using Arrays
C Queues using Arrays
Stacks using Arrays
C Stacks using Arrays
Queues using Linked Lists
C Queues using Linked Lists
Stacks using Linked Lists
C Stacks using Linked Lists
Advanced Lists and Queues
C Advanced Lists and Queues
Advanced Trees
C Advanced Trees
Stack-Queue Exercise using Dynamic Arrays
C Stack-Queue Exercise using Dynamic Arrays
Stack-Queue Exercise using Linked Lists
C Stack-Queue Exercise using Linked Lists
Hashtables with Chaining
C Hashtables with Chaining
Hashtables with Linear Probing
C Hashtables with Linear Probing
Other
Can I Run A Dual Monitor Setup
C Can I Run A Dual Monitor Setup
Function Comparison
C Function Comparison