C# || Remove Linked List Elements – How To Remove All Target Linked List Elements Using C#

The following is a module with functions which demonstrates how to remove all target linked list elements using C#.

1. Remove Elements – Problem Statement

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

Example 1:

``` Input: head = [1,2,6,3,4,5,6], val = 6 Output: [1,2,3,4,5] ```

Example 2:

``` Input: head = [], val = 1 Output: [] ```

Example 3:

``` Input: head = [7,7,7,7], val = 7 Output: [] ```

2. Remove Elements – Solution

The following is a solution which demonstrates how to remove all target linked list elements.

``` 2. Remove Elements - Solution C# // ============================================================================ // Author: Kenneth Perkins // Date: Apr 2, 2022 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to remove all target linked list elements // ============================================================================ /** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */ public class Solution { public ListNode RemoveElements(ListNode head, int val) { var ptr = head; // Loop through data checking to see if the next node equals the target value while (ptr != null && ptr.next != null) { // If the next node value is the target value, set the next node // to point to the one after it if (ptr.next.val == val) { ptr.next = ptr.next.next; } else { // Advance to the next node ptr = ptr.next; } } // If the head equals the target value, advance to the next if (head != null && head.val == val) { head = head.next; } return head; } }// http://programmingnotes.org/ 12345678910111213141516171819202122232425262728293031323334353637383940414243 // ============================================================================//    Author: Kenneth Perkins//    Date:   Apr 2, 2022//    Taken From: http://programmingnotes.org///    File:  Solution.cs//    Description: Demonstrates how to remove all target linked list elements// ============================================================================/** * Definition for singly-linked list. * public class ListNode { *     public int val; *     public ListNode next; *     public ListNode(int val=0, ListNode next=null) { *         this.val = val; *         this.next = next; *     } * } */public class Solution {    public ListNode RemoveElements(ListNode head, int val) {        var ptr = head;         // Loop through data checking to see if the next node equals the target value        while (ptr != null && ptr.next != null) {             // If the next node value is the target value, set the next node            // to point to the one after it            if (ptr.next.val == val) {                ptr.next = ptr.next.next;            } else {                // Advance to the next node                ptr = ptr.next;            }        }         // If the head equals the target value, advance to the next        if (head != null && head.val == val) {            head = head.next;        }         return head;    }}// http://programmingnotes.org/ ```

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

``` [1,2,3,4,5] [] [] ```

C# || How To Flatten A Multilevel Doubly Linked List Using C#

The following is a module with functions which demonstrates how to flatten a doubly linked list using C#.

1. Flatten – Problem Statement

You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.

Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.

Example 1:

``` Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12] Output: [1,2,3,7,8,11,12,9,10,4,5,6] Explanation:```

``` ```

```The multilevel linked list in the input is as follows: ```

After flattening the multilevel linked list it becomes:

Example 2:

``` Input: head = [1,2,null,3] Output: [1,3,2] Explanation:```

``` The input multilevel linked list is as follows: ```

``` 1---2---NULL | 3---NULL ```

Example 3:

``` Input: head = [] Output: [] ```

2. Flatten – Solution

The following are two solutions which demonstrates how to flatten a doubly linked list.

Iterative

``` 2. Flatten Iterative - Solution C# // ============================================================================ // Author: Kenneth Perkins // Date: Oct 30, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to flatten a doubly linked list // ============================================================================ /* // Definition for a Node. public class Node { public int val; public Node prev; public Node next; public Node child; } */ public class Solution { public Node Flatten(Node head) { var current = head; var stack = new Stack<Node>(); // Loop through nodes while (current != null) { // Check to see if node has child if (current.child != null) { // If current node has a next node, save to stack // so we can reconnect it to the tail // of the child node later if (current.next != null) { stack.Push(current.next); } // Set the next node as the child, // we will now iterate down this path current.next = current.child; // Set the previous node as the current current.next.prev = current; // Set child to null current.child = null; } else if (current.next == null) { // Reconnect node at the top of the // stack to the tail child node if (stack.Count > 0) { // Set the next node as the reconnected node, // we will now iterate down this path current.next = stack.Pop(); current.next.prev = current; } } current = current.next; } return head; } }// http://programmingnotes.org/ 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859 // ============================================================================//    Author: Kenneth Perkins//    Date:   Oct 30, 2021//    Taken From: http://programmingnotes.org///    File:  Solution.cs//    Description: Demonstrates how to flatten a doubly linked list// ============================================================================/*// Definition for a Node.public class Node {    public int val;    public Node prev;    public Node next;    public Node child;}*/public class Solution {    public Node Flatten(Node head) {        var current = head;        var stack = new Stack<Node>();         // Loop through nodes        while (current != null) {             // Check to see if node has child            if (current.child != null) {                // If current node has a next node, save to stack                // so we can reconnect it to the tail                // of the child node later                if (current.next != null) {                    stack.Push(current.next);                }                 // Set the next node as the child,                // we will now iterate down this path                current.next = current.child;                 // Set the previous node as the current                current.next.prev = current;                 // Set child to null                current.child = null;             } else if (current.next == null) {                // Reconnect node at the top of the                // stack to the tail child node                if (stack.Count > 0) {                    // Set the next node as the reconnected node,                    // we will now iterate down this path                    current.next = stack.Pop();                    current.next.prev = current;                }            }            current = current.next;        }         return head;    }}// http://programmingnotes.org/ ```

Recursive

``` 2. Flatten Recursive - Solution C# // ============================================================================ // Author: Kenneth Perkins // Date: Oct 30, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to flatten a doubly linked list // ============================================================================ /* // Definition for a Node. public class Node { public int val; public Node prev; public Node next; public Node child; } */ public class Solution { public Node Flatten(Node head) { Flatten(head, null); return head; } private Node Flatten(Node current, Node previous) { if (current == null) { return previous; } // If previous node exists, set the next and previous values if (previous != null) { previous.next = current; current.prev = previous; } // Save the next node so we can reconnect it to the tail // of the child node later var next = current.next; // Traverse down child path. // If children exist, this returns the last child for the current node var tail = Flatten(current.child, current); // Child path has been explored, set to null current.child = null; // Reconnect the next node to the tail child node return Flatten(next, tail); } }// http://programmingnotes.org/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748 // ============================================================================//    Author: Kenneth Perkins//    Date:   Oct 30, 2021//    Taken From: http://programmingnotes.org///    File:  Solution.cs//    Description: Demonstrates how to flatten a doubly linked list// ============================================================================/*// Definition for a Node.public class Node {    public int val;    public Node prev;    public Node next;    public Node child;}*/public class Solution {    public Node Flatten(Node head) {        Flatten(head, null);        return head;    }     private Node Flatten(Node current, Node previous) {        if (current == null) {            return previous;        }         // If previous node exists, set the next and previous values        if (previous != null) {            previous.next = current;            current.prev = previous;        }         // Save the next node so we can reconnect it to the tail        // of the child node later        var next = current.next;         // Traverse down child path.        // If children exist, this returns the last child for the current node        var tail = Flatten(current.child, current);         // Child path has been explored, set to null        current.child = null;         // Reconnect the next node to the tail child node        return Flatten(next, tail);    }}// http://programmingnotes.org/ ```

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

``` [1,2,3,7,8,11,12,9,10,4,5,6] [1,3,2] [] ```

C++ || Snippet â€“ Simple Linked List Using Delete, Insert, & Display Functions

The following is sample code for a simple linked list, which implements the following functions: “Delete, Insert, and Display.”

The sample code provided on this page is a stripped down version of a more robust linked list class which was previously discussed on this site. Sample code for that can be found here.

It is recommended you check that out as the functions implemented within that class are very useful.

``` Simple Linked List C++ // ============================================================================ // Author: Kenneth Perkins // Date: Aug 18, 2012 // Taken From: http://programmingnotes.org/ // File: SimpleList.cpp // Description: Demonstrates the use of a simple linked list. // ============================================================================ #include <iostream> #include <string> using namespace std; struct node { /* -- you can use different data types here -- instead of just a string char letter; int number; double fNumber; */ string name; node* next; }; // global variables // this is the front of the list node* head = NULL; // function prototype void Insert(string info); void Delete(string info); void Display(); void DestroyList(); int main() { // if you want to insert data into the list // this is one way you can do it, using a 'temp' pointer node* temp = new node; temp->name = "My Programming Notes"; temp->next = NULL; // set the head node to the data thats in the 'temp' pointer head = temp; // display data to the screen cout << head->name <<endl<<endl; // use the insert function to add new data to the list // NOTE: you could have also used the 'insert' function ^ above // to place data into the list Insert("Is An Awesome Site!"); // insert more data into the list Insert("August"); Display(); // delete the selected text from the list Delete("August"); Display(); // destroy the current pointers in the list // after you are finished using them DestroyList(); return 0; }// end of main void Insert(string info) { node* newItem = new node; newItem->name = info; newItem->next = NULL; // if the list is empty, add new item to the front if(head == NULL) { head = newItem; } else // if the list isnt empty, add new item to the end { node* iter = head; while(iter->next != NULL) { iter = iter->next; } iter->next = newItem; } }// end of Insert void Delete(string info) { node* iter = head; // if the list is empty, do nothing if(head == NULL) { return; } // delete the first item in the list else if(head->name == info) { head = head->next; delete iter; } // search the list until we find the desired item else { while(iter->next != NULL) { if(iter->next->name == info) { node* deleteNode = iter->next; iter->next = iter->next->next; delete deleteNode; break; } iter = iter->next; } } }// end of Delete void Display() { node* iter = head; // traverse thru the list, displaying the // text at each node location while(iter != NULL) { cout<<iter->name<<endl; iter = iter->next; } cout<<endl; }// end of Display void DestroyList() { if(head != NULL) { cout << "\n\nDestroying nodes...\n"; while(head != NULL) { node* temp = head; cout << temp->name <<endl; head = head->next; delete temp; } } }// http://programmingnotes.org/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148 // ============================================================================//    Author: Kenneth Perkins//    Date:   Aug 18, 2012//    Taken From: http://programmingnotes.org///    File:  SimpleList.cpp//    Description: Demonstrates the use of a simple linked list.// ============================================================================#include <iostream>#include <string>using namespace std; struct node{    /* -- you can use different data types here         -- instead of just a string    char letter;    int number;    double fNumber;    */    string name;    node* next;}; // global variables// this is the front of the listnode* head = NULL; // function prototypevoid Insert(string info);void Delete(string info);void Display();void DestroyList(); int main(){    // if you want to insert data into the list    // this is one way you can do it, using a 'temp' pointer    node* temp = new node;    temp->name = "My Programming Notes";    temp->next = NULL;     // set the head node to the data thats in the 'temp' pointer    head = temp;     // display data to the screen    cout << head->name <<endl<<endl;     // use the insert function to add new data to the list    // NOTE: you could have also used the 'insert' function ^ above    // to place data into the list    Insert("Is An Awesome Site!");     // insert more data into the list    Insert("August");    Display();     // delete the selected text from the list    Delete("August");    Display();     // destroy the current pointers in the list    // after you are finished using them    DestroyList();     return 0;}// end of main void Insert(string info){    node* newItem = new node;    newItem->name = info;    newItem->next = NULL;     // if the list is empty, add new item to the front    if(head == NULL)    {        head = newItem;    }    else // if the list isnt empty, add new item to the end    {        node* iter = head;        while(iter->next != NULL)        {            iter = iter->next;        }        iter->next = newItem;    }}// end of Insert void Delete(string info){    node* iter = head;     // if the list is empty, do nothing    if(head == NULL)    {        return;    }    // delete the first item in the list    else if(head->name == info)    {        head = head->next;        delete iter;    }    // search the list until we find the desired item    else    {        while(iter->next != NULL)        {            if(iter->next->name == info)            {                node* deleteNode = iter->next;                iter->next = iter->next->next;                delete deleteNode;                break;            }            iter = iter->next;        }    }}// end of Delete void Display(){    node* iter = head;    // traverse thru the list, displaying the    // text at each node location    while(iter != NULL)    {        cout<<iter->name<<endl;        iter = iter->next;    }    cout<<endl;}// end of Display void DestroyList(){    if(head != NULL)    {        cout << "\n\nDestroying nodes...\n";        while(head != NULL)        {            node* temp = head;            cout << temp->name <<endl;            head = head->next;            delete temp;        }    }}// http://programmingnotes.org/ ```

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output

`My Programming Notes`

``` My Programming Notes Is An Awesome Site! August [DELETE THE TEXT "AUGUST"] My Programming Notes Is An Awesome Site! ```

```Destroying nodes... My Programming Notes Is An Awesome Site! ```

C++ || Snippet â€“ Custom Template Linked List Sample Code

This page will consist of sample code for a singly linked list, which is loosely based on the built in C++ “List” library. Provided in the linked list class are the following functions:

``` * PushFront - Adds new item to the front of the list (LIFO) * PushBack - Adds new item to the back of the list (FIFO) * PopFront - Returns & removes first item from the list * PopBack - Returns & removes last item from the list * Front - Returns (but does not delete) the first item from the list * Back - Returns (but does not delete) the last item from the list * Delete - Searches and deletes the requested item * Display - Display all the current contents in the list * Replace - Replaces existing item from the list with a new item If existing item cannot be found, the new item is added to the back of the list * InsertBefore - Inserts new item before the existing item. If existing item cannot be found, the new item is added to the back of the list * InsertAfter - Inserts new item after the existing item. If existing item cannot be found, the new item is added to the back of the list * InsertInOrder - Inserts new item in numerical order, from lowest to highest * Size - Return the current size of the list * MakeEmpty - Initializes the list to an empty state 123456789101112131415161718192021222324252627282930 * PushFront - Adds new item to the front of the list (LIFO) * PushBack - Adds new item to the back of the list (FIFO) * PopFront - Returns & removes first item from the list * PopBack - Returns & removes last item from the list * Front - Returns (but does not delete) the first item from the list * Back - Returns (but does not delete) the last item from the list * Delete - Searches and deletes the requested item * Display - Display all the current contents in the list * Replace - Replaces existing item from the list with a new item            If existing item cannot be found, the new item is added to the back of the list * InsertBefore - Inserts new item before the existing item.                 If existing item cannot be found, the new item is added to the back of the list * InsertAfter - Inserts new item after the existing item.                 If existing item cannot be found, the new item is added to the back of the list * InsertInOrder - Inserts new item in numerical order, from lowest to highest * Size - Return the current size of the list * MakeEmpty - Initializes the list to an empty state ```

From the following, the functions of interest to look out for are the “Delete, Display, Replace, InsertBefore, InsertAfter, and InsertInOrder” functions as they are typically used as programming assignments in many C++ Data structures courses to further demonstrate how linked lists operate.

