Programming - C Advanced Lists and Queues
programming·@drifter1·
0.000 HBDProgramming - C Advanced Lists and Queues
<html>
<p> <img src="http://www.tutorialsteacher.com/Content/images/csharp/csharp-queue.png" width="460" height="221"/></p>
<p> 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 <strong>Double Linked Lists,</strong> <strong>Circular Linked Lists</strong> and <strong>Priority Queues</strong> in <strong>C Language</strong>. If you want haven't seen it yet <a href="https://steemit.com/programming/@drifter1/programming-c-linked-lists">here</a> the post I uploaded that explains the Basic Linked List Structures. Now, without further do, let's get started!</p>
<h1>Double Linked Lists:</h1>
<p> 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:</p>
<pre><code>typedef struct Node{</code></pre>
<pre><code> int val;</code></pre>
<pre><code> struct Node *next;</code></pre>
<pre><code>}Node;</code></pre>
<p> 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:</p>
<pre><code>typedef struct Node{</code></pre>
<pre><code> int val;</code></pre>
<pre><code> struct Node *next;</code></pre>
<pre><code> struct Node *prev;</code></pre>
<pre><code>}Node;</code></pre>
<p> 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!</p>
<p>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! </p>
<p><br></p>
<p>The Way we insert a new Node looks like this:</p>
<pre><code>Node *nn;</code></pre>
<pre><code>// create our new node</code></pre>
<pre><code>nn = (Node*)malloc(sizeof(Node));</code></pre>
<pre><code>nn->val = val;</code></pre>
<pre><code>nn->next = NULL;</code></pre>
<pre><code>nn->prev = NULL;</code></pre>
<p><br></p>
<p>Now let's take a look at all <strong>function</strong>s:</p>
<pre><code>Node *insertFirst(Node *head, int val){</code></pre>
<pre><code> Node *nn;</code></pre>
<pre><code> // create our new node</code></pre>
<pre><code> nn = (Node*)malloc(sizeof(Node));</code></pre>
<pre><code> nn->val = val;</code></pre>
<pre><code> nn->next = NULL;</code></pre>
<pre><code> nn->prev = NULL;</code></pre>
<pre><code> // check if list is empty</code></pre>
<pre><code> if(head == NULL){</code></pre>
<pre><code> // return pointer to nn</code></pre>
<pre><code> return nn;</code></pre>
<pre><code> }</code></pre>
<pre><code> // set head to be our next pointer</code></pre>
<pre><code> nn->next = head;</code></pre>
<pre><code> // return pointer to nn</code></pre>
<pre><code> return nn; </code></pre>
<pre><code>}</code></pre>
<p><br></p>
<pre><code>Node *insertLast(Node *head, int val){</code></pre>
<pre><code> Node *nn, *cur;</code></pre>
<pre><code> // create our new node</code></pre>
<pre><code> nn = (Node*)malloc(sizeof(Node));</code></pre>
<pre><code> nn->val = val;</code></pre>
<pre><code> nn->next = NULL;</code></pre>
<pre><code> // check if list is empty</code></pre>
<pre><code> if(head == NULL){</code></pre>
<pre><code> // return pointer to nn</code></pre>
<pre><code> return nn;</code></pre>
<pre><code> }</code></pre>
<pre><code> // set cur to point to our list</code></pre>
<pre><code> cur = head;</code></pre>
<pre><code> // use a while loop to find the last Item</code></pre>
<pre><code> while(cur->next != NULL){</code></pre>
<pre><code> // set cur to next Item</code></pre>
<pre><code> cur = cur->next; </code></pre>
<pre><code> }</code></pre>
<pre><code> // next of last Item will be our new node</code></pre>
<pre><code> cur->next = nn;</code></pre>
<pre><code> // prev of nn will be our cur pointer</code></pre>
<pre><code> nn->prev = cur;</code></pre>
<pre><code> // return head</code></pre>
<pre><code> return head; </code></pre>
<pre><code>}</code></pre>
<p><br></p>
<p>DeleteFirst() doesn't change!</p>
<p><br></p>
<pre><code>Node* deleteLast(Node *head){</code></pre>
<pre><code> Node *cur;</code></pre>
<pre><code> // check if list is empty</code></pre>
<pre><code> if(head == NULL){</code></pre>
<pre><code> // simply return it back after printing</code></pre>
<pre><code> printf("Empty List!");</code></pre>
<pre><code> return head;</code></pre>
<pre><code> }</code></pre>
<pre><code> // check if first Item is the only Item</code></pre>
<pre><code> if(head->next == NULL){</code></pre>
<pre><code> // make the list NULL</code></pre>
<pre><code> return NULL; </code></pre>
<pre><code> }</code></pre>
<pre><code> // set cur to point to our list</code></pre>
<pre><code> cur = head;</code></pre>
<pre><code> // use a while loop to find the last Item</code></pre>
<pre><code> while(cur->next != NULL){</code></pre>
<pre><code> // set cur to next Item</code></pre>
<pre><code> cur = cur->next; </code></pre>
<pre><code> }</code></pre>
<pre><code> // set the prev pointer's next pointer to NULL</code></pre>
<pre><code> cur->prev->next = NULL;</code></pre>
<pre><code> // return head</code></pre>
<pre><code> return head;</code></pre>
<pre><code>}</code></pre>
<p><br></p>
<p>Tweaking some things we can make the previous function work for specific value deletion like this:</p>
<pre><code>Node* deleteVal(Node *head, int val){</code></pre>
<pre><code> Node *cur;</code></pre>
<pre><code> int found = 0;</code></pre>
<pre><code> // check if list is empty</code></pre>
<pre><code> if(head == NULL){</code></pre>
<pre><code> // simply return it back after printing</code></pre>
<pre><code> printf("Empty List!");</code></pre>
<pre><code> return head;</code></pre>
<pre><code> }</code></pre>
<pre><code> // check if first Item is the only Item</code></pre>
<pre><code> if(head->next == NULL){</code></pre>
<pre><code> //check if value is the same</code></pre>
<pre><code> if(head->val == val){</code></pre>
<pre><code> return NULL;</code></pre>
<pre><code> } </code></pre>
<pre><code> printf("%d was not found!\n", val);</code></pre>
<pre><code> return head; </code></pre>
<pre><code> }</code></pre>
<pre><code> // set cur to point to our list</code></pre>
<pre><code> cur = head;</code></pre>
<pre><code> // use a while loop to find the Item</code></pre>
<pre><code> while(cur->next != NULL){</code></pre>
<pre><code> // check val</code></pre>
<pre><code> if(cur->val == val){</code></pre>
<pre><code> found = 1;</code></pre>
<pre><code> break;</code></pre>
<pre><code> }</code></pre>
<pre><code> // set cur to next Item</code></pre>
<pre><code> cur = cur->next; </code></pre>
<pre><code> }</code></pre>
<pre><code> // check if not found</code></pre>
<pre><code> if(found == 0){</code></pre>
<pre><code> printf("%d was not found!\n", val);</code></pre>
<pre><code> return head;</code></pre>
<pre><code> } </code></pre>
<pre><code> // set the prev pointer's next pointer </code></pre>
<pre><code> // to the next pointer of Node to be deleted</code></pre>
<pre><code> cur->prev->next = cur->next; </code></pre>
<pre><code> // return head</code></pre>
<pre><code> return head;</code></pre>
<pre><code>}</code></pre>
<p><br></p>
<p>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!</p>
<p><br></p>
<h1>Circular Linked Lists:</h1>
<p> 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.</p>
<p> 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).</p>
<p><br></p>
<h1>Priority Queues:</h1>
<p> 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.</p>
<p> 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. </p>
<p> 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.</p>
<p> 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:</p>
<pre><code>typedef struct Node{ </code></pre>
<pre><code> int val;</code></pre>
<pre><code> int priority;</code></pre>
<pre><code> struct Node *next;</code></pre>
<pre><code>}Node;</code></pre>
<pre><code><br></code></pre>
<pre><code>typedef struct Queue{</code></pre>
<pre><code> Node *front;</code></pre>
<pre><code> Node *rear;</code></pre>
<pre><code>}Queue;</code></pre>
<p> The dequeue and print functions will be exactly the same as last time.</p>
<pre><code>int dequeue(Queue *Q){</code></pre>
<pre><code> int val;</code></pre>
<pre><code> // check if empty</code></pre>
<pre><code> if(Q->front == NULL){</code></pre>
<pre><code> return -1;</code></pre>
<pre><code> }</code></pre>
<pre><code> // get value in front</code></pre>
<pre><code> val = Q->front->val;</code></pre>
<pre><code> // check if one item inside</code></pre>
<pre><code> if(Q->front == Q->rear){</code></pre>
<pre><code> Q->front = Q->rear = NULL;</code></pre>
<pre><code> }</code></pre>
<pre><code> // basic case</code></pre>
<pre><code> else{</code></pre>
<pre><code> // make front point to next</code></pre>
<pre><code> Q->front = Q->front->next;</code></pre>
<pre><code> }</code></pre>
<pre><code> //return the value </code></pre>
<pre><code> return val; </code></pre>
<pre><code>}</code></pre>
<p><br></p>
<pre><code>void print(Queue Q){</code></pre>
<pre><code> int val;</code></pre>
<pre><code> // check if empty</code></pre>
<pre><code> if(Q.front == NULL){</code></pre>
<pre><code> printf("Queue is Empty!\n");</code></pre>
<pre><code> return;</code></pre>
<pre><code> }</code></pre>
<pre><code> // call dequeue as long as there are items</code></pre>
<pre><code> while((val= dequeue(&Q)) != -1){</code></pre>
<pre><code> printf("%d ", val);</code></pre>
<pre><code> } </code></pre>
<pre><code> printf("\n");</code></pre>
<pre><code>}</code></pre>
<p> 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.</p>
<pre><code>void enqueue(Queue *Q, int val, int priority){</code></pre>
<pre><code> Node *cur, *nn, temp;</code></pre>
<pre><code> // create new node</code></pre>
<pre><code> nn = (Node*)malloc(sizeof(Node));</code></pre>
<pre><code> nn->val = val;</code></pre>
<pre><code> nn->priority = priority;</code></pre>
<pre><code> nn->next = NULL;</code></pre>
<pre><code> // check if empty</code></pre>
<pre><code> if(Q->front == NULL){</code></pre>
<pre><code> Q->front = Q->rear = nn;</code></pre>
<pre><code> return;</code></pre>
<pre><code> }</code></pre>
<pre><code> // insert new Node at front</code></pre>
<pre><code> nn->next = Q->front;</code></pre>
<pre><code> Q->front = nn;</code></pre>
<pre><code> </code></pre>
<pre><code> // order using priorities</code></pre>
<pre><code> cur = Q->front;</code></pre>
<pre><code> while(cur->next != NULL){</code></pre>
<pre><code> // check priorities</code></pre>
<pre><code> if(cur->priority < cur->next->priority){</code></pre>
<pre><code> // swap Node values and priorities</code></pre>
<pre><code> temp = *cur;</code></pre>
<pre><code> cur->val = cur->next->val;</code></pre>
<pre><code> cur->priority = cur->next->priority;</code></pre>
<pre><code> cur->next->val = temp.val;</code></pre>
<pre><code> cur->next->priority = temp.priority;</code></pre>
<pre><code> }</code></pre>
<pre><code> cur = cur->next;</code></pre>
<pre><code> }</code></pre>
<pre><code>}</code></pre>
<p><br></p>
<p>Last but not least here a programm that uses those functions:</p>
<pre><code>int main(){</code></pre>
<pre><code> // initialize Queue</code></pre>
<pre><code> Queue Q;</code></pre>
<pre><code> Q.front = Q.rear = NULL;</code></pre>
<pre><code> print(Q);</code></pre>
<pre><code> // add 5 to queue</code></pre>
<pre><code> enqueue(&Q, 5, 2);</code></pre>
<pre><code> print(Q);</code></pre>
<pre><code> // add 10 to queue</code></pre>
<pre><code> enqueue(&Q, 10, 5);</code></pre>
<pre><code> print(Q);</code></pre>
<pre><code> // add 3 to queue</code></pre>
<pre><code> enqueue(&Q, 3, 1);</code></pre>
<pre><code> print(Q);</code></pre>
<pre><code> // remove from queue</code></pre>
<pre><code> int val;</code></pre>
<pre><code> val = dequeue(&Q);</code></pre>
<pre><code> if(val == -1){</code></pre>
<pre><code> printf("Queue is Empty!\n");</code></pre>
<pre><code> }</code></pre>
<pre><code> else{</code></pre>
<pre><code> printf("%d\n", val);</code></pre>
<pre><code> }</code></pre>
<pre><code> print(Q); </code></pre>
<pre><code>}</code></pre>
<p><br></p>
<p>That was the end of today's post. Hope you enjoyed it! :)</p>
</html>👍 drifter1, pillowz, luisneira, anyx, kushed, stone1, steemychicken1, aizensou, stoner19, hagie, coinbar, lifeisawesome, positivity, swedoise, kingsmind, romedog, spg, ozchartart, ozmaster, steemizen, berniesanders, joseph, richman, kevinwong, fabio, knozaki2015, allasyummyfood, capitalism, thebluepanda, yoshiko, thisisbenbrick, sirwinchester, einsteinpotsdam, zahnspange, steemsquad, allesgruen, honeyscribe, dannystravels, jerryblanceton, timbernana, sherlockcupid, dark.horse, i-gordan, sunshinetraveler, freefuture, kinakomochi, biancajapan, pula78, altaq, aiporlanibenjez, adragnaphilmore, asparasjenna, bertaroyer, cherio, copherexilorme, cannizzozephieri, beyersduba, bezelllivintoni, alinesherwood, joykit, humphreyb, harmannmorgan, griglikbenack, dariasaponta, ivorybrys, giannicoangla, gubseribbotsona, julissaboeckmann, jemisondeku, haytonmomper, ganngenes, karliks, lindseycok, nellyrocks, meharbankert, metteserve, manzaneirajenna, lavonnebatlinerr, mccalliehart, leverhelgeq, nicolebh, roqueone, renafuam, ribblepascual, orourkepage, reevaweiden, ranskijenna, ranseydrink, purdieabrah, sherriechau, wendizero, seibsleskl131, smedleyobieby, scarfatojennaii, schlitzrhymes, voughtbrink, pharesim, aomura, smf, tomato-ghost, paulygg, neander-squirrel, thomasp, rapp, carlagonz, slowwalker, patrice, ebargains, strangerarray, someguy123, dexter-k, adept, wackou, xeldal, pkattera, arconite, gandalf, elgeko, cube48, oluwoleolaide, joey1996, woz.software,