``` #include 'LinkedList.h' C++ // ============================================================================ // Author: Kenneth Perkins // Date: Jul 26, 2012 // Taken From: http://programmingnotes.org/ // File: LinkedList.h // Description: This is a class which implements various functions which // demonstrates the use of a Linked List. // ============================================================================ #include <iostream> template <class ItemType> class LinkedList { public: LinkedList(); /* Function: Constructor initializes list Precondition: None Postcondition: Defines private variables */ bool IsEmpty(); /* Function: Determines whether queue is empty Precondition: List has been created Postcondition: The function = true if the list is empty and the function = false if list is not empty */ void PushFront(ItemType item); /* Function: Adds new item to the front of the list (LIFO) Precondition: List has been created and is not full Postcondition: Item is in the list */ void PushBack(ItemType item); /* Function: Adds new item to the back of the list (FIFO) Precondition: List has been created and is not full Postcondition: Item is in the list */ ItemType PopFront(); /* Function: Returns & removes first item from the last Precondition: List has been initialized Postcondition: The first item in the list is removed */ ItemType PopBack(); /* Function: Returns & removes last item from the list Precondition: List has been initialized Postcondition: The last item in the list is removed */ ItemType Front(); /* Function: Returns (but does not delete) the first item from the list Precondition: List has been initialized Postcondition: The first item in the list is removed */ ItemType Back(); /* Function: Returns (but does not delete) the last item from the list Precondition: List has been initialized Postcondition: The last item in the list is removed */ void Delete(ItemType item); /* Function: Searches and deletes the requested item Precondition: List has been created and is not empty Postcondition: Item removed from the list */ void Display(); /* Function: Display all the current contents in the list Precondition: List has been created and is not empty Postcondition: List is displayed to the screen */ void Replace(ItemType initial, ItemType replace); /* Function: Replaces existing item from the list with a new item Precondition: List has been created and is not empty Postcondition: Initial item is replaced with the new one */ void InsertBefore(ItemType initial, ItemType newItem); /* Function: Inserts new item before the existing item Precondition: List has been created and is not empty Postcondition: New item is inserted before the existing item */ void InsertAfter(ItemType initial, ItemType newItem); /* Function: Inserts new item after the existing item Precondition: List has been created and is not empty Postcondition: New item is inserted after the existing item */ void InsertInOrder(ItemType item); /* Function: Inserts new item in numerical order, from lowest to highest Precondition: List has been created and is not empty Postcondition: The list is sorted in numerical order */ int Size(); /* Function: Return the current size of the list Precondition: List has been initialized Postcondition: The size of the list is returned */ void MakeEmpty(); /* Function: Initializes the list to an empty state Precondition: List has been created Postcondition: List no longer exists */ ~LinkedList(); /* Function: Deletes all the items in the list Precondition: List has been declared Postcondition: List no longer exists */ private: struct node { ItemType info; node* next; }; node* head; int size; }; //========================= Implementation ================================// template <class ItemType> LinkedList<ItemType>::LinkedList() { head = NULL; size = 0; }// end of LinkedList template <class ItemType> bool LinkedList<ItemType>::IsEmpty() { return (head==NULL); }// end of IsEmpty template <class ItemType> void LinkedList<ItemType>::PushFront(ItemType item) { // LIFO node* temp = new node; temp-> info = item; temp-> next = head; head = temp; ++size; }// end of PushFront template <class ItemType> void LinkedList<ItemType>::PushBack(ItemType item) { // FIFO node* temp = new node; temp->info = item; temp->next = NULL; if(IsEmpty()) { head=temp; } else { node* temp2 = head; while(temp2->next!=NULL) { temp2=temp2->next; } temp2->next=temp; } ++size; }// end of PushBack template <class ItemType> ItemType LinkedList<ItemType>::PopFront() { if(IsEmpty()) { std::cout<<"\nLIST EMPTY\n"; } else { ItemType item = head-> info; node* temp = head; head = head-> next; delete temp; --size; return item; } }// end of PopFront template <class ItemType> ItemType LinkedList<ItemType>::PopBack() { if(IsEmpty()) { std::cout<<"\nLIST EMPTY\n"; } else if(size == 1) { ItemType item = PopFront(); return item; } else { node* temp = head; ItemType item; while(temp->next != NULL) { if(temp->next->next==NULL) { node* temp2=temp->next; temp->next=temp->next->next; item = temp2-> info; delete temp2; break; } temp=temp->next; } --size; return item; } }// end of PopBack template <class ItemType> ItemType LinkedList<ItemType>::Front() { if(IsEmpty()) { std::cout<<"\nLIST EMPTY\n"; } else { return head-> info; } }// end of Front template <class ItemType> ItemType LinkedList<ItemType>::Back() { if(IsEmpty()) { std::cout<<"\nLIST EMPTY\n"; } else { node* temp = head; while(temp->next != NULL) { temp = temp-> next; } ItemType item = temp-> info; return item; } }// end of Back template <class ItemType> void LinkedList<ItemType>::Delete(ItemType item) { node* temp=head; if(IsEmpty()) { return; } else if(temp->info==item) { head=head->next; delete temp; --size; } else { while(temp->next!=NULL) { if(temp->next->info==item) { node* temp2=temp->next; temp->next=temp->next->next; delete temp2; --size; break; } temp=temp->next; } } }// end of Delete template <class ItemType> void LinkedList<ItemType>::Display() { node* temp=head; while(temp!=NULL) { std::cout<<temp->info<<std::endl; temp=temp->next; } }// end of Display template <class ItemType> void LinkedList<ItemType>::Replace(ItemType initial, ItemType replace) { node* temp=head; if(IsEmpty()) { PushFront(replace); } else if(temp->info==initial) { temp->info=replace; } else { while(temp->next!=NULL) { if(temp->info==initial) { temp->info=replace; break; } temp=temp->next; } if(temp->next==NULL) { PushBack(replace); } } }// end of Replace template <class ItemType> void LinkedList<ItemType>::InsertBefore(ItemType initial, ItemType newItem) { node* temp=head; node* temp2=new node; temp2->info=initial; temp2->next=NULL; if(IsEmpty()) { PushFront(newItem); } else if(temp->info==initial) { temp->info=newItem; temp2->next=temp->next; temp->next=temp2; ++size; } else { while(temp->next!=NULL) { if(temp->info==initial) { temp->info=newItem; temp2->next=temp->next; temp->next=temp2; ++size; break; } temp=temp->next; } if(temp->next==NULL) { PushBack(newItem); } } }// end of InsertBefore template <class ItemType> void LinkedList<ItemType>::InsertAfter(ItemType initial, ItemType newItem) { node* temp=head; node* temp2=new node; temp2->info=newItem; temp2->next=NULL; if(IsEmpty()) { PushFront(newItem); } else if(temp->info==initial) { temp2->next=temp->next; temp->next=temp2; ++size; } else { while(temp->next!=NULL) { if(temp->info==initial) { temp2->next=temp->next; temp->next=temp2; ++size; break; } temp=temp->next; } if(temp->next==NULL) { PushBack(newItem); } } }// end of InsertAfter template <class ItemType> void LinkedList<ItemType>::InsertInOrder(ItemType item) { if(IsEmpty()) { PushFront(item); } else { node* temp=head; node* temp2=new node; if(item <=(temp->info)) { ItemType placeHolder=temp->info; temp2->info=placeHolder; temp->info=item; temp2->next=temp->next; temp->next=temp2; ++size; } else { while(temp->next!=NULL) { if(((temp->info) <= item) && (item <= (temp->next->info))) { temp2->info=item; temp2->next=temp->next; temp->next=temp2; ++size; return; } temp=temp->next; } if(temp->next==NULL) { PushBack(item); } } } }// end of InsertInOrder template <class ItemType> int LinkedList<ItemType>::Size() { if(IsEmpty()) { std::cout<<"\nLIST EMPTY\n"; } return size; }// end of Size template <class ItemType> void LinkedList<ItemType>::MakeEmpty() { if(!IsEmpty()) { std::cout << "\nDestroying nodes...\n"; while(!IsEmpty()) { node* temp = head; //std::cout << temp-> info << '\n'; head = head-> next; delete temp; } size = 0; } }// end of MakeEmpty template <class ItemType> LinkedList<ItemType>::~LinkedList() { MakeEmpty(); }// http://programmingnotes.org/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452 // ============================================================================//    Author: Kenneth Perkins//    Date:   Jul 26, 2012//    Taken From: http://programmingnotes.org///    File:  LinkedList.h//    Description: This is a class which implements various functions which//          demonstrates the use of a Linked List. // ============================================================================#include <iostream> template <class ItemType>class LinkedList{public:    LinkedList();        /*   Function: Constructor initializes list             Precondition: None            Postcondition: Defines private variables */    bool IsEmpty();        /*   Function: Determines whether queue is empty            Precondition: List has been created            Postcondition: The function = true if the list is empty and the                             function = false if list is not empty */    void PushFront(ItemType item);        /*   Function: Adds new item to the front of the list (LIFO)            Precondition:  List has been created and is not full            Postcondition: Item is in the list */    void PushBack(ItemType item);        /*   Function: Adds new item to the back of the list (FIFO)            Precondition:  List has been created and is not full            Postcondition: Item is in the list */    ItemType PopFront();        /*   Function: Returns & removes first item from the last            Precondition: List has been initialized            Postcondition: The first item in the list is removed */    ItemType PopBack();        /*   Function: Returns & removes last item from the list            Precondition: List has been initialized            Postcondition: The last item in the list is removed */    ItemType Front();        /*   Function: Returns (but does not delete) the first item from the list            Precondition: List has been initialized            Postcondition: The first item in the list is removed */    ItemType Back();        /*   Function: Returns (but does not delete) the last item from the list            Precondition: List has been initialized            Postcondition: The last item in the list is removed */    void Delete(ItemType item);        /*   Function: Searches and deletes the requested item            Precondition:  List has been created and is not empty            Postcondition: Item removed from the list */    void Display();        /*   Function: Display all the current contents in the list            Precondition:  List has been created and is not empty            Postcondition: List is displayed to the screen */    void Replace(ItemType initial, ItemType replace);        /*   Function: Replaces existing item from the list with a new item            Precondition:  List has been created and is not empty            Postcondition: Initial item is replaced with the new one */    void InsertBefore(ItemType initial, ItemType newItem);        /*   Function: Inserts new item before the existing item            Precondition:  List has been created and is not empty            Postcondition: New item is inserted before the existing item */    void InsertAfter(ItemType initial, ItemType newItem);        /*   Function: Inserts new item after the existing item            Precondition:  List has been created and is not empty            Postcondition: New item is inserted after the existing item */    void InsertInOrder(ItemType item);          /*   Function: Inserts new item in numerical order, from lowest to highest            Precondition:  List has been created and is not empty            Postcondition: The list is sorted in numerical order */    int Size();        /*   Function: Return the current size of the list            Precondition: List has been initialized            Postcondition: The size of the list is returned */    void MakeEmpty();        /*   Function: Initializes the list to an empty state             Precondition: List has been created            Postcondition: List no longer exists */    ~LinkedList();        /*   Function: Deletes all the items in the list            Precondition: List has been declared            Postcondition: List no longer exists */ private:    struct node    {        ItemType info;        node* next;    };    node* head;     int size;}; //=========================  Implementation  ================================// template <class ItemType>LinkedList<ItemType>::LinkedList(){    head = NULL;    size = 0;}// end of LinkedList template <class ItemType>bool LinkedList<ItemType>::IsEmpty(){    return (head==NULL);}// end of IsEmpty template <class ItemType>void LinkedList<ItemType>::PushFront(ItemType item){    // LIFO     node* temp = new node;    temp-> info = item;    temp-> next = head;    head = temp;    ++size;}// end of PushFront template <class ItemType>void LinkedList<ItemType>::PushBack(ItemType item){    // FIFO    node* temp = new node;    temp->info = item;    temp->next = NULL;        if(IsEmpty())    {        head=temp;    }    else    {        node* temp2 = head;                while(temp2->next!=NULL)        {            temp2=temp2->next;        }        temp2->next=temp;    }    ++size;}// end of PushBack template <class ItemType>ItemType LinkedList<ItemType>::PopFront(){    if(IsEmpty())    {        std::cout<<"\nLIST EMPTY\n";    }    else    {          ItemType item = head-> info;          node* temp = head;        head = head-> next;        delete temp;        --size;        return item;    }}// end of PopFront template <class ItemType>ItemType LinkedList<ItemType>::PopBack(){    if(IsEmpty())    {        std::cout<<"\nLIST EMPTY\n";    }    else if(size == 1)    {        ItemType item = PopFront();        return item;    }    else    {        node* temp = head;        ItemType item;        while(temp->next != NULL)        {            if(temp->next->next==NULL)            {                node* temp2=temp->next;                temp->next=temp->next->next;                item = temp2-> info;                delete temp2;                break;            }            temp=temp->next;        }        --size;        return item;    }   }// end of PopBack template <class ItemType>ItemType LinkedList<ItemType>::Front(){    if(IsEmpty())    {        std::cout<<"\nLIST EMPTY\n";    }    else    {         return head-> info;    }}// end of Front template <class ItemType>ItemType LinkedList<ItemType>::Back() {    if(IsEmpty())    {        std::cout<<"\nLIST EMPTY\n";    }    else    {        node* temp = head;         while(temp->next != NULL)        {            temp = temp-> next;        }        ItemType item = temp-> info;        return item;    }   }// end of Back template <class ItemType>void LinkedList<ItemType>::Delete(ItemType item){    node* temp=head;    if(IsEmpty())    {        return;    }    else if(temp->info==item)    {        head=head->next;        delete temp;        --size;    }    else    {        while(temp->next!=NULL)        {            if(temp->next->info==item)            {                node* temp2=temp->next;                temp->next=temp->next->next;                delete temp2;                --size;                break;            }            temp=temp->next;        }    }}// end of Delete template <class ItemType>void LinkedList<ItemType>::Display(){    node* temp=head;    while(temp!=NULL)    {        std::cout<<temp->info<<std::endl;        temp=temp->next;    }}// end of Display template <class ItemType>void LinkedList<ItemType>::Replace(ItemType initial, ItemType replace){    node* temp=head;    if(IsEmpty())    {        PushFront(replace);    }    else if(temp->info==initial)    {        temp->info=replace;    }    else    {                while(temp->next!=NULL)        {            if(temp->info==initial)            {                temp->info=replace;                break;            }            temp=temp->next;        }        if(temp->next==NULL)        {            PushBack(replace);        }    }}// end of Replace template <class ItemType>void LinkedList<ItemType>::InsertBefore(ItemType initial, ItemType newItem){    node* temp=head;    node* temp2=new node;    temp2->info=initial;    temp2->next=NULL;             if(IsEmpty())    {        PushFront(newItem);    }    else if(temp->info==initial)    {        temp->info=newItem;         temp2->next=temp->next;        temp->next=temp2;        ++size;    }    else    {        while(temp->next!=NULL)        {            if(temp->info==initial)            {                temp->info=newItem;                 temp2->next=temp->next;                temp->next=temp2;                ++size;                break;            }            temp=temp->next;                   }        if(temp->next==NULL)        {            PushBack(newItem);        }    }}// end of InsertBefore template <class ItemType>void LinkedList<ItemType>::InsertAfter(ItemType initial, ItemType newItem){    node* temp=head;    node* temp2=new node;    temp2->info=newItem;    temp2->next=NULL;        if(IsEmpty())    {        PushFront(newItem);    }    else if(temp->info==initial)    {        temp2->next=temp->next;        temp->next=temp2;        ++size;    }    else    {           while(temp->next!=NULL)        {            if(temp->info==initial)            {                temp2->next=temp->next;                temp->next=temp2;                ++size;                break;            }            temp=temp->next;        }        if(temp->next==NULL)        {            PushBack(newItem);        }    }}// end of InsertAfter template <class ItemType>void LinkedList<ItemType>::InsertInOrder(ItemType item){    if(IsEmpty())    {        PushFront(item);    }    else    {        node* temp=head;        node* temp2=new node;            if(item <=(temp->info))        {              ItemType placeHolder=temp->info;            temp2->info=placeHolder;            temp->info=item;            temp2->next=temp->next;            temp->next=temp2;            ++size;        }         else        {            while(temp->next!=NULL)            {                       if(((temp->info) <= item) && (item <= (temp->next->info)))                {                               temp2->info=item;                    temp2->next=temp->next;                    temp->next=temp2;                    ++size;                    return;                }                temp=temp->next;            }            if(temp->next==NULL)            {                PushBack(item);            }        }    }}// end of InsertInOrder template <class ItemType>int LinkedList<ItemType>::Size(){    if(IsEmpty())    {        std::cout<<"\nLIST EMPTY\n";    }    return size;}// end of Size  template <class ItemType>void LinkedList<ItemType>::MakeEmpty(){    if(!IsEmpty())    {        std::cout << "\nDestroying nodes...\n";        while(!IsEmpty())        {            node* temp = head;            //std::cout << temp-> info << '\n';            head = head-> next;            delete temp;        }        size = 0;    }}// end of MakeEmpty template <class ItemType>LinkedList<ItemType>::~LinkedList(){    MakeEmpty();}// http://programmingnotes.org/ ```

===== DEMONSTRATION HOW TO USE =====

Use of the above template class is the same as its STL counterpart. Here is a sample program demonstrating its use.

``` How To Use #include 'LinkedList.h' C++ #include <iostream> #include <string> #include "LinkedList.h" using namespace std; int main() { // declare variables, using a string as // the item type for the class. // NOTE: you can also use an int, float, double etc. // instead of a string LinkedList<string> list; // demontrate the "InOrder" function cout<<"** These are names of fruits sorted in order" <<" using the 'InsertInOrder()' function:\n\n"; list.InsertInOrder("Tomato"); list.InsertInOrder("Orange"); list.InsertInOrder("Apple"); list.InsertInOrder("Plum"); list.Display(); cout<<"\nThere is currently "<<list.Size()<<" items in the list\n\n"; // demonstrate the "Delete" function cout<<"\n** Here is the same list with the word 'Plum' deleted" << "\nusing the 'Delete()' function:\n\n"; list.Delete("Plum"); list.Display(); cout<<"\nThere is currently "<<list.Size()<<" items in the listnn"; // demonstrate the "InsertAfter" function cout<<"\n** Now the word 'Bike' will be added to the list," <<"\nright after the word 'Apple' using the " <<"'InsertAfter()' function:\n\n"; list.InsertAfter("Apple","Bike"); list.Display(); cout<<"\nThere is currently "<<list.Size()<<" items in the list\n\n"; // demonstrate the "InsertBefore" function cout<<"\n** Now the name 'Jessica' will be added to the list," <<"\nright before the word 'Orange' using the " <<"'InsertBefore()' function:\n\n"; list.InsertBefore("Orange","Jessica"); list.Display(); cout<<"\nThere is currently "<<list.Size()<<" items in the list\n\n"; // demonstrate the "Replace" function cout<<"\n** The word 'Orange' will now be replaced with the name," <<"\n'Kat' using the 'Replace()' function:\n\n"; list.Replace("Orange","Kat"); list.Display(); cout<<"\nThere is currently "<<list.Size()<<" items in the list\n\n"; }// http://programmingnotes.org/ 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859 #include <iostream>#include <string>#include "LinkedList.h"using namespace std; int main(){    // declare variables, using a string as    // the item type for the class.      // NOTE: you can also use an int, float, double etc.    // instead of a string    LinkedList<string> list;     // demontrate the "InOrder" function    cout<<"** These are names of fruits sorted in order"        <<" using the 'InsertInOrder()' function:\n\n";    list.InsertInOrder("Tomato");    list.InsertInOrder("Orange");    list.InsertInOrder("Apple");    list.InsertInOrder("Plum");    list.Display();     cout<<"\nThere is currently "<<list.Size()<<" items in the list\n\n";     // demonstrate the "Delete" function    cout<<"\n** Here is the same list with the word 'Plum' deleted"        << "\nusing the 'Delete()' function:\n\n";    list.Delete("Plum");    list.Display();     cout<<"\nThere is currently "<<list.Size()<<" items in the listnn";     // demonstrate the "InsertAfter" function    cout<<"\n** Now the word 'Bike' will be added to the list,"        <<"\nright after the word 'Apple' using the "        <<"'InsertAfter()' function:\n\n";    list.InsertAfter("Apple","Bike");    list.Display();     cout<<"\nThere is currently "<<list.Size()<<" items in the list\n\n";     // demonstrate the "InsertBefore" function    cout<<"\n** Now the name 'Jessica' will be added to the list,"        <<"\nright before the word 'Orange' using the "        <<"'InsertBefore()' function:\n\n";    list.InsertBefore("Orange","Jessica");    list.Display();     cout<<"\nThere is currently "<<list.Size()<<" items in the list\n\n";     // demonstrate the "Replace" function    cout<<"\n** The word 'Orange' will now be replaced with the name,"        <<"\n'Kat' using the 'Replace()' function:\n\n";    list.Replace("Orange","Kat");    list.Display();     cout<<"\nThere is currently "<<list.Size()<<" items in the list\n\n";}// http://programmingnotes.org/ ```

Once compiled, you should get this as your output

`** These are names of fruits sorted in order using the 'InsertInOrder()' function:`

``` Apple Orange Plum Tomato There is currently 4 items in the list ** Here is the same list with the word 'Plum' deleted using the 'Delete()' function: Apple Orange Tomato There is currently 3 items in the list ** Now the word 'Bike' will be added to the list, right after the word 'Apple' using the 'InsertAfter()' function: Apple Bike Orange Tomato There is currently 4 items in the list ** Now the name 'Jessica' will be added to the list, right before the word 'Orange' using the 'InsertBefore()' function: Apple Bike Jessica Orange Tomato There is currently 5 items in the list ** The word 'Orange' will now be replaced with the name, 'Kat' using the 'Replace()' function: Apple Bike Jessica Kat Tomato ```

```There is currently 5 items in the list ```

C++ || Snippet â€“ Singly Linked List Custom Template Queue Sample Code

This page will consist of sample code for a custom singly linked list template queue. This implementation differs from the previously highlighted doubly linked list in that this version uses a single node to store its data rather than using two separate nodes (front and rear).

REQUIRED KNOWLEDGE FOR THIS SNIPPET

```Structs Classes Template Classes - What Are They?'' Queue - What is it? FIFO - First In First Out #include < queue> Linked Lists - How To Use ```

This template class is a custom duplication of the Standard Template Library (STL) queue class. Whether you like building your own data structures, you simply do not like to use any inbuilt functions, opting to build everything yourself, or your homework requires you make your own data structure, this sample code is really useful. I feel its beneficial building functions such as this, that way you better understand the behind the scene processes.

``` #include 'SingleQueue.h' C++ // ============================================================================ // Author: K Perkins // Date: Jul 14, 2012 // Taken From: http://programmingnotes.org/ // File: SingleQueue.h // Description: This is a class which implements various functions // demonstrating the use of a queue. // ============================================================================ #include <iostream> template <class ItemType> class SingleQueue { public: SingleQueue(); /* Function: Constructor initializes queue Precondition: None Postcondition: Defines private variables */ bool IsEmpty(); /* Function: Determines whether queue is empty Precondition: Queue has been created Postcondition: The function = true if the queue is empty and the function = false if queue is not empty */ bool IsFull(); /* Function: Determines whether queue is full Precondition: Queue has been created Postcondition: The function = true if the queue is full and the function = false if queue is not full */ void EnQueue(ItemType item); /* Function: Adds new item to the back of the queue Precondition: Queue has been created and is not full Postcondition: Item is in the queue */ ItemType DeQueue(); /* Function: Returns and then deletes the first item in the queue Precondition: Queue has been created and is not empty Postcondition: The first item in the queue has been removed and the queue order is maintained */ ItemType Front(); /* Function: Returns (but does not delete) the first item in the queue Precondition: Queue has been created and is not empty Postcondition: The first item in the queue has been returned and the queue order is maintained */ ItemType Rear(); /* Function: Returns (but does not delete) the last item in the queue Precondition: Queue has been created and is not empty Postcondition: The last item in the queue has been returned and the queue order is maintained */ int Size(); /* Function: Return the current size of the queue Precondition: Queue has been initialized Postcondition: The size of the queue is returned */ void MakeEmpty(); /* Function: Initializes queue to an empty state Precondition: Queue has been created Postcondition: Queue no longer exists */ ~SingleQueue(); /* Function: Removes the queue Precondition: Queue has been declared Postcondition: Queue no longer exists */ private: struct NodeType { ItemType currentItem; NodeType* next; }; NodeType* head; // front of queue int size; }; //========================= Implementation ================================// template<class ItemType> SingleQueue<ItemType>::SingleQueue() { head = NULL; size = 0; }/* end of SingleQueue */ template<class ItemType> bool SingleQueue<ItemType>::IsEmpty() { return (head == NULL); }/* end of IsEmpty */ template<class ItemType> bool SingleQueue<ItemType>::IsFull() { try { NodeType* location = new NodeType; delete location; return false; } catch(std::bad_alloc&) { return true; } }/* end of IsFull */ template<class ItemType> void SingleQueue<ItemType>::EnQueue(ItemType newItem) { if(IsFull()) { std::cout<<"nQUEUE FULLn"; } else { NodeType* newNode = new NodeType; // adds new node newNode-> currentItem = newItem; newNode-> next = NULL; if(IsEmpty()) { head = newNode; } else { NodeType* tempPtr = head; while(tempPtr-> next != NULL) { tempPtr = tempPtr-> next; } tempPtr-> next = newNode; } ++size; } }/* end of EnQueue */ template<class ItemType> ItemType SingleQueue<ItemType>::DeQueue() { if(IsEmpty()) { std::cout<<"nQUEUE EMPTYn"; } else { NodeType* tempPtr = head; // temporary pointer ItemType item = head-> currentItem; head = head-> next; delete tempPtr; --size; return item; } }/* end of DeQueue */ template<class ItemType> ItemType SingleQueue<ItemType>::Front() { if(IsEmpty()) { std::cout<<"nQUEUE EMPTYn"; } else { ItemType item = head-> currentItem; return item; } }/* end of Front */ template<class ItemType> ItemType SingleQueue<ItemType>::Rear() { if(IsEmpty()) { std::cout<<"nQUEUE EMPTYn"; } else { NodeType* tempPtr = head; // temporary pointer while(tempPtr->next != NULL) { tempPtr = tempPtr-> next; } ItemType item = tempPtr-> currentItem; return item; } }/* end of Rear */ template<class ItemType> int SingleQueue<ItemType>::Size() { if(IsEmpty()) { std::cout<<"nQUEUE EMPTYn"; } return size; }/* end of Size */ template<class ItemType> void SingleQueue<ItemType>::MakeEmpty() { if(!IsEmpty()) { std::cout << "Destroying nodes ...n"; while(!IsEmpty()) { NodeType* tempPtr = head; //std::cout << tempPtr-> currentItem << 'n'; head = head-> next; delete tempPtr; } size = 0; } }/* end of MakeEmpty */ template<class ItemType> SingleQueue<ItemType>::~SingleQueue() { MakeEmpty(); }// http://programmingnotes.org/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214 // ============================================================================//    Author: K Perkins//    Date:   Jul 14, 2012//    Taken From: http://programmingnotes.org///    File:  SingleQueue.h//    Description: This is a class which implements various functions//          demonstrating the use of a queue. // ============================================================================#include <iostream> template <class ItemType>class SingleQueue{public: SingleQueue(); /*   Function: Constructor initializes queue Precondition: None Postcondition: Defines private variables */ bool IsEmpty(); /*   Function: Determines whether queue is empty Precondition: Queue has been created Postcondition: The function = true if the queue is empty and the function = false if queue is not empty */ bool  IsFull(); /*   Function: Determines whether queue is full Precondition: Queue has been created Postcondition: The function = true if the queue is full and the function = false if queue is not full */ void EnQueue(ItemType item); /*   Function: Adds new item to the back of the queue Precondition:  Queue has been created and is not full Postcondition: Item is in the queue */ ItemType DeQueue(); /*   Function: Returns and then deletes the first item in the queue Precondition:  Queue has been created and is not empty Postcondition: The first item in the queue has been removed and the queue order is maintained */ ItemType Front(); /*   Function: Returns (but does not delete) the first item in the queue Precondition:  Queue has been created and is not empty Postcondition: The first item in the queue has been returned and the queue order is maintained */ ItemType Rear(); /*   Function: Returns (but does not delete) the last item in the queue Precondition:  Queue has been created and is not empty Postcondition: The last item in the queue has been returned and the queue order is maintained */ int Size();          /*   Function: Return the current size of the queue               Precondition: Queue has been initialized               Postcondition: The size of the queue is returned */ void MakeEmpty(); /*   Function: Initializes queue to an empty state Precondition: Queue has been created Postcondition: Queue no longer exists */ ~SingleQueue(); /*   Function: Removes the queue Precondition: Queue has been declared Postcondition: Queue no longer exists */private: struct  NodeType { ItemType currentItem; NodeType* next; }; NodeType* head; // front of queue int size;}; //=========================  Implementation  ================================// template<class ItemType>SingleQueue<ItemType>::SingleQueue(){ head = NULL; size = 0;}/* end of SingleQueue */ template<class ItemType>bool SingleQueue<ItemType>::IsEmpty(){ return (head == NULL);}/* end of IsEmpty */ template<class ItemType>bool SingleQueue<ItemType>::IsFull(){ try { NodeType* location = new NodeType; delete location; return false; } catch(std::bad_alloc&) { return true; }}/* end of IsFull */ template<class ItemType>void SingleQueue<ItemType>::EnQueue(ItemType newItem){ if(IsFull()) { std::cout<<"nQUEUE FULLn"; } else { NodeType* newNode = new NodeType;  // adds new node newNode-> currentItem = newItem; newNode-> next = NULL; if(IsEmpty()) { head = newNode; } else { NodeType* tempPtr = head; while(tempPtr-> next != NULL) { tempPtr = tempPtr-> next; } tempPtr-> next = newNode; } ++size; }}/* end of EnQueue */ template<class ItemType>ItemType SingleQueue<ItemType>::DeQueue() {    if(IsEmpty())    {        std::cout<<"nQUEUE EMPTYn";    }    else    {        NodeType* tempPtr = head;  // temporary pointer         ItemType item = head-> currentItem;        head = head-> next;        delete tempPtr;        --size;        return item;    } }/* end of DeQueue */ template<class ItemType>ItemType SingleQueue<ItemType>::Front() {    if(IsEmpty())    {        std::cout<<"nQUEUE EMPTYn";    }    else    {         ItemType item = head-> currentItem;        return item;    } }/* end of Front */ template<class ItemType>ItemType SingleQueue<ItemType>::Rear() {    if(IsEmpty())    {        std::cout<<"nQUEUE EMPTYn";    }    else    {        NodeType* tempPtr = head;  // temporary pointer         while(tempPtr->next != NULL)        {                tempPtr = tempPtr-> next;        }        ItemType item = tempPtr-> currentItem;        return item;    } }/* end of Rear */ template<class ItemType>int SingleQueue<ItemType>::Size(){    if(IsEmpty())    {        std::cout<<"nQUEUE EMPTYn";    }    return size;}/* end of Size */ template<class ItemType>void SingleQueue<ItemType>::MakeEmpty(){    if(!IsEmpty())    {        std::cout << "Destroying nodes ...n";        while(!IsEmpty())        {            NodeType* tempPtr = head;            //std::cout << tempPtr-> currentItem << 'n';            head = head-> next;            delete tempPtr;        }        size = 0;    }}/* end of MakeEmpty */ template<class ItemType>SingleQueue<ItemType>::~SingleQueue() { MakeEmpty();}// http://programmingnotes.org/ ```

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

===== DEMONSTRATION HOW TO USE =====

Use of the above template class is the same as its STL counterpart. Here is a sample program demonstrating its use.

``` How To Use #include 'SingleQueue.h' C++ #include <iostream> #include "SingleQueue.h" using namespace std; int main() { // declare variables SingleQueue<char> charQueue; SingleQueue<int> intQueue; SingleQueue<double> doubleQueue; // ------ Char Example ------// char charArry[]="My Programming Notes Is A Big Help!"; int counter=0; while(charArry[counter]!='\0') { charQueue.EnQueue(charArry[counter]); ++counter; } cout<<"charQueue has "<<charQueue.Size()<<" items in it " <<"and contains the text:n"; while(!charQueue.IsEmpty()) { cout<<charQueue.DeQueue(); } cout<<endl; // ------ Int Example ------// int intArry[]={1,22,309,461,-92,66,7,8,1987,9,27,12}; counter=0; while(counter < sizeof(intArry)/sizeof(intArry[0])) { intQueue.EnQueue(intArry[counter]); ++counter; } cout<<"nintQueue has "<<intQueue.Size()<<" items in it.n" <<"The sum of the numbers in the queue is: "; counter=0; while(!intQueue.IsEmpty()) { counter-=intQueue.DeQueue(); } cout<<counter<<endl; // ------ Double Example ------// double doubleArry[]={31.62,2.8,43.9,4.4,19.87,6.23,7.787,68.99,9.6,3.540,12.04}; double sum=0; counter=0; while(counter < sizeof(doubleArry)/sizeof(doubleArry[0])) { doubleQueue.EnQueue(doubleArry[counter]); ++counter; } cout<<"ndoubleQueue has "<<doubleQueue.Size()<<" items in it.n" <<"The sum of the numbers in the queue is: "; while(!doubleQueue.IsEmpty()) { sum+=doubleQueue.DeQueue(); } cout<<sum<<endl; return 0; }// http://programmingnotes.org/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263 #include <iostream>#include "SingleQueue.h"using namespace std; int main(){ // declare variables SingleQueue<char> charQueue; SingleQueue<int> intQueue; SingleQueue<double> doubleQueue; // ------ Char Example ------// char charArry[]="My Programming Notes Is A Big Help!"; int counter=0; while(charArry[counter]!='\0') { charQueue.EnQueue(charArry[counter]); ++counter; } cout<<"charQueue has "<<charQueue.Size()<<" items in it " <<"and contains the text:n"; while(!charQueue.IsEmpty()) { cout<<charQueue.DeQueue(); } cout<<endl; // ------ Int Example ------// int intArry[]={1,22,309,461,-92,66,7,8,1987,9,27,12}; counter=0; while(counter < sizeof(intArry)/sizeof(intArry[0])) { intQueue.EnQueue(intArry[counter]); ++counter; } cout<<"nintQueue has "<<intQueue.Size()<<" items in it.n" <<"The sum of the numbers in the queue is: "; counter=0; while(!intQueue.IsEmpty()) { counter-=intQueue.DeQueue(); } cout<<counter<<endl; // ------ Double Example ------// double doubleArry[]={31.62,2.8,43.9,4.4,19.87,6.23,7.787,68.99,9.6,3.540,12.04}; double sum=0; counter=0; while(counter < sizeof(doubleArry)/sizeof(doubleArry[0])) { doubleQueue.EnQueue(doubleArry[counter]); ++counter; } cout<<"ndoubleQueue has "<<doubleQueue.Size()<<" items in it.n" <<"The sum of the numbers in the queue is: "; while(!doubleQueue.IsEmpty()) { sum+=doubleQueue.DeQueue(); } cout<<sum<<endl;  return 0;}// http://programmingnotes.org/ ```

Once compiled, you should get this as your output

```charQueue has 35 items in it and contains the text: My Programming Notes Is A Big Help!```

``` intQueue has 12 items in it. The sum of the numbers in the queue is: -2817 ```

```doubleQueue has 11 items in it. The sum of the numbers in the queue is: 210.777 Press any key to continue . . . ```

C++ || Snippet â€“ Doubly Linked List Custom Template Queue Sample Code

This page will consist of sample code for a custom doubly linked list template queue. This implementation is considered a doubly linked list because it uses two nodes to store data in the queue – a ‘front’ and a ‘rear’ node. This is not a circular linked list, nor does it link forwards and/or backwards.

REQUIRED KNOWLEDGE FOR THIS SNIPPET

```Structs Classes Template Classes - What Are They? Queue - What is it? FIFO - First In First Out #include < queue> Linked Lists - How To Use ```

This template class is a custom duplication of the Standard Template Library (STL) queue class. Whether you like building your own data structures, you simply do not like to use any inbuilt functions, opting to build everything yourself, or your homework requires you make your own data structure, this sample code is really useful. I feel its beneficial building functions such as this, that way you better understand the behind the scene processes.

``` #include 'DoubleQueue.h' C++ // ============================================================================ // Author: K Perkins // Date: May 20, 2012 // Taken From: http://programmingnotes.org/ // File: DoubleQueue.h // Description: This is a class which implements various functions // demonstrating the use of a queue. // ============================================================================ #include <iostream> template <class ItemType> class DoubleQueue { public: DoubleQueue(); /* Function: Constructor initializes queue Precondition: None Postcondition: Defines private variables */ bool IsEmpty(); /* Function: Determines whether queue is empty Precondition: Queue has been created Postcondition: The function = true if the queue is empty and the function = false if queue is not empty */ bool IsFull(); /* Function: Determines whether queue is full Precondition: Queue has been created Postcondition: The function = true if the queue is full and the function = false if queue is not full */ void EnQueue(ItemType item); /* Function: Adds new item to the back of the queue Precondition: Queue has been created and is not full Postcondition: Item is in the queue */ ItemType DeQueue(); /* Function: Returns and then deletes the first item in the queue Precondition: Queue has been created and is not empty Postcondition: The first item in the queue has been removed and the queue order is maintained */ ItemType Front(); /* Function: Returns (but does not delete) the first item in the queue Precondition: Queue has been created and is not empty Postcondition: The first item in the queue has been returned and the queue order is maintained */ ItemType Rear(); /* Function: Returns (but does not delete) the last item in the queue Precondition: Queue has been created and is not empty Postcondition: The last item in the queue has been returned and the queue order is maintained */ int Size(); /* Function: Return the current size of the queue Precondition: Queue has been initialized Postcondition: The size of the queue is returned */ void MakeEmpty(); /* Function: Initializes queue to an empty state Precondition: Queue has been created Postcondition: Queue no longer exists */ ~DoubleQueue(); /* Function: Removes the queue Precondition: Queue has been declared Postcondition: Queue no longer exists */ private: struct NodeType { ItemType currentItem; NodeType* next; }; NodeType* front; // front of queue NodeType* rear; // back of queue int size; }; //========================= Implementation ================================// template<class ItemType> DoubleQueue<ItemType>::DoubleQueue() { front = NULL; rear = NULL; size = 0; }/* end of DoubleQueue */ template<class ItemType> bool DoubleQueue<ItemType>::IsEmpty() { return (front == NULL); }/* end of IsEmpty */ template<class ItemType> bool DoubleQueue<ItemType>::IsFull() { try { NodeType* location = new NodeType; delete location; return false; } catch(std::bad_alloc&) { return true; } }/* end of IsFull */ template<class ItemType> void DoubleQueue<ItemType>::EnQueue(ItemType newItem) { if(IsFull()) { std::cout<<"nQUEUE FULLn"; } else { NodeType* newNode = new NodeType; // adds new node newNode-> currentItem = newItem; newNode-> next = NULL; if(rear == NULL) { front = newNode; } else { rear-> next = newNode; } rear = newNode; ++size; } }/* end of EnQueue */ template<class ItemType> ItemType DoubleQueue<ItemType>::DeQueue() { if(IsEmpty()) { std::cout<<"nQUEUE EMPTYn"; } else { NodeType* tempPtr = front; // temporary pointer ItemType item = front-> currentItem; front = front-> next; if(front == NULL) { rear = NULL; } delete tempPtr; --size; return item; } }/* end of DeQueue */ template<class ItemType> ItemType DoubleQueue<ItemType>::Front() { if(IsEmpty()) { std::cout<<"nQUEUE EMPTYn"; } else { return front-> currentItem; } }/* end of Front */ template<class ItemType> ItemType DoubleQueue<ItemType>::Rear() { if(IsEmpty()) { std::cout<<"nQUEUE EMPTYn"; } else { return rear-> currentItem; } }/* end of Rear */ template<class ItemType> int DoubleQueue<ItemType>::Size() { if(IsEmpty()) { std::cout<<"nQUEUE EMPTYn"; } return size; }/* end of Size */ template<class ItemType> void DoubleQueue<ItemType>::MakeEmpty() { if(!IsEmpty()) { std::cout << "Destroying nodes ...n"; while(!IsEmpty()) { NodeType* tempPtr = front; //std::cout << tempPtr-> currentItem << 'n'; front = front-> next; delete tempPtr; } rear = NULL; size = 0; } }/* end of MakeEmpty */ template<class ItemType> DoubleQueue<ItemType>::~DoubleQueue() { MakeEmpty(); }// http://programmingnotes.org/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210 // ============================================================================//    Author: K Perkins//    Date:   May 20, 2012//    Taken From: http://programmingnotes.org///    File:  DoubleQueue.h//    Description: This is a class which implements various functions//          demonstrating the use of a queue. // ============================================================================#include <iostream> template <class ItemType>class DoubleQueue{public: DoubleQueue(); /*   Function: Constructor initializes queue Precondition: None Postcondition: Defines private variables */ bool IsEmpty(); /*   Function: Determines whether queue is empty Precondition: Queue has been created Postcondition: The function = true if the queue is empty and the function = false if queue is not empty */ bool  IsFull(); /*   Function: Determines whether queue is full Precondition: Queue has been created Postcondition: The function = true if the queue is full and the function = false if queue is not full */ void EnQueue(ItemType item); /*   Function: Adds new item to the back of the queue Precondition:  Queue has been created and is not full Postcondition: Item is in the queue */ ItemType DeQueue(); /*   Function: Returns and then deletes the first item in the queue Precondition:  Queue has been created and is not empty Postcondition: The first item in the queue has been removed and the queue order is maintained */ ItemType Front(); /*   Function: Returns (but does not delete) the first item in the queue Precondition:  Queue has been created and is not empty Postcondition: The first item in the queue has been returned and the queue order is maintained */ ItemType Rear(); /*   Function: Returns (but does not delete) the last item in the queue Precondition:  Queue has been created and is not empty Postcondition: The last item in the queue has been returned and the queue order is maintained */ int Size();          /*   Function: Return the current size of the queue               Precondition: Queue has been initialized               Postcondition: The size of the queue is returned */ void MakeEmpty(); /*   Function: Initializes queue to an empty state Precondition: Queue has been created Postcondition: Queue no longer exists */ ~DoubleQueue(); /*   Function: Removes the queue Precondition: Queue has been declared Postcondition: Queue no longer exists */private: struct  NodeType { ItemType currentItem; NodeType* next; }; NodeType* front; // front of queue NodeType* rear; // back of queue int size;}; //=========================  Implementation  ================================// template<class ItemType>DoubleQueue<ItemType>::DoubleQueue(){ front = NULL; rear = NULL; size = 0;}/* end of DoubleQueue */ template<class ItemType>bool DoubleQueue<ItemType>::IsEmpty(){ return (front == NULL);}/* end of IsEmpty */ template<class ItemType>bool DoubleQueue<ItemType>::IsFull(){ try { NodeType* location = new NodeType; delete location; return false; } catch(std::bad_alloc&) { return true; }}/* end of IsFull */ template<class ItemType>void DoubleQueue<ItemType>::EnQueue(ItemType newItem){ if(IsFull()) { std::cout<<"nQUEUE FULLn"; } else { NodeType* newNode = new NodeType; // adds new node newNode-> currentItem = newItem; newNode-> next = NULL; if(rear == NULL) { front = newNode; } else { rear-> next = newNode; } rear = newNode; ++size; }}/* end of EnQueue */ template<class ItemType>ItemType DoubleQueue<ItemType>::DeQueue() { if(IsEmpty()) { std::cout<<"nQUEUE EMPTYn"; } else { NodeType* tempPtr = front; // temporary pointer ItemType item = front-> currentItem; front = front-> next;  if(front == NULL) { rear = NULL; } delete tempPtr; --size; return item; } }/* end of DeQueue */ template<class ItemType>ItemType DoubleQueue<ItemType>::Front() { if(IsEmpty()) { std::cout<<"nQUEUE EMPTYn"; } else { return front-> currentItem; } }/* end of Front */ template<class ItemType>ItemType DoubleQueue<ItemType>::Rear() { if(IsEmpty()) { std::cout<<"nQUEUE EMPTYn"; } else { return rear-> currentItem; } }/* end of Rear */ template<class ItemType>int DoubleQueue<ItemType>::Size(){ if(IsEmpty()) { std::cout<<"nQUEUE EMPTYn"; } return size;}/* end of Size */ template<class ItemType>void DoubleQueue<ItemType>::MakeEmpty(){ if(!IsEmpty()) { std::cout << "Destroying nodes ...n"; while(!IsEmpty()) { NodeType* tempPtr = front; //std::cout << tempPtr-> currentItem << 'n'; front = front-> next; delete tempPtr; } rear = NULL; size = 0; }}/* end of MakeEmpty */ template<class ItemType>DoubleQueue<ItemType>::~DoubleQueue() { MakeEmpty();}// http://programmingnotes.org/ ```

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

===== DEMONSTRATION HOW TO USE =====

Use of the above template class is the same as its STL counterpart. Here is a sample program demonstrating its use.

``` How To Use #include 'DoubleQueue.h' C++ #include <iostream> #include "DoubleQueue.h" using namespace std; int main() { // declare variables DoubleQueue<char> charQueue; DoubleQueue<int> intQueue; DoubleQueue<float> floatQueue; // ------ Char Example ------// char charArry[]="My Programming Notes Helped Me Succeed!"; int counter=0; while(charArry[counter]!='\0') { charQueue.EnQueue(charArry[counter]); ++counter; } cout<<"charQueue has "<<charQueue.Size()<<" items in it " <<"and contains the text:n"; while(!charQueue.IsEmpty()) { cout<<charQueue.DeQueue(); } cout<<endl; // ------ Int Example ------// int intArry[]={1,22,3,46,5,66,7,8,1987}; counter=0; while(counter<9) { intQueue.EnQueue(intArry[counter]); ++counter; } cout<<"nintQueue has "<<intQueue.Size()<<" items in it.n" <<"The sum of the numbers in the queue is: "; counter=0; while(!intQueue.IsEmpty()) { counter-=intQueue.DeQueue(); } cout<<counter<<endl; // ------ Float Example ------// float floatArry[]={41.6,2.8,43.9,4.4,19.87,6.23,7.787,68.99,9.6,81.540}; float sum=0; counter=0; while(counter<10) { floatQueue.EnQueue(floatArry[counter]); ++counter; } cout<<"nfloatQueue has "<<floatQueue.Size()<<" items in it.n" <<"The sum of the numbers in the queue is: "; while(!floatQueue.IsEmpty()) { sum-=floatQueue.DeQueue(); } cout<<sum<<endl; return 0; }// http://programmingnotes.org/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263 #include <iostream>#include "DoubleQueue.h"using namespace std; int main(){ // declare variables DoubleQueue<char> charQueue; DoubleQueue<int> intQueue; DoubleQueue<float> floatQueue; // ------ Char Example ------// char charArry[]="My Programming Notes Helped Me Succeed!"; int counter=0; while(charArry[counter]!='\0') { charQueue.EnQueue(charArry[counter]); ++counter; } cout<<"charQueue has "<<charQueue.Size()<<" items in it " <<"and contains the text:n"; while(!charQueue.IsEmpty()) { cout<<charQueue.DeQueue(); } cout<<endl; // ------ Int Example ------// int intArry[]={1,22,3,46,5,66,7,8,1987}; counter=0; while(counter<9) { intQueue.EnQueue(intArry[counter]); ++counter; } cout<<"nintQueue has "<<intQueue.Size()<<" items in it.n" <<"The sum of the numbers in the queue is: "; counter=0; while(!intQueue.IsEmpty()) { counter-=intQueue.DeQueue(); } cout<<counter<<endl; // ------ Float Example ------// float floatArry[]={41.6,2.8,43.9,4.4,19.87,6.23,7.787,68.99,9.6,81.540}; float sum=0; counter=0; while(counter<10) { floatQueue.EnQueue(floatArry[counter]); ++counter; } cout<<"nfloatQueue has "<<floatQueue.Size()<<" items in it.n" <<"The sum of the numbers in the queue is: "; while(!floatQueue.IsEmpty()) { sum-=floatQueue.DeQueue(); } cout<<sum<<endl;  return 0;}// http://programmingnotes.org/ ```

Once compiled, you should get this as your output

```charQueue has 39 items in it and contains the text: My Programming Notes Helped Me Succeed!```

``` intQueue has 9 items in it. The sum of the numbers in the queue is: -2145 ```

```floatQueue has 10 items in it. The sum of the numbers in the queue is: -286.717 ```

C++ || Snippet â€“ Linked List Custom Template Stack Sample Code

This page will consist of sample code for a custom linked list template stack. This page differs from the previously highlighted array based template stack in that this version uses a singly linked list to store data rather than using an array.

REQUIRED KNOWLEDGE FOR THIS SNIPPET

```Structs Classes Template Classes - What Are They? Stacks LIFO - What Is It? #include < stack> Linked Lists - How To Use```

This template class is a custom duplication of the Standard Template Library (STL) stack class. Whether you like building your own data structures, you simply do not like to use any inbuilt functions, opting to build everything yourself, or your homework requires you make your own data structure, this sample code is really useful. I feel its beneficial building functions such as this, that way you better understand the behind the scene processes.

``` #include 'ClassStackListType.h' C++ // ============================================================================ // Author: K Perkins // Date: Apr 9, 2012 // Taken From: http://programmingnotes.org/ // File: ClassStackListType.h // Description: This is a class which implements various functions // demonstrating the use of a stack. // ============================================================================ #include <iostream> template <class ItemType> class StackListType { public: StackListType(); /* Function: constructor initializes class variables Precondition: none Postcondition: defines private variables */ bool IsEmpty(); /* Function: Determines whether the stack is empty Precondition: Stack has been initialized Postcondition: Function value = (stack is empty) */ bool IsFull(); /* Function: Determines whether the stack is full Precondition: Stack has been initialized Postcondition: Function value = (stack is full) */ int Size(); /* Function: Return the current size of the stack Precondition: Stack has been initialized Postcondition: If (stack is full) exception FullStack is thrown else newItem is at the top of the stack */ void MakeEmpty(); /* Function: Empties the stack Precondition: Stack has been initialized Postcondition: Stack is empty */ void Push(ItemType newItem); /* Function: Adds newItem to the top of the stack Precondition: Stack has been initialized Postcondition: If (stack is full) exception FullStack is thrown else newItem is at the top of the stack */ ItemType Pop(); /* Function: Returns & then removes top item from the stack Precondition: Stack has been initialized Postcondition: If (stack is empty) exception EmptyStack is thrown else top element has been removed from the stack */ ItemType Top(); /* Function: Returns the top item from the stack Precondition: Stack has been initialized Postcondition: If (stack is empty) exception EmptyStack is thrown else top element has been removed from the stack */ ~StackListType(); /* Function: destructor deallocates class variables Precondition: none Postcondition: deallocates private variables */ private: struct NodeType { ItemType currentItem; // Variable which hold all the incoming currentItem NodeType* next; // Creates a pointer that points to the next node in the list. }; int size; // Indicates the size of the stack ItemType junk; NodeType* headPtr; // Creates a head pointer that will point to the begining of the list. }; //========================= Implementation ================================// template<class ItemType> StackListType<ItemType>::StackListType() { size = 0; headPtr = NULL; }// End of StackListType template<class ItemType> bool StackListType<ItemType>::IsEmpty() { return (headPtr == NULL); }// End of IsEmpty template<class ItemType> bool StackListType<ItemType>::IsFull() { try { NodeType* tempPtr = new NodeType; delete tempPtr; return false; } catch(std::bad_alloc&) { return true; } }// End of IsFull template<class ItemType> int StackListType<ItemType>::Size() { if(IsEmpty()) { std::cout<<"nSTACK EMPTYn"; } return size; }// End of Size template<class ItemType> void StackListType<ItemType>::MakeEmpty() { size = 0; if (!IsEmpty()) { std::cout << "Destroying nodes ...n"; while (!IsEmpty()) { NodeType* tempPtr = headPtr; //std::cout << tempPtr-> currentItem << 'n'; headPtr = headPtr-> next; delete tempPtr; } } }// End of MakeEmpty template<class ItemType> void StackListType<ItemType>::Push(ItemType newItem) { if(IsFull()) { std::cout<<"nSTACK FULLn"; return; } NodeType* tempPtr = new NodeType; tempPtr-> currentItem = newItem; tempPtr-> next = headPtr; headPtr = tempPtr; ++size; }// End of Push template<class ItemType> ItemType StackListType<ItemType>::Pop() { if(IsEmpty()) { std::cout<<"nSTACK EMPTYn"; return junk; } else { ItemType data = headPtr-> currentItem; NodeType* tempPtr = headPtr; headPtr = headPtr-> next; delete tempPtr; --size; return data; } }// End of Pop template<class ItemType> ItemType StackListType<ItemType>::Top() { if(IsEmpty()) { std::cout<<"nSTACK EMPTYn"; return junk; } else { return headPtr-> currentItem; } }// End of Top template<class ItemType> StackListType<ItemType>::~StackListType() { MakeEmpty(); }// http://programmingnotes.org/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178 // ============================================================================//    Author: K Perkins//    Date:   Apr 9, 2012//    Taken From: http://programmingnotes.org///    File:  ClassStackListType.h//    Description: This is a class which implements various functions//          demonstrating the use of a stack. // ============================================================================#include <iostream>          template <class ItemType>class StackListType{public:    StackListType();          /*   Function: constructor initializes class variables                Precondition: none               Postcondition: defines private variables */    bool IsEmpty();          /*   Function: Determines whether the stack is empty               Precondition: Stack has been initialized               Postcondition: Function value = (stack is empty) */    bool IsFull();          /*   Function: Determines whether the stack is full               Precondition: Stack has been initialized               Postcondition: Function value = (stack is full) */    int Size();          /*   Function: Return the current size of the stack               Precondition: Stack has been initialized               Postcondition: If (stack is full) exception FullStack is thrown                                   else newItem is at the top of the stack */    void MakeEmpty();          /*   Function: Empties the stack               Precondition: Stack has been initialized               Postcondition: Stack is empty */    void Push(ItemType newItem);          /*   Function: Adds newItem to the top of the stack               Precondition: Stack has been initialized               Postcondition: If (stack is full) exception FullStack is thrown                                   else newItem is at the top of the stack */    ItemType Pop();          /*   Function: Returns & then removes top item from the stack               Precondition: Stack has been initialized               Postcondition: If (stack is empty) exception EmptyStack is thrown                                   else top element has been removed from the stack */    ItemType Top();          /*   Function: Returns the top item from the stack               Precondition: Stack has been initialized               Postcondition: If (stack is empty) exception EmptyStack is thrown                                   else top element has been removed from the stack */    ~StackListType();          /*   Function: destructor deallocates class variables                Precondition: none               Postcondition: deallocates private variables */ private:    struct NodeType    {          ItemType currentItem;  // Variable which hold all the incoming currentItem          NodeType* next; // Creates a pointer that points to the next node in the list.    };    int size;          // Indicates the size of the stack     ItemType junk;    NodeType* headPtr; // Creates a head pointer that will point to the begining of the list.}; //=========================  Implementation  ================================// template<class ItemType>StackListType<ItemType>::StackListType(){    size = 0;    headPtr = NULL;}//     End of StackListType template<class ItemType>bool StackListType<ItemType>::IsEmpty(){    return (headPtr == NULL);}//     End of IsEmpty template<class ItemType>bool StackListType<ItemType>::IsFull(){        try    {        NodeType* tempPtr = new NodeType;        delete tempPtr;        return false;    }    catch(std::bad_alloc&)    {        return true;    }}//     End of IsFull template<class ItemType>int StackListType<ItemType>::Size(){    if(IsEmpty())    {        std::cout<<"nSTACK EMPTYn";    }    return size;}//     End of Size template<class ItemType>void StackListType<ItemType>::MakeEmpty(){    size = 0;         if (!IsEmpty()) {        std::cout << "Destroying nodes ...n";  while (!IsEmpty()) { NodeType* tempPtr = headPtr; //std::cout << tempPtr-> currentItem << 'n'; headPtr = headPtr-> next; delete tempPtr; } }     }//     End of MakeEmpty template<class ItemType>void StackListType<ItemType>::Push(ItemType newItem){    if(IsFull())    {        std::cout<<"nSTACK FULLn";        return;    }    NodeType* tempPtr = new NodeType;    tempPtr-> currentItem = newItem;    tempPtr-> next = headPtr;    headPtr = tempPtr;    ++size;}//     End of Push template<class ItemType>ItemType StackListType<ItemType>::Pop(){    if(IsEmpty())    {        std::cout<<"nSTACK EMPTYn";        return junk;    }    else    {          ItemType data = headPtr-> currentItem;          NodeType* tempPtr = headPtr;        headPtr = headPtr-> next;        delete tempPtr;        --size;        return data;    }}//     End of Pop template<class ItemType>ItemType StackListType<ItemType>::Top(){    if(IsEmpty())    {        std::cout<<"nSTACK EMPTYn";        return junk;    }    else    {         return headPtr-> currentItem;    }}//     End of Top template<class ItemType>StackListType<ItemType>::~StackListType(){    MakeEmpty();   }// http://programmingnotes.org/ ```

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

===== DEMONSTRATION HOW TO USE =====

Use of the above template class is the same as its STL counterpart. Here is a sample program demonstrating its use.

``` How To Use #include 'ClassStackListType.h' C++ #include <iostream> #include "ClassStackListType.h" using namespace std; int main() { // declare variables StackListType<char> charStack; StackListType<int> intStack; StackListType<float> floatStack; // ------ Char Example ------// char charArry[]="My Programming Notes Is Awesome"; int counter=0; while(charArry[counter]!='\0') { charStack.Push(charArry[counter]); ++counter; } cout<<"charStack has "<<charStack.Size()<<" items in itn" <<"and contains the text ""<<charArry<<"" backwards:n"; while(!charStack.IsEmpty()) { cout<<charStack.Pop(); } cout<<endl; // ------ Int Example ------// int intArry[]={1,22,3,46,5,66,7,8,1987}; counter=0; while(counter<9) { intStack.Push(intArry[counter]); ++counter; } cout<<"nintStack has "<<intStack.Size()<<" items in it.n" <<"The sum of the numbers in the stack is: "; counter=0; while(!intStack.IsEmpty()) { counter+=intStack.Pop(); } cout<<counter<<endl; // ------ Float Example ------// float floatArry[]={41.6,2.8,43.9,4.4,19.87,6.23,7.787,68.99,9.6,81.540}; float sum=0; counter=0; while(counter<10) { floatStack.Push(floatArry[counter]); ++counter; } cout<<"nfloatStack has "<<floatStack.Size()<<" items in it.n" <<"The sum of the numbers in the stack is: "; while(!floatStack.IsEmpty()) { sum+=floatStack.Pop(); } cout<<sum<<endl; }// http://programmingnotes.org/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960 #include <iostream>#include "ClassStackListType.h"using namespace std; int  main(){    // declare variables     StackListType<char> charStack;     StackListType<int> intStack;     StackListType<float> floatStack;          // ------ Char Example ------//     char charArry[]="My Programming Notes Is Awesome";     int counter=0;     while(charArry[counter]!='\0')     {          charStack.Push(charArry[counter]);          ++counter;     }     cout<<"charStack has "<<charStack.Size()<<" items in itn"     <<"and contains the text ""<<charArry<<"" backwards:n";     while(!charStack.IsEmpty())     {          cout<<charStack.Pop();     }     cout<<endl;               // ------ Int Example ------//     int intArry[]={1,22,3,46,5,66,7,8,1987};     counter=0;     while(counter<9)     {          intStack.Push(intArry[counter]);          ++counter;     }     cout<<"nintStack has "<<intStack.Size()<<" items in it.n"     <<"The sum of the numbers in the stack is: ";     counter=0;     while(!intStack.IsEmpty())     {          counter+=intStack.Pop();     }     cout<<counter<<endl;          // ------ Float Example ------//     float floatArry[]={41.6,2.8,43.9,4.4,19.87,6.23,7.787,68.99,9.6,81.540};     float sum=0;     counter=0;     while(counter<10)     {          floatStack.Push(floatArry[counter]);          ++counter;     }     cout<<"nfloatStack has "<<floatStack.Size()<<" items in it.n"     <<"The sum of the numbers in the stack is: ";     while(!floatStack.IsEmpty())     {          sum+=floatStack.Pop();     }     cout<<sum<<endl;     }// http://programmingnotes.org/ ```

Once compiled, you should get this as your output

```charStack has 31 items in it and contains the text "My Programming Notes Is Awesome" backwards: emosewA sI setoN gnimmargorP yM```

``` intStack has 9 items in it. The sum of the numbers in the stack is: 2145 ```

```floatStack has 10 items in it. The sum of the numbers in the stack is: 286.717 ```

C++ || Multi Process Server & Client Hash Table Using Thread Pools, Message Queues, & Signal Handlers

The following is another homework assignment which was presented in an Operating Systems Concepts class. Using commandline arguments, the following is a program which implements a multi threaded hash table, utilizing message queues to pass text from a client program to a server program and vice versa. This program makes use of multiple interprocess communication function calls provided on Unix based systems.

REQUIRED KNOWLEDGE FOR THIS PROGRAM

```How To Override The Default Signal Handler (CTRL-C) How To Create And Use Pthreads For Interprocess Communication How To Use Message Queues For Interprocess Communication Multi Process Synchronization Producer Consumer Problem Using Pthreads Sample Input Server Records File - Download Here ```

==== 1. OVERVIEW ====

Hash tables are widely used for efficient storage and retrieval of data. When using hash tables in multi threaded applications, you must ensure that concurrent accesses into the hash table is free from race conditions, dead locks, and other problems that arise in program synchronization.

One solution to overcome this problem is to prevent concurrent accesses into the hash table altogether; i.e. prior to accessing the hash table, a thread acquires a lock, and then releases the lock after the access is complete. Such approach, although simple, is inefficient. The program demonstrated on this page implements an alternative solution, one which permits safe concurrent accesses into the hash table. In the approach implemented on this page, each hash location within a hash table is protected with a separate lock. Hence, multiple threads access the hash table concurrently as long as they are accessing different hash locations. For greater efficiency, this program also makes use of a thread pool.

==== 2. TECHNICAL DETAILS ====

This program was implemented in two parts; a server program and a client program. The server side of the program maintains a hash table of records and a pool of threads. The client program requests from the server program search records by sending record ids over a message queue. The server program then retrieves a request from the message queue, and wakes up a thread in the thread pool. That awakened thread then uses the id (sent from the client program) to retrieve the corresponding record from the hash table, and sends the found record from the server program to the client program over the message queue.

The server also reads a specified file from the commandline, which stores initial user data that is to be inserted and stored into the hash table. The incoming text file has the following format:

```a unique numerical id 1 (an integer) the first name 1 (a string) the last name 1 (a string) . . . a unique numerical id N (an integer) the first name N (a string) the last name N (a string) ```

These three fields make up one single record for one individual. More than one record may be present in the incoming text file.

==== 3. SERVER ====

The server has the following structure and function:

Multi Threaded Process Server Flow Control SelectShow

The server program is invoked with the following commandline structure:

./Server [FILE NAME] [NUMBER OF THREADS] (e.g. ./Server database.dat 10)

The server is implemented below.

``` Multi Threaded Process Server With Hash Table C++ // ============================================================================= // Author: K Perkins // Date: Oct 5, 2013 // Taken From: http://programmingnotes.org/ // File: Server.cpp // Description: Using a Hash Table, this program simulates a server and client // application. The server program maintains a hash table of records and // a pool of threads. The client requests records from the server by sending // record ID's over the message queue. The server retrieves a request from // the message queue and wakes up a thread in the thread pool. The awakened // thread then uses the ID to retrieve the corresponding record from the // hash table and sends the record to the client over the message queue. // // This is the server program which creates a message queue using the msgget() // system call, checks the message queue for new messages using the msgrcv() // system call, and uses the msgsnd system call to send messages back to // the client // ============================================================================= #include <iostream> #include <vector> #include <list> #include <cstdlib> #include <cstring> #include <fstream> #include <csignal> #include <pthread.h> #include <sys/types.h> #include <sys/ipc.h> #include <sys/msg.h> #include <unistd.h> using namespace std; // Compile & Run // g++ Server.cpp -o Server -lpthread // ./Server <FILE NAME> <NUMBER OF THREADS> // function prototypes void SignalHandler(int arg); void InsertInitialDataIntoTable(ifstream& infile); void* SearchRecords(void* args); void SendRecord(int id, const char* firstName, const char* lastName); void* GenerateNewRecord(void* args); // items which are placed inside the hash table cell struct Record { int id; char firstName[50]; char lastName[50]; }; // cell for the hash table struct Cell { list<Record> cell; pthread_mutex_t mutex; }; // message queue structure struct MsgQueue { // the channel the connection will be on long messageType; int recordID; char recordName[100]; }; // constant variables const int HASH_TABLE_SIZE = 100; const int NUM_NEW_RECORDS_THREADS = 5; const int CLIENT_TO_SERVER_CHANNEL = 2; const int SERVER_TO_CLIENT_CHANNEL = 4; const int MSG_Q_ID = 0664; // global variables int msqid = 0; // message queue ID vector<Cell> hashTable(HASH_TABLE_SIZE); list<int> recievedMsg; int main(int argc, char* argv[]) { // declare variables srand(time(NULL)); signal(SIGINT, SignalHandler); // override the CTRL-C terminal singal ifstream infile; // used to read in the file int searchThreadNum = 0; // keep track of how many threads are being processed int newRecThreadNum = 0; int numSearchThreads = 0; // how many threads search the table for records key_t key = 0; // generate key to a file pthread_t* searchRecordThreads = NULL; // array of search records threads pthread_t* getNewRecordThreads = NULL; // array of new records threads MsgQueue msg; // instantiate a message queue // check if theres enough commandline args if(argc < 3) { cerr<<"n** ERROR NOT ENOUGH ARGS!nn" <<"USAGE: "<<argv[0]<<" <FILE NAME> <NUMBER OF THREADS>nn"; exit(1); } // open the input records file infile.open(argv[1]); // check to see if file exists if(infile.fail()) { cerr<<"n** ERROR: ""<<argv[1]<<"" could not be found!n"; exit(1); } // insert data into the hash table from the source file InsertInitialDataIntoTable(infile); // close the file after we are done using it infile.close(); // get the number of threads from the command line numSearchThreads = atoi(argv[2]); // initialize the search thread array with the number // specified from the commandline searchRecordThreads = new pthread_t[numSearchThreads]; // initialize the new records thread array with the // specified number getNewRecordThreads = new pthread_t[NUM_NEW_RECORDS_THREADS]; // get a key for our msg queue key = ftok("/bin/ls", 'O'); // check if we got a valid key if(key < 0) { perror("ftok error"); exit(1); } // get a msg ID msqid = msgget(key, MSG_Q_ID | IPC_CREAT); // check if we got a valid ID if(msqid < 0) { perror("msgget error"); exit(1); } cout<<"n** SERVER ID #"<<msqid<<" SUCCESSFULLY ESTABLISHEDn"<<endl; // infinite loop to send/recieve messages to/from client do{ // recieve record from client if(msgrcv(msqid, &msg, sizeof(msg) - sizeof(long), CLIENT_TO_SERVER_CHANNEL, 0) < 0) { perror("msgsnd error"); exit(1); } // save the recieved record from the client into a linked list // this is used in the "SearchRecords" function recievedMsg.push_back(msg.recordID); // --- SEARCH RECORDS THREADS // keep track of how many threads are being used if(searchThreadNum > numSearchThreads-1) { searchThreadNum = 0; } // create threads & send them to work if(pthread_create(&searchRecordThreads[searchThreadNum], NULL, &SearchRecords, NULL) < 0) { perror("pthread_create error"); exit(1); } // wait for threads to finish pthread_join(searchRecordThreads[searchThreadNum], NULL); // --- GENERATE NEW RECORDS THREADS // keep track of how many threads are being used if(newRecThreadNum > NUM_NEW_RECORDS_THREADS-1) { newRecThreadNum = 0; } // create threads & send them to work if(pthread_create(&getNewRecordThreads[newRecThreadNum], NULL, &GenerateNewRecord, NULL) < 0) { perror("pthread_create error"); exit(1); } // wait for threads to finish pthread_join(getNewRecordThreads[newRecThreadNum], NULL); // --- INCREMENT NUMBER OF THREADS BEING USED //cout<<searchThreadNum<<endl; ++searchThreadNum; ++newRecThreadNum; }while(true); return 0; }// end of main void* GenerateNewRecord(void* args) { const char* names[]={"Alva","Edda","Hiram","Lemuel","Della","Roseann","Sang", "Evelia","Claire","Marylou","Magda","Irvin","Reagan","Deb","Hillary", "Tuyetm","Cherilyn","Amina","Justin","Neville","Jessica","Demi", "Graham","Cinderella","Freddy","Vivan","Marjorie","Krystal","Liza", "Spencer","Jordon","Bernie","Geraldine","Kati","Jetta","Carmella", "Chery","Earlene","Gene","Lorri","Albertina","Ula","Karena","Johanna", "Alex","Tobias","Lashawna","Domitila","Chantel","Deneen","Nigel", "Lashanda","Donn","Theda","Many","Jeramy","Jodee","Tamra","Dessie", "Lawrence","Jaime","Basil","Roger","Cythia","Homer","Lilliam","Victoria", "Tod","Harley","Meghann","Jacquelyne","Arie","Rosemarie","Lyndon","Blanch", "Kenneth","Perkins","Kaleena"}; Record temp; int record = rand()%10000; int nameLen = sizeof(names)/sizeof(names[0]); // lock the current hash table cell if(pthread_mutex_lock(&hashTable[record%HASH_TABLE_SIZE].mutex) < 0) { perror("pthread_mutex_lock error"); exit(1); } // put the new data into the hash table temp.id = record; strncpy(temp.firstName, names[rand()%(nameLen-1)], sizeof(temp.firstName)); strncpy(temp.lastName, names[rand()%(nameLen-1)], sizeof(temp.lastName)); hashTable[record%HASH_TABLE_SIZE].cell.push_back(temp); pthread_mutex_init(&hashTable[temp.id%HASH_TABLE_SIZE].mutex, NULL); // unlock the current hash table cell if(pthread_mutex_unlock(&hashTable[record%HASH_TABLE_SIZE].mutex) < 0) { perror("pthread_mutex_lock error"); exit(1); } return 0; }// end of GenerateNewRecord void* SearchRecords(void* args) { int record = 0; bool found = false; // get the record from the client to search the hash table if(!recievedMsg.empty()) { record = recievedMsg.front(); recievedMsg.pop_front(); } //cout<<endl<<record<<endl; // if the current hash table cell isnt empty, search for the record id if(!hashTable[record%HASH_TABLE_SIZE].cell.empty()) { // lock the current hash table cell if(pthread_mutex_lock(&hashTable[record%HASH_TABLE_SIZE].mutex) < 0) { perror("pthread_mutex_lock error"); exit(1); } // search hash table cell to see if given record is there for(list<Record>::iterator iter = hashTable[record%HASH_TABLE_SIZE].cell.begin(); iter != hashTable[record%HASH_TABLE_SIZE].cell.end(); ++iter) { // we found a match in the hash table if(iter->id == record) { // set the data fields of the found record // to prepare it to be sent over the message queue SendRecord(iter->id, iter->firstName, iter->lastName); found = true; break; } } // unlock the current hash table cell if(pthread_mutex_unlock(&hashTable[record%HASH_TABLE_SIZE].mutex) < 0) { perror("pthread_mutex_lock error"); exit(1); } } // if we didnt find a record, tell that to the client if(!found) { SendRecord(-1, "Record Not Found!", ""); } return 0; }// end of SearchRecords void SendRecord(int id, const char* firstName, const char* lastName) { MsgQueue msg; // instantiate a message queue // set the message queue channel msg.messageType = SERVER_TO_CLIENT_CHANNEL; // set the record id msg.recordID = id; // set the record name strncpy(msg.recordName, firstName, sizeof(msg.recordName)); strncat(msg.recordName, " ", sizeof(msg.recordName)); strncat(msg.recordName, lastName, sizeof(msg.recordName)); // send record to client if(msgsnd(msqid, &msg, sizeof(msg) - sizeof(long), 0) < 0) { perror("msgsnd error"); exit(1); } }// end of SendRecord void InsertInitialDataIntoTable(ifstream& infile) { Record temp; while(infile>>temp.id >>temp.firstName >>temp.lastName) { hashTable[temp.id%HASH_TABLE_SIZE].cell.push_back(temp); pthread_mutex_init(&hashTable[temp.id%HASH_TABLE_SIZE].mutex, NULL); } }// end of InsertInitialDataIntoTable void SignalHandler(int arg) { cerr<<"nnCaught the CTRL-Cn" <<"Shutting down the server connection..n"; // deallocate the queue if(msgctl(msqid, IPC_RMID, NULL) < 0) { perror("msgctl error"); } exit(0); }// http://programmingnotes.org/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348 // =============================================================================//   Author: K Perkins//   Date:   Oct 5, 2013//   Taken From: http://programmingnotes.org///   File:  Server.cpp//   Description: Using a Hash Table, this program simulates a server and client //     application. The server program maintains a hash table of records and //     a pool of threads. The client requests records from the server by sending //     record ID's over the message queue. The server retrieves a request from //     the message queue and wakes up a thread in the thread pool. The awakened //     thread then uses the ID to retrieve the corresponding record from the //     hash table and sends the record to the client over the message queue.//     //     This is the server program which creates a message queue using the msgget() //     system call, checks the message queue for new messages using the msgrcv() //     system call, and uses the msgsnd system call to send messages back to //     the client// =============================================================================#include <iostream>#include <vector>#include <list>#include <cstdlib>#include <cstring>#include <fstream>#include <csignal>#include <pthread.h>#include <sys/types.h>#include <sys/ipc.h>#include <sys/msg.h>#include <unistd.h>using namespace std; // Compile & Run// g++ Server.cpp -o Server -lpthread// ./Server <FILE NAME> <NUMBER OF THREADS> // function prototypesvoid SignalHandler(int arg);void InsertInitialDataIntoTable(ifstream& infile);void* SearchRecords(void* args);void SendRecord(int id, const char* firstName, const char* lastName);void* GenerateNewRecord(void* args); // items which are placed inside the hash table cellstruct Record{    int id;    char firstName[50];    char lastName[50];}; // cell for the hash tablestruct Cell{       list<Record> cell;    pthread_mutex_t mutex;}; // message queue structurestruct MsgQueue{    // the channel the connection will be on    long messageType;    int recordID;    char recordName[100]; }; // constant variablesconst int HASH_TABLE_SIZE = 100;const int NUM_NEW_RECORDS_THREADS = 5;const int CLIENT_TO_SERVER_CHANNEL = 2;const int SERVER_TO_CLIENT_CHANNEL = 4; const int MSG_Q_ID = 0664; // global variablesint msqid = 0; // message queue IDvector<Cell> hashTable(HASH_TABLE_SIZE);list<int> recievedMsg; int main(int argc, char* argv[]){     // declare variables    srand(time(NULL));    signal(SIGINT, SignalHandler); // override the CTRL-C terminal singal     ifstream infile; // used to read in the file    int searchThreadNum = 0; // keep track of how many threads are being processed    int newRecThreadNum = 0;    int numSearchThreads = 0; // how many threads search the table for records       key_t key = 0; // generate key to a file    pthread_t* searchRecordThreads = NULL; // array of search records threads    pthread_t* getNewRecordThreads = NULL; // array of new records threads      MsgQueue msg;  // instantiate a message queue               // check if theres enough commandline args    if(argc < 3)    {        cerr<<"n** ERROR NOT ENOUGH ARGS!nn"            <<"USAGE: "<<argv[0]<<" <FILE NAME> <NUMBER OF THREADS>nn";        exit(1);    }     // open the input records file    infile.open(argv[1]);     // check to see if file exists    if(infile.fail())    {        cerr<<"n** ERROR: ""<<argv[1]<<"" could not be found!n";        exit(1);    }     // insert data into the hash table from the source file    InsertInitialDataIntoTable(infile);     // close the file after we are done using it    infile.close();            // get the number of threads from the command line     numSearchThreads = atoi(argv[2]);     // initialize the search thread array with the number     // specified from the commandline    searchRecordThreads = new pthread_t[numSearchThreads];     // initialize the new records thread array with the    // specified number    getNewRecordThreads = new pthread_t[NUM_NEW_RECORDS_THREADS];             // get a key for our msg queue    key = ftok("/bin/ls", 'O');     // check if we got a valid key    if(key < 0)    {        perror("ftok error");        exit(1);    }      // get a msg ID    msqid = msgget(key, MSG_Q_ID | IPC_CREAT);             // check if we got a valid ID    if(msqid < 0)    {        perror("msgget error");        exit(1);     }     cout<<"n** SERVER ID #"<<msqid<<" SUCCESSFULLY ESTABLISHEDn"<<endl;      // infinite loop to send/recieve messages to/from client     do{         // recieve record from client        if(msgrcv(msqid, &msg, sizeof(msg) - sizeof(long), CLIENT_TO_SERVER_CHANNEL, 0) < 0)        {            perror("msgsnd error");            exit(1);        }                     // save the recieved record from the client into a linked list        // this is used in the "SearchRecords" function        recievedMsg.push_back(msg.recordID);         // --- SEARCH RECORDS THREADS                // keep track of how many threads are being used                      if(searchThreadNum > numSearchThreads-1)        {            searchThreadNum = 0;                }          // create threads & send them to work        if(pthread_create(&searchRecordThreads[searchThreadNum], NULL, &SearchRecords, NULL) < 0)        {            perror("pthread_create error");            exit(1);        }                         // wait for threads to finish        pthread_join(searchRecordThreads[searchThreadNum], NULL);                // --- GENERATE NEW RECORDS THREADS        // keep track of how many threads are being used                      if(newRecThreadNum > NUM_NEW_RECORDS_THREADS-1)        {            newRecThreadNum = 0;                }          // create threads & send them to work        if(pthread_create(&getNewRecordThreads[newRecThreadNum], NULL, &GenerateNewRecord, NULL) < 0)        {            perror("pthread_create error");            exit(1);        }                         // wait for threads to finish        pthread_join(getNewRecordThreads[newRecThreadNum], NULL);             // --- INCREMENT NUMBER OF THREADS BEING USED               //cout<<searchThreadNum<<endl;        ++searchThreadNum;          ++newRecThreadNum;         }while(true);                 return 0;}// end of main void* GenerateNewRecord(void* args){     const char* names[]={"Alva","Edda","Hiram","Lemuel","Della","Roseann","Sang",        "Evelia","Claire","Marylou","Magda","Irvin","Reagan","Deb","Hillary",        "Tuyetm","Cherilyn","Amina","Justin","Neville","Jessica","Demi",        "Graham","Cinderella","Freddy","Vivan","Marjorie","Krystal","Liza",        "Spencer","Jordon","Bernie","Geraldine","Kati","Jetta","Carmella",        "Chery","Earlene","Gene","Lorri","Albertina","Ula","Karena","Johanna",        "Alex","Tobias","Lashawna","Domitila","Chantel","Deneen","Nigel",        "Lashanda","Donn","Theda","Many","Jeramy","Jodee","Tamra","Dessie",        "Lawrence","Jaime","Basil","Roger","Cythia","Homer","Lilliam","Victoria",        "Tod","Harley","Meghann","Jacquelyne","Arie","Rosemarie","Lyndon","Blanch",        "Kenneth","Perkins","Kaleena"};            Record temp;    int record = rand()%10000;            int nameLen = sizeof(names)/sizeof(names[0]);       // lock the current hash table cell    if(pthread_mutex_lock(&hashTable[record%HASH_TABLE_SIZE].mutex) < 0)    {        perror("pthread_mutex_lock error");        exit(1);    }         // put the new data into the hash table    temp.id = record;    strncpy(temp.firstName, names[rand()%(nameLen-1)], sizeof(temp.firstName));    strncpy(temp.lastName, names[rand()%(nameLen-1)], sizeof(temp.lastName));     hashTable[record%HASH_TABLE_SIZE].cell.push_back(temp);    pthread_mutex_init(&hashTable[temp.id%HASH_TABLE_SIZE].mutex, NULL);            // unlock the current hash table cell    if(pthread_mutex_unlock(&hashTable[record%HASH_TABLE_SIZE].mutex) < 0)    {        perror("pthread_mutex_lock error");        exit(1);    }    return 0; }// end of GenerateNewRecord void* SearchRecords(void* args){     int record = 0;    bool found = false;     // get the record from the client to search the hash table    if(!recievedMsg.empty())    {        record = recievedMsg.front();        recievedMsg.pop_front();    }    //cout<<endl<<record<<endl;     // if the current hash table cell isnt empty, search for the record id    if(!hashTable[record%HASH_TABLE_SIZE].cell.empty())    {           // lock the current hash table cell        if(pthread_mutex_lock(&hashTable[record%HASH_TABLE_SIZE].mutex) < 0)        {            perror("pthread_mutex_lock error");            exit(1);        }                // search hash table cell to see if given record is there        for(list<Record>::iterator iter = hashTable[record%HASH_TABLE_SIZE].cell.begin();             iter != hashTable[record%HASH_TABLE_SIZE].cell.end(); ++iter)        {            // we found a match in the hash table            if(iter->id == record)            {                // set the data fields of the found record                 // to prepare it to be sent over the message queue                                SendRecord(iter->id, iter->firstName, iter->lastName);                found = true;                break;            }        }         // unlock the current hash table cell         if(pthread_mutex_unlock(&hashTable[record%HASH_TABLE_SIZE].mutex) < 0)        {            perror("pthread_mutex_lock error");            exit(1);        }    }     // if we didnt find a record, tell that to the client    if(!found)    {        SendRecord(-1, "Record Not Found!", "");    }    return 0; }// end of SearchRecords void SendRecord(int id, const char* firstName, const char* lastName){    MsgQueue msg;  // instantiate a message queue     // set the message queue channel    msg.messageType = SERVER_TO_CLIENT_CHANNEL;          // set the record id    msg.recordID = id;                     // set the record name    strncpy(msg.recordName, firstName, sizeof(msg.recordName));    strncat(msg.recordName, " ", sizeof(msg.recordName));    strncat(msg.recordName, lastName, sizeof(msg.recordName));              // send record to client    if(msgsnd(msqid, &msg, sizeof(msg) - sizeof(long), 0) < 0)    {        perror("msgsnd error");        exit(1);    }    }// end of SendRecord    void InsertInitialDataIntoTable(ifstream& infile){      Record temp;    while(infile>>temp.id >>temp.firstName >>temp.lastName)    {        hashTable[temp.id%HASH_TABLE_SIZE].cell.push_back(temp);        pthread_mutex_init(&hashTable[temp.id%HASH_TABLE_SIZE].mutex, NULL);    }   }// end of InsertInitialDataIntoTable void SignalHandler(int arg){    cerr<<"nnCaught the CTRL-Cn"        <<"Shutting down the server connection..n";      // deallocate the queue     if(msgctl(msqid, IPC_RMID, NULL) < 0)    {        perror("msgctl error");    }     exit(0);}// http://programmingnotes.org/ ```

The client program has a much easier flow of control. It is implemented below.

==== 4. CLIENT ====

The client has the following structure and function:

Multi Threaded Process Client Flow Control SelectShow

The client program was designed to sleep for 1 second every time a new record is obtained from the server. This makes it so its easier for the user to see what is being displayed on the screen.

The client program is invoked with the following commandline structure:

./client

The client is implemented below.

``` Multi Threaded Process Server With Hash Table C++ // ============================================================================= // Author: K Perkins // Date: Oct 5, 2013 // Taken From: http://programmingnotes.org/ // File: Client.cpp // Description: Using a Hash Table, this program simulates a server and client // application. The server program maintains a hash table of records and // a pool of threads. The client requests records from the server by sending // record ID's over the message queue. The server retrieves a request from // the message queue and wakes up a thread in the thread pool. The awakened // thread then uses the ID to retrieve the corresponding record from the // hash table and sends the record to the client over the message queue. // // This is the client program which connects to the message queue that the // server previously establishes using the msgget() system call. It checks // the message queue for sucessfully found records using the msgrcv() system // call, and uses the msgsnd system call to send new search records back to // the server, where it searches for new records // // NOTE: This file is set to display records on a 1 second delay // ============================================================================= #include <iostream> #include <cstdlib> #include <ctime> #include <unistd.h> #include <sys/types.h> #include <sys/ipc.h> #include <sys/msg.h> using namespace std; // Compile & Run // g++ Client.cpp -o Client // ./Client // message queue structure struct MsgQueue { // the channel the connection will be on long messageType; int recordID; char recordName[100]; }; // constant variables const int HOW_LONG_TO_SLEEP = 1; const int CLIENT_TO_SERVER_CHANNEL = 2; const int SERVER_TO_CLIENT_CHANNEL = 4; const int MSG_Q_ID = 0664; int main() { // declare variables MsgQueue msg; srand(time(NULL)); key_t key = 0; int msqid = 0; // message queue ID // get a key for the queue key = ftok("/bin/ls", 'O'); // check if we got a valid key if(key < 0) { cerr<<"ftok"; exit(1); } // get the ID of the queue msqid = msgget(key,MSG_Q_ID); // check if we got a valid ID if(msqid < 0) { cerr<<"n** ERROR - CONNECTION TO SERVER NOT FOUNDnn"; exit(1); } cerr<<"n** CONNECTION TO SERVER ID #"<<msqid<<" SUCCESSn"<<endl; // infinite loop to send/recieve messages from server do{ // connect to the server msg.messageType = CLIENT_TO_SERVER_CHANNEL; // generate a random search key msg.recordID = rand()%10000; // send record search to the server if(msgsnd(msqid, &msg, sizeof(msg) - sizeof(long), 0) < 0) { cerr<<"n** SERVER CONNECTION CLOSED..nn"; exit(1); } // recieve a record from the server if(msgrcv(msqid, &msg, sizeof(msg) - sizeof(long), SERVER_TO_CLIENT_CHANNEL, 0) < 0) { cerr<<"n** SERVER CONNECTION CLOSED..nn"; exit(1); } // if we found a valid record, display it to the screen if(msg.recordID > 0) { cerr<< "ID = "<<msg.recordID<<" tRecord = "<<msg.recordName<<endl; sleep(HOW_LONG_TO_SLEEP); } }while(true); return 0; }// http://programmingnotes.org/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111 // =============================================================================//   Author: K Perkins//   Date:   Oct 5, 2013//   Taken From: http://programmingnotes.org///   File:  Client.cpp//   Description: Using a Hash Table, this program simulates a server and client //     application. The server program maintains a hash table of records and //     a pool of threads. The client requests records from the server by sending //     record ID's over the message queue. The server retrieves a request from //     the message queue and wakes up a thread in the thread pool. The awakened //     thread then uses the ID to retrieve the corresponding record from the //     hash table and sends the record to the client over the message queue.//     //     This is the client program which connects to the message queue that the //     server previously establishes using the msgget() system call. It checks //     the message queue for sucessfully found records using the msgrcv() system //     call, and uses the msgsnd system call to send new search records back to //     the server, where it searches for new records// //     NOTE: This file is set to display records on a 1 second delay// =============================================================================#include <iostream>#include <cstdlib>#include <ctime>#include <unistd.h>#include <sys/types.h>#include <sys/ipc.h>#include <sys/msg.h>using namespace std; // Compile & Run// g++ Client.cpp -o Client// ./Client // message queue structurestruct MsgQueue{    // the channel the connection will be on long messageType; int recordID; char recordName[100]; }; // constant variablesconst int HOW_LONG_TO_SLEEP = 1;const int CLIENT_TO_SERVER_CHANNEL = 2;const int SERVER_TO_CLIENT_CHANNEL = 4;const int MSG_Q_ID = 0664; int main(){    // declare variables    MsgQueue msg;    srand(time(NULL));    key_t key = 0;    int msqid = 0; // message queue ID            // get a key for the queue    key = ftok("/bin/ls", 'O');     // check if we got a valid key    if(key < 0)    {        cerr<<"ftok";        exit(1);    }      // get the ID of the queue     msqid = msgget(key,MSG_Q_ID);      // check if we got a valid ID    if(msqid < 0)    {        cerr<<"n** ERROR - CONNECTION TO SERVER NOT FOUNDnn";        exit(1);     }      cerr<<"n** CONNECTION TO SERVER ID #"<<msqid<<" SUCCESSn"<<endl;      // infinite loop to send/recieve messages from server     do{             // connect to the server        msg.messageType = CLIENT_TO_SERVER_CHANNEL;         // generate a random search key        msg.recordID = rand()%10000;                // send record search to the server        if(msgsnd(msqid, &msg, sizeof(msg) - sizeof(long), 0) < 0)        {            cerr<<"n** SERVER CONNECTION CLOSED..nn";            exit(1);        }                // recieve a record from the server        if(msgrcv(msqid, &msg, sizeof(msg) - sizeof(long), SERVER_TO_CLIENT_CHANNEL, 0) < 0)        {            cerr<<"n** SERVER CONNECTION CLOSED..nn";            exit(1);        }                // if we found a valid record, display it to the screen        if(msg.recordID > 0)        {            cerr<< "ID = "<<msg.recordID<<"  tRecord = "<<msg.recordName<<endl;            sleep(HOW_LONG_TO_SLEEP);        }                      }while(true);         return 0;}// http://programmingnotes.org/ ```

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

See sample files named server.cpp and client.cpp which illustrate interprocess communications using message queues. See file condvar.cpp which illustrates the use of condition variables. Finally, see file signal.cpp which illustrates the overriding of default signal handlers.

The following is sample output:
(Note: remember to include the initial records input file!)

SERVER OUTPUT:

`./Server INPUT_Records_programmingnotes_freeweq_com.txt 26`

``` ** SERVER ID #1015808 SUCCESSFULLY ESTABLISHED ^C ```

```Caught the CTRL-C Shutting down the server connection.. ```

CLIENT OUTPUT:

`./Client`

``` ** CONNECTION TO SERVER ID #1015808 SUCCESS ID = 243 Record = Graham Basil ID = 7943 Record = Tobias Arie ID = 3607 Record = Claire Amina ID = 849 Record = Jetta Victoria ID = 126 Record = Jeramy Tod ID = 7483 Record = Vivan Krystal ID = 8036 Record = Lilliam Harley ID = 1901 Record = Kati Basil ID = 3524 Record = Kenneth Perkins ID = 5256 Record = Jodee Albertina ID = 7065 Record = Marylou Donn ID = 3951 Record = Ula Domitila ID = 395 Record = Jaime Lilliam ID = 9234 Record = Nigel Gene ID = 4148 Record = Carmella Evelia ID = 9340 Record = Sang Cherilyn ID = 3834 Record = Jessica Freddy ```

```** SERVER CONNECTION CLOSED.. ```

C++ || Custom Template Hash Map With Iterator Using Separate Chaining

Before we get into the code, what is a Hash Map? Simply put, a Hash Map is an extension of a Hash Table; which is a data structure used to map unique “keys” to specific “values.” The Hash Map demonstrated on this page is different from the previous Hash Table implementation in that key/value pairs do not need to be the same datatype, they can be completely different. So for example, if you wish to map a string “key” to an integer “value“, utilizing a Hash Map is ideal.

In its most simplest form, a Hash Map can be thought of as an associative array, or a “dictionary.” Hash Map’s are composed of a collection of key/value pairs, such that each possible key appears atleast once in the collection for a given value. While a standard array requires that indice subscripts be integers, a hash map can use a string, an integer, or even a floating point value as the index. That index is called the “key,” and the contents within the array at that specific index location is called the “value.” A hash map uses a hash function to generate an index into the table, creating buckets or slots, from which the correct value can be found.

To illustrate, suppose that you’re working with some data that has values associated with strings — for instance, you might have student names and you wish to assign them grades. How would you store this data? Depending on your skill level, you might use multiple arrays during the implementation. For example, in terms of a one dimensional array, if we wanted to access the data for a student located at index #25, we could access it by doing:

``` studentNames[25]; // do something with the data studentGrades[25]; ```

Here, we dont have to search through each element in the array to find what we need, we just access it at index #25. The question is, how do we know that index #25 holds the data that we are looking for? If we have a large set of data, not only will keeping track of multiple arrays become tiresome, but doing a sequential search over each item within the separate arrays can become very inefficient. That is where hashing comes in handy. Using a Hash Map, we can use the students name as the “key,” and the students grade as the data “value.” Given this “key” (the students name), we can apply a hash function to map a unique index or bucket within the hash table to find the data “value” (the students grade) that we wish to access.

So in essence, a Hash Map is an extension of a hash table, which is a data structure that stores key/value pairs. Hash tables are typically used because they are ideal for doing a quick search of items.

Though hashing is ideal, it isnt perfect. It is possible for multiple “keys” to be hashed into the same location. Hash “collisions” are practically unavoidable when hashing large data sets. The code demonstrated on this page handles collisions via separate chaining, utilizing an array of linked list head nodes to store multiple keys within one bucket – should any collisions occur.

A special feature of this current hash map class is that its implemented as a multimap, meaning that more than one “value” can be associated with a given “key.” For example, in a student enrollment system where students may be enrolled in multiple classes simultaneously, there might be an association for each enrollment where the “key” is the student ID, and the “value” is the course ID. In this example, if a given student is enrolled in three courses, there will be three associated “values” (course ID’s) for one “key” (student ID) in the Hash Map.

An iterator was also implemented, making data access that much more simple within the hash map class. Click here for an overview demonstrating how custom iterators can be built.

=== CUSTOM TEMPLATE HASH MAP WITH ITERATOR ===

``` #include 'HashMap.h' - Hash Map With Iterator C++ // ============================================================================ // Author: Kenneth Perkins // Date: June 11, 2013 // Taken From: http://programmingnotes.org/ // File: HashMap.h // Description: This is a class which implements various functions // demonstrating the use of a Hash Map. // ============================================================================ #ifndef TEMPLATE_HASH_MAP #define TEMPLATE_HASH_MAP #include <iostream> #include <string> #include <sstream> #include <cstdlib> // if user doesnt define, this is the // default hash map size const int HASH_SIZE = 350; template <class Key, class Value> class HashMap { public: HashMap(int hashSze = HASH_SIZE); /* Function: Constructor initializes hash map Precondition: None Postcondition: Defines private variables */ bool IsEmpty(int keyIndex); /* Function: Determines whether hash map is empty at the given hash map key index Precondition: Hash map has been created Postcondition: The function = true if the hash map is empty and the function = false if hash map is not empty */ bool IsFull(); /* Function: Determines whether hash map is full Precondition: Hash map has been created Postcondition: The function = true if the hash map is full and the function = false if hash map is not full */ int Hash(Key m_key); /* Function: Computes and returns a hash map key index for a given item The returned key index is the given cell where the item resides Precondition: Hash map has been created and is not full Postcondition: The hash key is returned */ void Insert(Key m_key, Value m_value); /* Function: Adds new item to the back of the list at a given key in the hash map A unique hash key is automatically generated for each new item Precondition: Hash map has been created and is not full Postcondition: Item is in the hash map */ bool Remove(Key m_key, Value deleteItem); /* Function: Removes the first instance from the map whose value is "deleteItem" Precondition: Hash map has been created and is not empty Postcondition: The function = true if deleteItem is found and the function = false if deleteItem is not found */ void Sort(int keyIndex); /* Function: Sort the items in the map at the given hashmap key index Precondition: Hash map has been initialized Postcondition: The hash map is sorted */ int TableSize(); /* Function: Return the size of the hash map Precondition: Hash map has been initialized Postcondition: The size of the hash map is returned */ int TotalElems(); /* Function: Return the total number of elements contained in the hash map Precondition: Hash map has been initialized Postcondition: The size of the hash map is returned */ int BucketSize(int keyIndex); /* Function: Return the number of items contained in the hash map cell at the given hashmap key index Precondition: Hash map has been initialized Postcondition: The size of the given key cell is returned */ int Count(Key m_key, Value searchItem); /* Function: Return the number of times searchItem appears in the map at the given key Precondition: Hash map has been initialized Postcondition: The number of times searchItem appears in the map is returned */ int ContainsKey(Key m_key); /* Function: Return the number of times the given key appears in the hashmap Precondition: Hash map has been initialized Postcondition: The number of times the given key appears in the map is returned */ void MakeEmpty(); /* Function: Initializes hash map to an empty state Precondition: Hash map has been created Postcondition: Hash map no longer exists */ ~HashMap(); /* Function: Removes the hash map Precondition: Hash map has been declared Postcondition: Hash map no longer exists */ // -- ITERATOR CLASS -- class Iterator; /* Function: Class declaration to the iterator Precondition: Hash map has been declared Postcondition: Hash Iterator has been declared */ Iterator begin(int keyIndex){return(!IsEmpty(keyIndex)) ? head[keyIndex]:NULL;} /* Function: Returns the beginning of the current hashmap key index Precondition: Hash map has been declared Postcondition: Hash cell has been returned to the Iterator */ Iterator end(int keyIndex=0){return NULL;} /* Function: Returns the end of the current hashmap key index Precondition: Hash map has been declared Postcondition: Hash cell has been returned to the Iterator */ private: struct KeyValue // struct to hold key/value pairs { Key key; Value value; }; struct node { KeyValue currentItem; node* next; }; node** head; // array of linked list declaration - front of each hash map cell int hashSize; // the size of the hash map (how many cells it has) int totElems; // holds the total number of elements in the entire table int* bucketSize; // holds the total number of elems in each specific hash map cell }; //========================= Implementation ================================// template <class Key, class Value> HashMap<Key, Value>::HashMap(int hashSze) { hashSize = hashSze; head = new node*[hashSize]; bucketSize = new int[hashSize]; for(int x=0; x < hashSize; ++x) { head[x] = NULL; bucketSize[x] = 0; } totElems = 0; }/* End of HashMap */ template <class Key, class Value> bool HashMap<Key, Value>::IsEmpty(int keyIndex) { if(keyIndex >=0 && keyIndex < hashSize) { return head[keyIndex] == NULL; } return true; }/* End of IsEmpty */ template <class Key, class Value> bool HashMap<Key, Value>::IsFull() { try { node* location = new node; delete location; return false; } catch(std::bad_alloc&) { return true; } }/* End of IsFull */ template <class Key, class Value> int HashMap<Key, Value>::Hash(Key m_key) { long h = 19937; std::stringstream convert; // convert the parameter to a string using "stringstream" which is done // so we can hash multiple datatypes using only one function convert << m_key; std::string temp = convert.str(); for(unsigned x=0; x < temp.length(); ++x) { h = (h << 6) ^ (h >> 26) ^ temp[x]; } return abs(h % hashSize); } /* End of Hash */ template <class Key, class Value> void HashMap<Key, Value>::Insert(Key m_key, Value m_value) { if(IsFull()) { //std::cout<<"\nINSERT ERROR - HASH MAP FULL\n"; } else { int keyIndex = Hash(m_key); node* newNode = new node; // add new node newNode-> currentItem.key = m_key; newNode-> currentItem.value = m_value; newNode-> next = NULL; if(IsEmpty(keyIndex)) { head[keyIndex] = newNode; } else { node* temp = head[keyIndex]; while(temp-> next != NULL) { temp = temp-> next; } temp-> next = newNode; } ++bucketSize[keyIndex]; ++totElems; } }/* End of Insert */ template <class Key, class Value> bool HashMap<Key, Value>::Remove(Key m_key, Value deleteItem) { bool isFound = false; node* temp; int keyIndex = Hash(m_key); if(IsEmpty(keyIndex)) { //std::cout<<"\nREMOVE ERROR - HASH MAP EMPTY\n"; } else if(head[keyIndex]->currentItem.key == m_key && head[keyIndex]->currentItem.value == deleteItem) { temp = head[keyIndex]; head[keyIndex] = head[keyIndex]-> next; delete temp; --totElems; --bucketSize[keyIndex]; isFound = true; } else { for(temp = head[keyIndex];temp->next!=NULL;temp=temp->next) { if(temp->next->currentItem.key == m_key && temp->next->currentItem.value == deleteItem) { node* deleteNode = temp->next; temp-> next = temp-> next-> next; delete deleteNode; isFound = true; --totElems; --bucketSize[keyIndex]; break; } } } return isFound; }/* End of Remove */ template <class Key, class Value> void HashMap<Key, Value>::Sort(int keyIndex) { if(IsEmpty(keyIndex)) { //std::cout<<"\nSORT ERROR - HASH MAP EMPTY\n"; } else { int listSize = BucketSize(keyIndex); bool sorted = false; do{ sorted = true; int x = 0; for(node* temp = head[keyIndex]; temp->next!=NULL && x < listSize-1; temp=temp->next,++x) { if(temp-> currentItem.value > temp->next->currentItem.value) { std::swap(temp-> currentItem,temp->next->currentItem); sorted = false; } } --listSize; }while(!sorted); } }/* End of Sort */ template <class Key, class Value> int HashMap<Key, Value>::TableSize() { return hashSize; }/* End of TableSize */ template <class Key, class Value> int HashMap<Key, Value>::TotalElems() { return totElems; }/* End of TotalElems */ template <class Key, class Value> int HashMap<Key, Value>::BucketSize(int keyIndex) { return(!IsEmpty(keyIndex)) ? bucketSize[keyIndex]:0; }/* End of BucketSize */ template <class Key, class Value> int HashMap<Key, Value>::Count(Key m_key, Value searchItem) { int keyIndex = Hash(m_key); int search = 0; if(IsEmpty(keyIndex)) { //std::cout<<"\nCOUNT ERROR - HASH MAP EMPTY\n"; } else { for(node* temp = head[keyIndex];temp!=NULL;temp=temp->next) { if(temp->currentItem.key == m_key && temp->currentItem.value == searchItem) { ++search; } } } return search; }/* End of Count */ template <class Key, class Value> int HashMap<Key, Value>::ContainsKey(Key m_key) { int keyIndex = Hash(m_key); int search = 0; if(IsEmpty(keyIndex)) { //std::cout<<"\nCONTAINS KEY ERROR - HASH MAP EMPTY\n"; } else { for(node* temp = head[keyIndex];temp!=NULL;temp=temp->next) { if(temp->currentItem.key == m_key) { ++search; } } } return search; }/* End of ContainsKey */ template <class Key, class Value> void HashMap<Key, Value>::MakeEmpty() { totElems = 0; for(int x=0; x < hashSize; ++x) { if(!IsEmpty(x)) { //std::cout << "Destroying nodes ...\n"; while(!IsEmpty(x)) { node* temp = head[x]; //std::cout << temp-> currentItem.value <<std::endl; head[x] = head[x]-> next; delete temp; } } bucketSize[x] = 0; } }/* End of MakeEmpty */ template <class Key, class Value> HashMap<Key, Value>::~HashMap() { MakeEmpty(); delete[] head; delete[] bucketSize; }/* End of ~HashMap */ // END OF THE HASH MAP CLASS // ----------------------------------------------------------- // START OF THE HASH MAP ITERATOR CLASS template <class Key, class Value> class HashMap<Key, Value>::Iterator : public std::iterator<std::forward_iterator_tag,Value>, public HashMap<Key, Value> { public: // Iterator constructor Iterator(node* otherIter = NULL) { itHead = otherIter; } ~Iterator() {} // The assignment and relational operators are straightforward Iterator& operator=(const Iterator& other) { itHead = other.itHead; return(*this); } bool operator==(const Iterator& other)const { return itHead == other.itHead; } bool operator!=(const Iterator& other)const { return itHead != other.itHead; } bool operator<(const Iterator& other)const { return itHead < other.itHead; } bool operator>(const Iterator& other)const { return other.itHead < itHead; } bool operator<=(const Iterator& other)const { return (!(other.itHead < itHead)); } bool operator>=(const Iterator& other)const { return (!(itHead < other.itHead)); } // Update my state such that I refer to the next element in the // HashMap. Iterator operator+(int incr) { node* temp = itHead; for(int x=0; x < incr && temp!= NULL; ++x) { temp = temp->next; } return temp; } Iterator operator+=(int incr) { for(int x=0; x < incr && itHead!= NULL; ++x) { itHead = itHead->next; } return itHead; } Iterator& operator++() // pre increment { if(itHead != NULL) { itHead = itHead->next; } return(*this); } Iterator operator++(int) // post increment { node* temp = itHead; this->operator++(); return temp; } KeyValue& operator[](int incr) { // Return "junk" data // to prevent the program from crashing if(itHead == NULL || (*this + incr) == NULL) { return junk; } return(*(*this + incr)); } // Return a reference to the value in the node. I do this instead // of returning by value so a caller can update the value in the // node directly. KeyValue& operator*() { // Return "junk" data // to prevent the program from crashing if(itHead == NULL) { return junk; } return itHead->currentItem; } KeyValue* operator->() { return(&**this); } private: node* itHead; KeyValue junk; }; #endif // http://programmingnotes.org/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489 // ============================================================================//    Author: Kenneth Perkins//    Date:   June 11, 2013//    Taken From: http://programmingnotes.org///    File:  HashMap.h//    Description: This is a class which implements various functions//          demonstrating the use of a Hash Map.// ============================================================================#ifndef TEMPLATE_HASH_MAP#define TEMPLATE_HASH_MAP#include <iostream>#include <string>#include <sstream>#include <cstdlib> // if user doesnt define, this is the// default hash map sizeconst int HASH_SIZE = 350; template <class Key, class Value>class HashMap{public:    HashMap(int hashSze = HASH_SIZE);        /*   Function: Constructor initializes hash map            Precondition: None            Postcondition: Defines private variables */    bool IsEmpty(int keyIndex);        /*   Function: Determines whether hash map is empty at the given hash                            map key index            Precondition: Hash map has been created            Postcondition: The function = true if the hash map is empty and the                             function = false if hash map is not empty */    bool  IsFull();        /*   Function: Determines whether hash map is full            Precondition: Hash map has been created            Postcondition: The function = true if the hash map is full and the                             function = false if hash map is not full */    int Hash(Key m_key);        /*   Function: Computes and returns a hash map key index for a given item                        The returned key index is the given cell where the item resides            Precondition:  Hash map has been created and is not full            Postcondition: The hash key is returned */    void Insert(Key m_key, Value m_value);        /*   Function: Adds new item to the back of the list at a given key in the hash map                         A unique hash key is automatically generated for each new item            Precondition:  Hash map has been created and is not full            Postcondition: Item is in the hash map */    bool Remove(Key m_key, Value deleteItem);        /*   Function: Removes the first instance from the map whose value is "deleteItem"            Precondition:  Hash map has been created and is not empty            Postcondition: The function = true if deleteItem is found and the                             function = false if deleteItem is not found */    void Sort(int keyIndex);        /*   Function: Sort the items in the map at the given hashmap key index            Precondition: Hash map has been initialized            Postcondition: The hash map is sorted */    int TableSize();        /*   Function: Return the size of the hash map            Precondition: Hash map has been initialized            Postcondition: The size of the hash map is returned */    int TotalElems();        /*   Function: Return the total number of elements contained in the hash map            Precondition: Hash map has been initialized            Postcondition: The size of the hash map is returned */    int BucketSize(int keyIndex);        /*   Function: Return the number of items contained in the hash map                        cell at the given hashmap key index            Precondition: Hash map has been initialized            Postcondition: The size of the given key cell is returned */    int Count(Key m_key, Value searchItem);        /*   Function: Return the number of times searchItem appears in the map                        at the given key            Precondition: Hash map has been initialized            Postcondition: The number of times searchItem appears in the map is returned */    int ContainsKey(Key m_key);        /*   Function: Return the number of times the given key appears in the hashmap            Precondition: Hash map has been initialized            Postcondition: The number of times the given key appears in the map is returned */    void MakeEmpty();        /*   Function: Initializes hash map to an empty state            Precondition: Hash map has been created            Postcondition: Hash map no longer exists */    ~HashMap();        /*   Function: Removes the hash map            Precondition: Hash map has been declared            Postcondition: Hash map no longer exists */     //  -- ITERATOR CLASS --    class Iterator;        /*   Function: Class declaration to the iterator            Precondition: Hash map has been declared            Postcondition: Hash Iterator has been declared */     Iterator begin(int keyIndex){return(!IsEmpty(keyIndex)) ? head[keyIndex]:NULL;}        /*   Function: Returns the beginning of the current hashmap key index            Precondition: Hash map has been declared            Postcondition: Hash cell has been returned to the Iterator */     Iterator end(int keyIndex=0){return NULL;}        /*   Function: Returns the end of the current hashmap key index            Precondition: Hash map has been declared            Postcondition: Hash cell has been returned to the Iterator */ private:    struct KeyValue  // struct to hold key/value pairs    {        Key key;        Value value;    };    struct node    {        KeyValue currentItem;        node* next;    };    node** head; // array of linked list declaration - front of each hash map cell    int hashSize; // the size of the hash map (how many cells it has)    int totElems; // holds the total number of elements in the entire table    int* bucketSize; // holds the total number of elems in each specific hash map cell}; //=========================  Implementation  ================================// template <class Key, class Value>HashMap<Key, Value>::HashMap(int hashSze){    hashSize = hashSze;    head = new node*[hashSize];    bucketSize = new int[hashSize];    for(int x=0; x < hashSize; ++x)    {        head[x] = NULL;        bucketSize[x] = 0;    }    totElems = 0;}/* End of HashMap */ template <class Key, class Value>bool HashMap<Key, Value>::IsEmpty(int keyIndex){    if(keyIndex >=0 && keyIndex < hashSize)    {        return head[keyIndex] == NULL;    }    return true;}/* End of IsEmpty */ template <class Key, class Value>bool HashMap<Key, Value>::IsFull(){    try    {        node* location = new node;        delete location;        return false;    }    catch(std::bad_alloc&)    {        return true;    }}/* End of IsFull */ template <class Key, class Value>int HashMap<Key, Value>::Hash(Key m_key)```