## 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++ || 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; // do something with the data studentGrades; ```

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){    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/ ```

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

The iterator class starts on line #381, and is built to support most of the standard relational operators, as well as arithmetic operators such as ‘+,+=,++’ (pre/post increment). The * (star), bracket [] and -> arrow operators are also supported. Click here for an overview demonstrating how custom iterators can be built.

The rest of 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 many of its STL template class counterparts. Here are sample programs demonstrating its use.

``` #1 - Demonstrate Basic Use C++ // DEMONSTRATE BASIC USE AND THE REMOVE / SORT FUNCTIONS #include <iostream> #include <string> #include "HashMap.h" using namespace std; // iterator declaration typedef HashMap<string, int>::Iterator iterDec; int main() { // declare variables HashMap<string, int> hashMap; // place items into the hash map using the 'insert' function // NOTE: its OK for dupicate keys to be inserted into the hash map hashMap.Insert("BIOL", 585); hashMap.Insert("CPSC", 386); hashMap.Insert("ART", 101); hashMap.Insert("CPSC", 462); hashMap.Insert("HIST", 251); hashMap.Insert("CPSC", 301); hashMap.Insert("MATH", 270); hashMap.Insert("PE", 145); hashMap.Insert("BIOL", 134); hashMap.Insert("GEOL", 201); hashMap.Insert("CIS", 465); hashMap.Insert("CPSC", 240); hashMap.Insert("GEOL", 101); hashMap.Insert("MATH", 150); hashMap.Insert("DANCE", 134); hashMap.Insert("CPSC", 131); hashMap.Insert("ART", 345); hashMap.Insert("CHEM", 185); hashMap.Insert("PE", 125); hashMap.Insert("CPSC", 120); // display the number of times the key "CPSC" appears in the hashmap cout<<"The key 'CPSC' appears in the hash map "<< hashMap.ContainsKey("CPSC")<<" time(s)\n"; // declare an iterator for the "CPSC" key so we can display data to screen iterDec it = hashMap.begin(hashMap.Hash("CPSC")); // display the first value cout<<"\nThe first item with the key 'CPSC' is: " <<it.value<<endl; // display all the values in the hash map whose key matches "CPSC" // NOTE: its possible for multiple different keys types // to be placed into the same hash map bucket cout<<"\nThese are all the items in the hash map whose key is 'CPSC': \n"; for(int x=0; x < hashMap.BucketSize(hashMap.Hash("CPSC")); ++x) { if(it[x].key == "CPSC") // make sure this is the key we are looking for { cout<<" Key-> "<<it[x].key<<"\tValue-> "<<it[x].value<<endl; } } // remove the first value from the key "CPSC" cout<<"\n[REMOVE THE VALUE '"<<it.value<<"' FROM THE KEY '"<<it.key<<"']\n"; hashMap.Remove("CPSC",it.value); // display the number of times the key "CPSC" appears in the hashmap cout<<"\nNow the key 'CPSC' only appears in the hash map "<< hashMap.ContainsKey("CPSC")<<" time(s)\n"; // update the iterator to the current hash map state it = hashMap.begin(hashMap.Hash("CPSC")); // sort the values in the hash map bucket whose key is "CSPC" hashMap.Sort(hashMap.Hash("CPSC")); // display the values whose key matches "CPSC" cout<<"\nThese are the sorted items in the hash map whose key is 'CPSC': \n"; for(int x=0; x < hashMap.BucketSize(hashMap.Hash("CPSC")); ++x) { if(it[x].key == "CPSC") { cout<<" Key-> "<<it[x].key<<"\tValue-> "<<it[x].value<<endl; } } // display all the key/values in the entire hash map cout<<"\nThese are all of the items in the entire hash map: \n"; for(int x=0; x < hashMap.TableSize(); ++x) { if(!hashMap.IsEmpty(x)) { for(iterDec iter = hashMap.begin(x); iter != hashMap.end(x); ++iter) { cout<<" Key-> "<<(*iter).key<<"\tValue-> "<<iter->value<<endl; } cout<<endl; } } // display the total number of items in the hash map cout<<"The total number of items in the hash map is: "<< hashMap.TotalElems()<<endl; return 0; }// http://programmingnotes.org/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104 // DEMONSTRATE BASIC USE AND THE REMOVE / SORT FUNCTIONS#include <iostream>#include <string>#include "HashMap.h"using namespace std; // iterator declarationtypedef HashMap<string, int>::Iterator iterDec; int main(){    // declare variables    HashMap<string, int> hashMap;        // place items into the hash map using the 'insert' function    // NOTE: its OK for dupicate keys to be inserted into the hash map    hashMap.Insert("BIOL", 585);    hashMap.Insert("CPSC", 386);    hashMap.Insert("ART", 101);    hashMap.Insert("CPSC", 462);    hashMap.Insert("HIST", 251);    hashMap.Insert("CPSC", 301);    hashMap.Insert("MATH", 270);    hashMap.Insert("PE", 145);    hashMap.Insert("BIOL", 134);    hashMap.Insert("GEOL", 201);    hashMap.Insert("CIS", 465);    hashMap.Insert("CPSC", 240);    hashMap.Insert("GEOL", 101);    hashMap.Insert("MATH", 150);    hashMap.Insert("DANCE", 134);    hashMap.Insert("CPSC", 131);    hashMap.Insert("ART", 345);    hashMap.Insert("CHEM", 185);    hashMap.Insert("PE", 125);    hashMap.Insert("CPSC", 120);        // display the number of times the key "CPSC" appears in the hashmap    cout<<"The key 'CPSC' appears in the hash map "<<        hashMap.ContainsKey("CPSC")<<" time(s)\n";        // declare an iterator for the "CPSC" key so we can display data to screen    iterDec it = hashMap.begin(hashMap.Hash("CPSC"));        // display the first value    cout<<"\nThe first item with the key 'CPSC' is: "        <<it.value<<endl;        // display all the values in the hash map whose key matches "CPSC"    // NOTE: its possible for multiple different keys types    //   to be placed into the same hash map bucket        cout<<"\nThese are all the items in the hash map whose key is 'CPSC': \n";    for(int x=0; x < hashMap.BucketSize(hashMap.Hash("CPSC")); ++x)    {        if(it[x].key == "CPSC") // make sure this is the key we are looking for        {            cout<<"  Key-> "<<it[x].key<<"\tValue-> "<<it[x].value<<endl;        }    }        // remove the first value from the key "CPSC"    cout<<"\n[REMOVE THE VALUE '"<<it.value<<"' FROM THE KEY '"<<it.key<<"']\n";        hashMap.Remove("CPSC",it.value);        // display the number of times the key "CPSC" appears in the hashmap    cout<<"\nNow the key 'CPSC' only appears in the hash map "<<        hashMap.ContainsKey("CPSC")<<" time(s)\n";             // update the iterator to the current hash map state    it = hashMap.begin(hashMap.Hash("CPSC"));        // sort the values in the hash map bucket whose key is "CSPC"    hashMap.Sort(hashMap.Hash("CPSC"));        // display the values whose key matches "CPSC"    cout<<"\nThese are the sorted items in the hash map whose key is 'CPSC': \n";    for(int x=0; x < hashMap.BucketSize(hashMap.Hash("CPSC")); ++x)    {        if(it[x].key == "CPSC")        {            cout<<"  Key-> "<<it[x].key<<"\tValue-> "<<it[x].value<<endl;        }    }                    // display all the key/values in the entire hash map     cout<<"\nThese are all of the items in the entire hash map: \n";    for(int x=0; x < hashMap.TableSize(); ++x)    {        if(!hashMap.IsEmpty(x))        {            for(iterDec iter = hashMap.begin(x); iter != hashMap.end(x); ++iter)            {                cout<<"  Key-> "<<(*iter).key<<"\tValue-> "<<iter->value<<endl;            }            cout<<endl;        }            }        // display the total number of items in the hash map    cout<<"The total number of items in the hash map is: "<<        hashMap.TotalElems()<<endl;                   return 0;}// http://programmingnotes.org/ ```

SAMPLE OUTPUT:

`The key 'CPSC' appears in the hash map 6 time(s)`

``` The first item with the key 'CPSC' is: 386 These are all the items in the hash map whose key is 'CPSC': Key-> CPSC Value-> 386 Key-> CPSC Value-> 462 Key-> CPSC Value-> 301 Key-> CPSC Value-> 240 Key-> CPSC Value-> 131 Key-> CPSC Value-> 120 [REMOVE THE VALUE '386' FROM THE KEY 'CPSC'] Now the key 'CPSC' only appears in the hash map 5 time(s) These are the sorted items in the hash map whose key is 'CPSC': Key-> CPSC Value-> 120 Key-> CPSC Value-> 131 Key-> CPSC Value-> 240 Key-> CPSC Value-> 301 Key-> CPSC Value-> 462 These are all of the items in the entire hash map: Key-> CIS Value-> 465 Key-> DANCE Value-> 134 Key-> PE Value-> 145 Key-> PE Value-> 125 Key-> MATH Value-> 270 Key-> MATH Value-> 150 Key-> GEOL Value-> 201 Key-> GEOL Value-> 101 Key-> CPSC Value-> 120 Key-> CPSC Value-> 131 Key-> CPSC Value-> 240 Key-> CPSC Value-> 301 Key-> CPSC Value-> 462 Key-> BIOL Value-> 585 Key-> BIOL Value-> 134 Key-> ART Value-> 101 Key-> ART Value-> 345 Key-> CHEM Value-> 185 Key-> HIST Value-> 251 ```

```The total number of items in the hash map is: 19 ```

``` #2 - Display Items In A Struct C++ // DISPLAY ALL DATA INSIDE HASH MAP USING STD::STRING / INT / DOUBLE / STRUCT #include <iostream> #include <string> #include "HashMap.h" using namespace std; // sample struct demo struct MyStruct { string car; int year; double mpg; // struct comparison operators // used for 'remove' function bool operator == (const MyStruct& rhs)const { return car == rhs.car && year == rhs.year && mpg == rhs.mpg; } // used for 'sort' function bool operator > (const MyStruct& rhs)const { return car > rhs.car; } };// end of MyStruct // iterator declaration typedef HashMap<string, MyStruct>::Iterator iterDec; int main() { // declare variables MyStruct access; HashMap<string, MyStruct> hashMap(10); // --- initialize data for car #1 --- access.car = "Ford Fusion"; access.year = 2006; access.mpg = 28.5; hashMap.Insert("Kenneth",access); // --- initialize data for car #2 --- access.car = "BMW 535i"; access.year = 2014; access.mpg = 25.4; hashMap.Insert("Kenneth",access); // --- initialize data for car #3 --- access.car = "Nissan Altima"; access.year = 2011; access.mpg = 30.7; hashMap.Insert("Jessica",access); // --- initialize data for car #4 --- access.car = "Acura Integra"; access.year = 2001; access.mpg = 20.2; hashMap.Insert("Kenneth",access); // diplay how many cars "Kenneth" owns cout <<"'Kenneth' owns "<<hashMap.ContainsKey("Kenneth")<<" cars"<<endl; // display all items in the hash map // NOTE: its possible for multiple different keys types // to be placed into the same hash map bucket cout<<"\nThese are all of the cars in the hash map: \n"; for(int x=0; x < hashMap.TableSize(); ++x) { if(!hashMap.IsEmpty(x)) { // initialize an iterator iterDec iter = hashMap.begin(x); // display the key cout<<(*iter).key<<"'s car(s)\n"; // display all the values for(;iter != hashMap.end(x); ++iter) { cout<<"\tCar: "<<iter->value.car <<"\n\tYear: "<<iter->value.year <<"\n\tMPG: "<<iter->value.mpg<<endl<<endl; } } } // display the number of items in the hash map cout<<"The total number of cars in the hash map is: "<< hashMap.TotalElems()<<endl; // sort the cars that "Kenneth" owns by name cout<<"\nSorting the cars that 'Kenneth' owns by name.. \n"; hashMap.Sort(hashMap.Hash("Kenneth")); // display all items in the hash map again cout<<"\nAgain, these are all of the cars in the hash map: \n"; for(int x=0; x < hashMap.TableSize(); ++x) { if(!hashMap.IsEmpty(x)) { // initialize an iterator iterDec iter = hashMap.begin(x); // display the key cout<<iter->key<<"'s car(s)\n"; // display all the values for(;iter != hashMap.end(x); ++iter) { cout<<"\tCar: "<<(*iter).value.car <<"\n\tYear: "<<(*iter).value.year <<"\n\tMPG: "<<(*iter).value.mpg<<endl<<endl; } } } // remove the car 'Acura Integra' from "Kenneth's" inventory for(iterDec iter = hashMap.begin(hashMap.Hash("Kenneth")); iter != hashMap.end(hashMap.Hash("Kenneth")); ++iter) { if(iter->value.car == "Acura Integra") { cout<<"'"<<iter->value.car<<"' has been removed from 'Kenneth's' inventory..\n"; hashMap.Remove("Kenneth",(*iter).value); break; } } // display how many cars "Kenneth" owns cout <<"\n'Kenneth' now owns only "<<hashMap.ContainsKey("Kenneth")<<" cars"<<endl; // display all items in the hash map one more time cout<<"\nThese are all of the cars in the hash map with the 'Acura Integra' removed: \n"; for(int x=0; x < hashMap.TableSize(); ++x) { if(!hashMap.IsEmpty(x)) { // initialize an iterator iterDec iter = hashMap.begin(x); // display the key cout<<(*iter).key<<"'s car(s)\n"; // display all the values for(;iter != hashMap.end(x); ++iter) { cout<<"\tCar: "<<iter->value.car <<"\n\tYear: "<<iter->value.year <<"\n\tMPG: "<<iter->value.mpg<<endl<<endl; } } } // display the number of items in the hash map cout<<"The total number of cars in the hash map is: "<< hashMap.TotalElems()<<endl; return 0; }// http://programmingnotes.org/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159 // DISPLAY ALL DATA INSIDE HASH MAP USING STD::STRING / INT / DOUBLE / STRUCT#include <iostream>#include <string>#include "HashMap.h"using namespace std; // sample struct demostruct MyStruct{    string car;    int year;    double mpg;        // struct comparison operators    // used for 'remove' function    bool operator == (const MyStruct& rhs)const    {        return car == rhs.car &&            year == rhs.year &&            mpg == rhs.mpg;    }        // used for 'sort' function    bool operator > (const MyStruct& rhs)const    {        return car > rhs.car;    }    };// end of MyStruct // iterator declarationtypedef HashMap<string, MyStruct>::Iterator iterDec; int main(){    // declare variables    MyStruct access;     HashMap<string, MyStruct> hashMap(10);        // --- initialize data for car #1 ---    access.car = "Ford Fusion";    access.year = 2006;    access.mpg = 28.5;            hashMap.Insert("Kenneth",access);                    // --- initialize data for car #2 ---    access.car = "BMW 535i";    access.year = 2014;    access.mpg = 25.4;    hashMap.Insert("Kenneth",access);        // --- initialize data for car #3 ---    access.car = "Nissan Altima";    access.year = 2011;    access.mpg = 30.7;    hashMap.Insert("Jessica",access);             // --- initialize data for car #4 ---    access.car = "Acura Integra";    access.year = 2001;    access.mpg = 20.2;        hashMap.Insert("Kenneth",access);                   // diplay how many cars "Kenneth" owns    cout <<"'Kenneth' owns "<<hashMap.ContainsKey("Kenneth")<<" cars"<<endl;                     // display all items in the hash map    // NOTE: its possible for multiple different keys types    //   to be placed into the same hash map bucket         cout<<"\nThese are all of the cars in the hash map: \n";    for(int x=0; x < hashMap.TableSize(); ++x)    {        if(!hashMap.IsEmpty(x))        {            // initialize an iterator            iterDec iter = hashMap.begin(x);                        // display the key            cout<<(*iter).key<<"'s car(s)\n";            // display all the values             for(;iter != hashMap.end(x); ++iter)            {                cout<<"\tCar: "<<iter->value.car                    <<"\n\tYear: "<<iter->value.year                    <<"\n\tMPG: "<<iter->value.mpg<<endl<<endl;                                            }        }            }                       // display the number of items in the hash map    cout<<"The total number of cars in the hash map is: "<<        hashMap.TotalElems()<<endl;           // sort the cars that "Kenneth" owns by name    cout<<"\nSorting the cars that 'Kenneth' owns by name.. \n";             hashMap.Sort(hashMap.Hash("Kenneth"));            // display all items in the hash map again      cout<<"\nAgain, these are all of the cars in the hash map: \n";    for(int x=0; x < hashMap.TableSize(); ++x)    {        if(!hashMap.IsEmpty(x))        {            // initialize an iterator            iterDec iter = hashMap.begin(x);                        // display the key            cout<<iter->key<<"'s car(s)\n";            // display all the values             for(;iter != hashMap.end(x); ++iter)            {                cout<<"\tCar: "<<(*iter).value.car                    <<"\n\tYear: "<<(*iter).value.year                    <<"\n\tMPG: "<<(*iter).value.mpg<<endl<<endl;                            }        }            }      // remove the car 'Acura Integra' from "Kenneth's" inventory    for(iterDec iter = hashMap.begin(hashMap.Hash("Kenneth"));         iter != hashMap.end(hashMap.Hash("Kenneth")); ++iter)    {         if(iter->value.car == "Acura Integra")        {            cout<<"'"<<iter->value.car<<"' has been removed from 'Kenneth's' inventory..\n";            hashMap.Remove("Kenneth",(*iter).value);            break;        }    }            // display how many cars "Kenneth" owns    cout <<"\n'Kenneth' now owns only "<<hashMap.ContainsKey("Kenneth")<<" cars"<<endl;                         // display all items in the hash map one more time      cout<<"\nThese are all of the cars in the hash map with the 'Acura Integra' removed: \n";    for(int x=0; x < hashMap.TableSize(); ++x)    {        if(!hashMap.IsEmpty(x))        {            // initialize an iterator            iterDec iter = hashMap.begin(x);                        // display the key            cout<<(*iter).key<<"'s car(s)\n";            // display all the values             for(;iter != hashMap.end(x); ++iter)            {                cout<<"\tCar: "<<iter->value.car                    <<"\n\tYear: "<<iter->value.year                    <<"\n\tMPG: "<<iter->value.mpg<<endl<<endl;            }        }            }             // display the number of items in the hash map    cout<<"The total number of cars in the hash map is: "<<        hashMap.TotalElems()<<endl;                       return 0;}// http://programmingnotes.org/ ```

SAMPLE OUTPUT:

`'Kenneth' owns 3 cars`

``` These are all of the cars in the hash map: Jessica's car(s) Car: Nissan Altima Year: 2011 MPG: 30.7 Kenneth's car(s) Car: Ford Fusion Year: 2006 MPG: 28.5 Car: BMW 535i Year: 2014 MPG: 25.4 Car: Acura Integra Year: 2001 MPG: 20.2 ----------------------------------------------------- The total number of cars in the hash map is: 4 Sorting the cars that 'Kenneth' owns by name.. Again, these are all of the cars in the hash map: Jessica's car(s) Car: Nissan Altima Year: 2011 MPG: 30.7 Kenneth's car(s) Car: Acura Integra Year: 2001 MPG: 20.2 Car: BMW 535i Year: 2014 MPG: 25.4 Car: Ford Fusion Year: 2006 MPG: 28.5 ----------------------------------------------------- 'Acura Integra' has been removed from 'Kenneth's' inventory.. 'Kenneth' now owns only 2 cars These are all of the cars in the hash map with the 'Acura Integra' removed: Jessica's car(s) Car: Nissan Altima Year: 2011 MPG: 30.7 Kenneth's car(s) Car: BMW 535i Year: 2014 MPG: 25.4 Car: Ford Fusion Year: 2006 MPG: 28.5 ----------------------------------------------------- ```

```The total number of cars in the hash map is: 3 ```

## C++ || Simple Spell Checker Using A Hash Table The following is another programming assignment which was presented in a C++ Data Structures course. This assignment was used to gain more experience using hash tables.

REQUIRED KNOWLEDGE FOR THIS PROGRAM

```Hash Table - What Is It? How To Create A Spell Checker How To Read Data From A File Strtok - Split Strings Into Tokens #include 'HashTable.h' The Dictionary File - Download Here ```

== OVERVIEW ==

This program first reads words from a dictionary file, and inserts them into a hash table.

The dictionary file consists of a list of 62,454 correctly spelled lowercase words, separated by whitespace. The words are inserted into the hash table, with each bucket growing dynamically as necessary to hold all of the incoming data.

After the reading of the dictionary file is complete, the program prompts the user for input. After input is obtained, each word that the user enteres into the program is looked up within the hash table to see if it exists. If the user entered word exists within the hash table, then that word is spelled correctly. If not, a list of possible suggested spelling corrections is displayed to the screen.

== HASH TABLE STATISTICS ==

To better understand how hash tables work, this program reports the following statistics to the screen:

```• The total size of the hash table. • The size of the largest hash table bucket. • The size of the smallest hash table bucket. • The total number of buckets used. • The average hash table bucket size.```

A timer is used in this program to time (in seconds) how long it takes to read in the dictionary file. The program also saves each hash table bucket into a separate output .txt file. This is used to further visualize how the hash table data is internally being stored within memory.

== SPELL CHECKING ==

The easiest way to generate corrections for a spell checker is via a trial and error method. If we assume that the misspelled word contains only a single error, we can try all possible corrections and look each up in the dictionary.

Example:

``` wird: bird gird ward word wild wind wire wiry```

Traditionally, spell checkers look for four possible errors: a wrong letter (“wird”), also knows as alteration. An inserted letter (“woprd”), a deleted letter (“wrd”), or a pair of adjacent transposed letters (“wrod”).

The easiest of which is checking for a wrong letter. For example, if a word isnt found in the dictionary, all variants of that word can be looked up by changing one letter. Given the user input “wird,” a one letter variant can be “aird”, “bird”, “cird”, etc. through “zird.” Then “ward”, “wbrd”, “wcrd” through “wzrd”, can be checked, and so forth. Whenever a match is found within the dictionary, the spelling correction should be displayed to the screen.

For a detailed analysis how the other methods can be constructed, click here.

===== SIMPLE SPELL CHECKER =====

This program uses a custom template.h class. To obtain the code for that class, click here.

``` Simple Spell Checker Using A Hash Table C++ // ============================================================================ // Author: Kenneth Perkins // Date: Jan 31, 2013 // Taken From: http://programmingnotes.org/ // File: SpellCheck.cpp // Description: This is a simple spell checker which tests the HashTable.h // class. // ============================================================================ #include <iostream> #include <fstream> #include <cctype> #include <cstring> #include <string> #include <iomanip> #include <ctime> #include <limits> #include "HashTable.h" using namespace std; // iterator declaration for hash table typedef HashTable<string>::Iterator iterDec; // hash table size const int TABLE_SIZE = 19000; // strtok delimiters const char* DELIMITERS = " ,.-\':;?()+*/\\%\$#!\"@\^&"; // function prototypes void PrintTableStats(HashTable<string>& hashTable); int SpellCheck(HashTable<string>& hashTable, string word); string ToLowerCase(string word); int main() { // declare variables int result = 0; string userInput; string currWord; clock_t beg; // used to time the hashtable load clock_t end; // used to time the hashtable load char response; ifstream infile; HashTable<string> hashTable(TABLE_SIZE); // open the dictionary file infile.open("INPUT_Dictionary_programmingnotes_freeweq_com.txt"); // check if the file exists, EXIT if it doesnt if(infile.fail()) { cout<<"\n\n**ERROR - The dictionary file could not be found...\n"; exit(1); } cerr<<"\nLoading dictionary...."; beg = clock(); // start the timer // get data from file and put into hashtable while(infile >> currWord) { // makes sure duplicate words arent inserted into table if(!hashTable.Count(currWord)) { hashTable.Insert(currWord); } } infile.close(); PrintTableStats(hashTable); end = clock()-beg; // end the timer cout<<"\n\nDictionary loaded in "<< (double)end / ((double)CLOCKS_PER_SEC)<<" secs!"; // creates a line separator cout<<endl; cout.fill('-'); cout<<left<<setw(50)<<""<<endl; do{ // get user input cout<<"\n>> Please enter a sentence: "; getline(cin,userInput); cout<<endl; // split each word from the string into individual words to check if // they are spelled correctly char* splitInput = strtok(const_cast<char*>(userInput.c_str()),DELIMITERS); while(splitInput!=NULL) { currWord = splitInput; currWord = ToLowerCase(currWord); result += SpellCheck(hashTable,currWord); splitInput = strtok(NULL,DELIMITERS); } // display results if(result > 0) { cout<<"Number of words spelled incorrectly: "<<result<<endl; result = 0; } // ask for more data cout<<"\nDo you want to enter another sentence? (y/n): "; cin >> response; cin.ignore(numeric_limits<streamsize>::max(),'\n'); // clear the cin buffer }while(toupper(response)=='Y'); cout<<"\nBYE!!\n"; return 0; }// end of main void PrintTableStats(HashTable<string>& hashTable) { int largestBucket = -9999999; int largestIndex = 0; int smallestBucket = 9999999; int smallestIndex = 0; double numBuckestUsed = 0; ofstream outfile("OUTPUT_HashTable_Stats_programmingnotes_freeweq_com.txt"); for(int x=0; x < hashTable.TableSize(); ++x) { // iterator is used to traverse each hashtable bucket iterDec it = hashTable.begin(x); if(!hashTable.IsEmpty(x)) { if(smallestBucket > hashTable.BucketSize(x)) { smallestBucket = hashTable.BucketSize(x); smallestIndex = x; } if(largestBucket < hashTable.BucketSize(x)) { largestBucket = hashTable.BucketSize(x); largestIndex = x; } ++numBuckestUsed; outfile<<"\nBucket #"<<x<<":\n"; for(int y = 0; y < hashTable.BucketSize(x); ++y) { outfile <<"\t"<< it[y] << endl; } } } cout<<"Complete!\n"; // creates a line separator cout<<endl; cout.fill('-'); cout<<left<<setw(50)<<""<<endl; cout<<"Total dictionary words = "<<hashTable.TotalElems()<<endl <<"Hash table size = "<<hashTable.TableSize()<<endl <<"Largest bucket size = "<<largestBucket<< " items at index #"<<largestIndex<<endl <<"Smallest bucket size = "<<smallestBucket<< " items at index #"<<smallestIndex<<endl <<"Total buckets used = "<<numBuckestUsed<<endl <<"Total percent of hash table used = "<<(numBuckestUsed/hashTable.TableSize())*100<<"%"<<endl <<"Average bucket size = "<<(hashTable.TotalElems()/numBuckestUsed)<<" items"; }// end of PrintTableStats int SpellCheck(HashTable<string>& hashTable, string word) { int result = 0; int suggestion = 0; string remove; int numRemove=0; if(!hashTable.Count(word)) { ++result; cout<<"** "<<word<<": "; // alteration & insertion for(unsigned x = 0; x < word.length(); ++x) { string alteration = word; for(char c = 'a'; c <= 'z'; ++c) { //alteration alteration[x] = c; if(hashTable.Count(alteration)) { cout<<alteration<<", "; remove[numRemove++] = alteration; ++suggestion; // remove the entry so it isnt displayed multiple times hashTable.Remove(alteration); } //insertion string insertion = word.substr(0, x) + c + word.substr(x); if(hashTable.Count(insertion)) { cout<<insertion<<", "; remove[numRemove++] = insertion; ++suggestion; // remove the entry so it isnt displayed multiple times hashTable.Remove(insertion); } } } // transposition & deletion for(unsigned x = 0; x < word.length()-1;++x) { // transposition string transposition = word.substr(0,x) + word[x+1] + word[x] + word.substr(x+2); if(hashTable.Count(transposition)) { cout<<transposition<<", "; remove[numRemove++] = transposition; ++suggestion; // remove the entry so it isnt displayed multiple times hashTable.Remove(transposition); } // deletion string deletion = word.substr(0, x)+ word.substr(x + 1); if(hashTable.Count(deletion)) { cout<<deletion<<", "; remove[numRemove++] = deletion; ++suggestion; // remove the entry so it isnt displayed multiple times hashTable.Remove(deletion); } } // place the removed items back inside the hash table while(numRemove>=0) { hashTable.Insert(remove[numRemove--]); } if(suggestion < 1) { cout<<"No spelling suggestion found..."; } cout<<endl<<endl; } return result; }// end of SpellCheck string ToLowerCase(string word) { for(unsigned x = 0; x < word.length(); ++x) { word[x] = tolower(word[x]); } return word; }// http://programmingnotes.org/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248 // ============================================================================//    Author: Kenneth Perkins//    Date:   Jan 31, 2013//    Taken From: http://programmingnotes.org///    File:  SpellCheck.cpp//    Description: This is a simple spell checker which tests the HashTable.h//          class. // ============================================================================#include <iostream>#include <fstream>#include <cctype>#include <cstring>#include <string>#include <iomanip>#include <ctime>#include <limits>#include "HashTable.h"using namespace std; // iterator declaration for hash tabletypedef HashTable<string>::Iterator iterDec; // hash table sizeconst int TABLE_SIZE = 19000; // strtok delimitersconst char* DELIMITERS = " ,.-\':;?()+*/\\%\$#!\"@\^&"; // function prototypesvoid PrintTableStats(HashTable<string>& hashTable);int SpellCheck(HashTable<string>& hashTable, string word);string ToLowerCase(string word); int main(){ // declare variables int result = 0; string userInput; string currWord; clock_t beg; // used to time the hashtable load clock_t end; // used to time the hashtable load char response; ifstream infile; HashTable<string> hashTable(TABLE_SIZE);  // open the dictionary file infile.open("INPUT_Dictionary_programmingnotes_freeweq_com.txt");  // check if the file exists, EXIT if it doesnt if(infile.fail()) { cout<<"\n\n**ERROR - The dictionary file could not be found...\n"; exit(1); }  cerr<<"\nLoading dictionary...."; beg = clock(); // start the timer  // get data from file and put into hashtable while(infile >> currWord) { // makes sure duplicate words arent inserted into table if(!hashTable.Count(currWord)) { hashTable.Insert(currWord); } } infile.close(); PrintTableStats(hashTable);   end = clock()-beg; // end the timer cout<<"\n\nDictionary loaded in "<< (double)end / ((double)CLOCKS_PER_SEC)<<" secs!"; // creates a line separator cout<<endl; cout.fill('-'); cout<<left<<setw(50)<<""<<endl;   do{ // get user input cout<<"\n>> Please enter a sentence: "; getline(cin,userInput); cout<<endl;  // split each word from the string into individual words to check if // they are spelled correctly char* splitInput = strtok(const_cast<char*>(userInput.c_str()),DELIMITERS); while(splitInput!=NULL) { currWord = splitInput; currWord = ToLowerCase(currWord); result += SpellCheck(hashTable,currWord); splitInput = strtok(NULL,DELIMITERS); }  // display results if(result > 0) { cout<<"Number of words spelled incorrectly: "<<result<<endl; result = 0; }  // ask for more data cout<<"\nDo you want to enter another sentence? (y/n): "; cin >> response; cin.ignore(numeric_limits<streamsize>::max(),'\n'); // clear the cin buffer }while(toupper(response)=='Y');  cout<<"\nBYE!!\n";  return 0;}// end of main void PrintTableStats(HashTable<string>& hashTable){ int largestBucket = -9999999; int largestIndex = 0; int smallestBucket = 9999999; int smallestIndex = 0; double numBuckestUsed = 0; ofstream outfile("OUTPUT_HashTable_Stats_programmingnotes_freeweq_com.txt"); for(int x=0; x < hashTable.TableSize(); ++x) { // iterator is used to traverse each hashtable bucket iterDec it = hashTable.begin(x); if(!hashTable.IsEmpty(x)) { if(smallestBucket > hashTable.BucketSize(x)) { smallestBucket = hashTable.BucketSize(x); smallestIndex = x; } if(largestBucket < hashTable.BucketSize(x)) { largestBucket = hashTable.BucketSize(x); largestIndex = x; } ++numBuckestUsed; outfile<<"\nBucket #"<<x<<":\n"; for(int y = 0; y < hashTable.BucketSize(x); ++y) { outfile <<"\t"<< it[y] << endl; } } } cout<<"Complete!\n";  // creates a line separator cout<<endl; cout.fill('-'); cout<<left<<setw(50)<<""<<endl;  cout<<"Total dictionary words = "<<hashTable.TotalElems()<<endl <<"Hash table size = "<<hashTable.TableSize()<<endl <<"Largest bucket size = "<<largestBucket<< " items at index #"<<largestIndex<<endl <<"Smallest bucket size = "<<smallestBucket<< " items at index #"<<smallestIndex<<endl <<"Total buckets used = "<<numBuckestUsed<<endl <<"Total percent of hash table used = "<<(numBuckestUsed/hashTable.TableSize())*100<<"%"<<endl <<"Average bucket size = "<<(hashTable.TotalElems()/numBuckestUsed)<<" items";}// end of PrintTableStats int SpellCheck(HashTable<string>& hashTable, string word){ int result = 0; int suggestion = 0; string remove; int numRemove=0;  if(!hashTable.Count(word)) { ++result; cout<<"** "<<word<<": "; // alteration & insertion for(unsigned x = 0; x < word.length(); ++x) { string alteration = word; for(char c = 'a'; c <= 'z'; ++c) { //alteration alteration[x] = c; if(hashTable.Count(alteration)) { cout<<alteration<<", "; remove[numRemove++] = alteration; ++suggestion; // remove the entry so it isnt displayed multiple times hashTable.Remove(alteration); } //insertion string insertion = word.substr(0, x) + c + word.substr(x); if(hashTable.Count(insertion)) { cout<<insertion<<", "; remove[numRemove++] = insertion; ++suggestion; // remove the entry so it isnt displayed multiple times hashTable.Remove(insertion); } } } // transposition & deletion for(unsigned x = 0; x < word.length()-1;++x) { // transposition string transposition = word.substr(0,x) + word[x+1] + word[x] + word.substr(x+2); if(hashTable.Count(transposition)) { cout<<transposition<<", "; remove[numRemove++] = transposition; ++suggestion; // remove the entry so it isnt displayed multiple times hashTable.Remove(transposition);  } // deletion string deletion = word.substr(0, x)+ word.substr(x + 1); if(hashTable.Count(deletion)) { cout<<deletion<<", "; remove[numRemove++] = deletion; ++suggestion; // remove the entry so it isnt displayed multiple times hashTable.Remove(deletion); } } // place the removed items back inside the hash table while(numRemove>=0) { hashTable.Insert(remove[numRemove--]); } if(suggestion < 1) { cout<<"No spelling suggestion found..."; } cout<<endl<<endl; } return result;}// end of SpellCheck string ToLowerCase(string word){ for(unsigned x = 0; x < word.length(); ++x) { word[x] = tolower(word[x]); } return word;}// 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.

Remember to include the data file.

Once compiled, you should get this as your output

`Loading dictionary....Complete!`

``` -------------------------------------------------- Total dictionary words = 61286 Hash table size = 19000 Largest bucket size = 13 items at index #1551 Smallest bucket size = 1 items at index #11 Total buckets used = 18217 Total percent of hash table used = 95.8789% Average bucket size = 3.36422 items Dictionary loaded in 1.861 secs! -------------------------------------------------- >> Please enter a sentence: wird ** wird: bird, gird, ward, weird, word, wild, wind, wire, wired, wiry, Number of words spelled incorrectly: 1 Do you want to enter another sentence? (y/n): y -------------------------------------------------- >> Please enter a sentence: woprd ** woprd: word, Number of words spelled incorrectly: 1 Do you want to enter another sentence? (y/n): y -------------------------------------------------- >> Please enter a sentence: wrd ** wrd: ard, ord, ward, wed, word, Number of words spelled incorrectly: 1 Do you want to enter another sentence? (y/n): y -------------------------------------------------- >> Please enter a sentence: wrod ** wrod: brod, trod, wood, rod, word, Number of words spelled incorrectly: 1 Do you want to enter another sentence? (y/n): y -------------------------------------------------- >> Please enter a sentence: New! Safe and efective ** efective: defective, effective, elective, Number of words spelled incorrectly: 1 Do you want to enter another sentence? (y/n): y -------------------------------------------------- >> Please enter a sentence: This is a sentance with no corections gygyuigigigiug ** sentance: sentence, ** corections: corrections, ** gygyuigigigiug: No spelling suggestion found... Number of words spelled incorrectly: 3 Do you want to enter another sentence? (y/n): n ```

```BYE!! ```

## C++ || Custom Template Hash Table With Iterator Using Separate Chaining Before we get into the code, what is a Hash Table? Simply put, a Hash Table is a data structure used to implement an associative array; one that can map unique “keys” to specific values. While a standard array requires that indice subscripts be integers, a hash table can use a floating point value, a string, another array, or even a structure 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 table 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, compare a standard array full of data (100 elements). If the position was known for the specific item that we wanted to access within the array, we could quickly access it. For example, if we wanted to access the data located at index #5 in the array, we could access it by doing:

``` array; // do something with the data ```

Here, we dont have to search through each element in the array to find what we need, we just access it at index #5. The question is, how do we know that index #5 stores the data that we are looking for? If we have a large set of data, doing a sequential search over each item within the array can be very inefficient. That is where hashing comes in handy. Given a “key,” we can apply a hash function to a unique index or bucket to find the data that we wish to access.

So in essence, a hash table is a data structure that stores key/value pairs, and is 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 items 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 values within one bucket – should any collisions occur.

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

=== CUSTOM TEMPLATE HASH TABLE WITH ITERATOR ===

``` #include 'HashTable.h' - Hash Table With Iterator C++ // ============================================================================ // Author: Kenneth Perkins // Date: Jan 18, 2013 // Taken From: http://programmingnotes.org/ // File: HashTable.h // Description: This is a class which implements various functions which // demonstrates the use of a Hash Table. // ============================================================================ #ifndef TEMPLATE_HASH_TABLE #define TEMPLATE_HASH_TABLE #include <iostream> #include <string> #include <sstream> #include <cstdlib> // if user doesnt define, this is the // default hash table size const int HASH_SIZE = 100; template <class ItemType> class HashTable { public: HashTable(int hashSze = HASH_SIZE); /* Function: Constructor initializes hash table Precondition: None Postcondition: Defines private variables */ bool IsEmpty(int key); /* Function: Determines whether hash table is empty at the given key Precondition: Hash table has been created Postcondition: The function = true if the hash table is empty and the function = false if hash table is not empty */ bool IsFull(); /* Function: Determines whether hash table is full Precondition: Hash table has been created Postcondition: The function = true if the hash table is full and the function = false if hash table is not full */ int Hash(ItemType newItem); /* Function: Computes and returns a unique hash key for a given item The returned key is the given cell where the item resides Precondition: Hash table has been created and is not full Postcondition: The hash key is returned */ void Insert(ItemType newItem); /* Function: Adds newItem to the back of the list at a given key in the hash table A unique hash key is automatically generated for each newItem Precondition: Hash table has been created and is not full Postcondition: Item is in the hash table */ void Append(int key, ItemType newItem); /* Function: Adds new item to the end of the list at a given key in the hash table Precondition: Hash table has been created and is not full Postcondition: Item is in the hash table */ bool Remove(ItemType deleteItem, int key = -1); /* Function: Removes the first instance from the table whose value is "deleteItem" Optional second parameter indicates the key where deleteItem is located Precondition: Hash table 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 key); /* Function: Sort the items in the table at the given key Precondition: Hash table has been initialized Postcondition: The hash table is sorted */ int TableSize(); /* Function: Return the size of the hash table Precondition: Hash table has been initialized Postcondition: The size of the hash table is returned */ int TotalElems(); /* Function: Return the total number of elements contained in the hash table Precondition: Hash table has been initialized Postcondition: The size of the hash table is returned */ int BucketSize(int key); /* Function: Return the number of items contained in the hash table cell at the given key Precondition: Hash table has been initialized Postcondition: The size of the given key cell is returned */ int Count(ItemType searchItem); /* Function: Return the number of times searchItem appears in the table. Only works on items located in their correctly hashed cells Precondition: Hash table has been initialized Postcondition: The number of times searchItem appears in the table is returned */ void MakeEmpty(); /* Function: Initializes hash table to an empty state Precondition: Hash table has been created Postcondition: Hash table no longer exists */ ~HashTable(); /* Function: Removes the hash table Precondition: Hash table has been declared Postcondition: Hash table no longer exists */ // -- ITERATOR CLASS -- class Iterator; /* Function: Class declaration to the iterator Precondition: Hash table has been declared Postcondition: Hash Iterator has been declared */ Iterator begin(int key){return(!IsEmpty(key)) ? head[key]:NULL;} /* Function: Returns the beginning of the current hash cell list Precondition: Hash table has been declared Postcondition: Hash cell has been returned to the Iterator */ Iterator end(int key=0){return NULL;} /* Function: Returns the end of the current hash cell list Precondition: Hash table has been declared Postcondition: Hash cell has been returned to the Iterator */ private: struct node { ItemType currentItem; node* next; }; node** head; // array of linked list declaration - front of each hash table cell int hashSize; // the size of the hash table (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 table cell }; //========================= Implementation ================================// template<class ItemType> HashTable<ItemType>::HashTable(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 HashTable */ template<class ItemType> bool HashTable<ItemType>::IsEmpty(int key) { if(key >=0 && key < hashSize) { return head[key] == NULL; } return true; }/* End of IsEmpty */ template<class ItemType> bool HashTable<ItemType>::IsFull() { try { node* location = new node; delete location; return false; } catch(std::bad_alloc&) { return true; } }/* End of IsFull */ template<class ItemType> int HashTable<ItemType>::Hash(ItemType newItem) { 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 << newItem; 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 ItemType> void HashTable<ItemType>::Insert(ItemType newItem) { if(IsFull()) { //std::cout<<"nINSERT ERROR - HASH TABLE FULLn"; } else { int key = Hash(newItem); Append(key,newItem); } }/* End of Insert */ template<class ItemType> void HashTable<ItemType>::Append(int key, ItemType newItem) { if(IsFull()) { //std::cout<<"nAPPEND ERROR - HASH TABLE FULLn"; } else { node* newNode = new node; // adds new node newNode-> currentItem = newItem; newNode-> next = NULL; if(IsEmpty(key)) { head[key] = newNode; } else { node* tempPtr = head[key]; while(tempPtr-> next != NULL) { tempPtr = tempPtr-> next; } tempPtr-> next = newNode; } ++bucketSize[key]; ++totElems; } }/* End of Append */ template<class ItemType> bool HashTable<ItemType>::Remove(ItemType deleteItem, int key) { bool isFound = false; node* tempPtr; if(key == -1) { key = Hash(deleteItem); } if(IsEmpty(key)) { //std::cout<<"nREMOVE ERROR - HASH TABLE EMPTYn"; } else if(head[key]->currentItem == deleteItem) { tempPtr = head[key]; head[key] = head[key]-> next; delete tempPtr; --totElems; --bucketSize[key]; isFound = true; } else { for(tempPtr = head[key];tempPtr->next!=NULL;tempPtr=tempPtr->next) { if(tempPtr->next->currentItem == deleteItem) { node* deleteNode = tempPtr->next; tempPtr-> next = tempPtr-> next-> next; delete deleteNode; isFound = true; --totElems; --bucketSize[key]; break; } } } return isFound; }/* End of Remove */ template<class ItemType> void HashTable<ItemType>::Sort(int key) { if(IsEmpty(key)) { //std::cout<<"nSORT ERROR - HASH TABLE EMPTYn"; } else { int listSize = BucketSize(key); bool sorted = false; do{ sorted = true; int x = 0; for(node* tempPtr = head[key]; tempPtr->next!=NULL && x < listSize-1; tempPtr=tempPtr->next,++x) { if(tempPtr-> currentItem > tempPtr->next->currentItem) { ItemType temp = tempPtr-> currentItem; tempPtr-> currentItem = tempPtr->next->currentItem; tempPtr->next->currentItem = temp; sorted = false; } } --listSize; }while(!sorted); } }/* End of Sort */ template<class ItemType> int HashTable<ItemType>::TableSize() { return hashSize; }/* End of TableSize */ template<class ItemType> int HashTable<ItemType>::TotalElems() { return totElems; }/* End of TotalElems */ template<class ItemType> int HashTable<ItemType>::BucketSize(int key) { return(!IsEmpty(key)) ? bucketSize[key]:0; }/* End of BucketSize */ template<class ItemType> int HashTable<ItemType>::Count(ItemType searchItem) { int key = Hash(searchItem); int search = 0; if(IsEmpty(key)) { //std::cout<<"nCOUNT ERROR - HASH TABLE EMPTYn"; } else { for(node* tempPtr = head[key];tempPtr!=NULL;tempPtr=tempPtr->next) { if(tempPtr->currentItem == searchItem) { ++search; } } } return search; }/* End of Count */ template<class ItemType> void HashTable<ItemType>::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 <<std::endl; head[x] = head[x]-> next; delete temp; } } bucketSize[x] = 0; } }/* End of MakeEmpty */ template<class ItemType> HashTable<ItemType>::~HashTable() { MakeEmpty(); delete[] head; delete[] bucketSize; }/* End of ~HashTable */ // END OF THE HASH TABLE CLASS // ----------------------------------------------------------- // START OF THE HASH TABLE ITERATOR CLASS template <class ItemType> class HashTable<ItemType>::Iterator : public std::iterator<std::forward_iterator_tag,ItemType>, public HashTable<ItemType> { 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 // HashTable. 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; } ItemType& 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. ItemType& operator*() { // Return "junk" data // to prevent the program from crashing if(itHead == NULL) { return junk; } return itHead->currentItem; } ItemType* operator->() { return(&**this); } private: node* itHead; ItemType junk; }; #endif // http://programmingnotes.org/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476 // ============================================================================//    Author: Kenneth Perkins//    Date:   Jan 18, 2013//    Taken From: http://programmingnotes.org///    File:  HashTable.h//    Description: This is a class which implements various functions which//          demonstrates the use of a Hash Table.// ============================================================================#ifndef TEMPLATE_HASH_TABLE#define TEMPLATE_HASH_TABLE#include <iostream>#include <string>#include <sstream>#include <cstdlib> // if user doesnt define, this is the// default hash table sizeconst int HASH_SIZE = 100; template <class ItemType>class HashTable{public:    HashTable(int hashSze = HASH_SIZE);        /*   Function: Constructor initializes hash table            Precondition: None            Postcondition: Defines private variables */    bool IsEmpty(int key);        /*   Function: Determines whether hash table is empty at the given key            Precondition: Hash table has been created            Postcondition: The function = true if the hash table is empty and the                             function = false if hash table is not empty */    bool  IsFull();        /*   Function: Determines whether hash table is full            Precondition: Hash table has been created            Postcondition: The function = true if the hash table is full and the                             function = false if hash table is not full */    int Hash(ItemType newItem);        /*   Function: Computes and returns a unique hash key for a given item                        The returned key is the given cell where the item resides            Precondition:  Hash table has been created and is not full            Postcondition: The hash key is returned */    void Insert(ItemType newItem);        /*   Function: Adds newItem to the back of the list at a given key in the hash table                         A unique hash key is automatically generated for each newItem            Precondition:  Hash table has been created and is not full            Postcondition: Item is in the hash table */    void Append(int key, ItemType newItem);        /*   Function: Adds new item to the end of the list at a given                         key in the hash table            Precondition:  Hash table has been created and is not full            Postcondition: Item is in the hash table */    bool Remove(ItemType deleteItem, int key = -1);        /*   Function: Removes the first instance from the table whose value is "deleteItem"                      Optional second parameter indicates the key where deleteItem is located            Precondition:  Hash table 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 key);        /*   Function: Sort the items in the table at the given key            Precondition: Hash table has been initialized            Postcondition: The hash table is sorted */    int TableSize();        /*   Function: Return the size of the hash table            Precondition: Hash table has been initialized            Postcondition: The size of the hash table is returned */    int TotalElems();        /*   Function: Return the total number of elements contained in the hash table            Precondition: Hash table has been initialized            Postcondition: The size of the hash table is returned */    int BucketSize(int key);        /*   Function: Return the number of items contained in the hash table                        cell at the given key            Precondition: Hash table has been initialized            Postcondition: The size of the given key cell is returned */    int Count(ItemType searchItem);        /*   Function: Return the number of times searchItem appears in the table.                        Only works on items located in their correctly hashed cells            Precondition: Hash table has been initialized            Postcondition: The number of times searchItem appears in the table is returned */    void MakeEmpty();        /*   Function: Initializes hash table to an empty state            Precondition: Hash table has been created            Postcondition: Hash table no longer exists */    ~HashTable();        /*   Function: Removes the hash table            Precondition: Hash table has been declared            Postcondition: Hash table no longer exists */     //  -- ITERATOR CLASS --    class Iterator;        /*   Function: Class declaration to the iterator            Precondition: Hash table has been declared            Postcondition: Hash Iterator has been declared */     Iterator begin(int key){return(!IsEmpty(key)) ? head[key]:NULL;}        /*   Function: Returns the beginning of the current hash cell list            Precondition: Hash table has been declared            Postcondition: Hash cell has been returned to the Iterator */     Iterator end(int key=0){return NULL;}        /*   Function: Returns the end of the current hash cell list            Precondition: Hash table has been declared            Postcondition: Hash cell has been returned to the Iterator */ private:    struct node    {        ItemType currentItem;        node* next;    };    node** head; // array of linked list declaration - front of each hash table cell    int hashSize; // the size of the hash table (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 table cell}; //=========================  Implementation  ================================// template<class ItemType>HashTable<ItemType>::HashTable(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 HashTable */ template<class ItemType>bool HashTable<ItemType>::IsEmpty(int key){    if(key >=0 && key < hashSize)    {        return head[key] == NULL;    }    return true;}/* End of IsEmpty */ template<class ItemType>bool HashTable<ItemType>::IsFull(){    try    {        node* location = new node;        delete location;        return false;    }    catch(std::bad_alloc&)    {        return true;    }}/* End of IsFull */ template<class ItemType>int HashTable<ItemType>::Hash(ItemType newItem){    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 << newItem;    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 ItemType>void HashTable<ItemType>::Insert(ItemType newItem){    if(IsFull())    {        //std::cout<<"nINSERT ERROR - HASH TABLE FULLn";    }    else    {        int key = Hash(newItem);        Append(key,newItem);    }}/* End of Insert */ template<class ItemType>void HashTable<ItemType>::Append(int key, ItemType newItem){    if(IsFull())    {        //std::cout<<"nAPPEND ERROR - HASH TABLE FULLn";    }    else    {        node* newNode = new node;  // adds new node        newNode-> currentItem = newItem;        newNode-> next = NULL;         if(IsEmpty(key))        {            head[key] = newNode;        }        else        {            node* tempPtr = head[key];            while(tempPtr-> next != NULL)            {                tempPtr = tempPtr-> next;            }            tempPtr-> next = newNode;        }        ++bucketSize[key];        ++totElems;    }}/* End of Append */ template<class ItemType>bool HashTable<ItemType>::Remove(ItemType deleteItem, int key){    bool isFound = false;    node* tempPtr;    if(key == -1)    {        key = Hash(deleteItem);    }     if(IsEmpty(key))    {        //std::cout<<"nREMOVE ERROR - HASH TABLE EMPTYn";    }    else if(head[key]->currentItem == deleteItem)    {        tempPtr = head[key];        head[key] = head[key]-> next;        delete tempPtr;        --totElems;        --bucketSize[key];        isFound = true;    }    else    {        for(tempPtr = head[key];tempPtr->next!=NULL;tempPtr=tempPtr->next)        {            if(tempPtr->next->currentItem == deleteItem)            {                node* deleteNode = tempPtr->next;                tempPtr-> next = tempPtr-> next-> next;                delete deleteNode;                isFound = true;                --totElems;                --bucketSize[key];                break;            }        }    }    return isFound;}/* End of Remove */ template<class ItemType>void HashTable<ItemType>::Sort(int key){    if(IsEmpty(key))    {        //std::cout<<"nSORT ERROR - HASH TABLE EMPTYn";    }    else    {        int listSize = BucketSize(key);        bool sorted = false;         do{            sorted = true;            int x = 0;            for(node* tempPtr = head[key];                tempPtr->next!=NULL && x < listSize-1;                tempPtr=tempPtr->next,++x)            {                if(tempPtr-> currentItem > tempPtr->next->currentItem)                {                    ItemType temp = tempPtr-> currentItem;                    tempPtr-> currentItem = tempPtr->next->currentItem;                    tempPtr->next->currentItem = temp;                    sorted = false;                }            }            --listSize;        }while(!sorted);    }}/* End of Sort */ template<class ItemType>int HashTable<ItemType>::TableSize(){    return hashSize;}/* End of TableSize */ template<class ItemType>int HashTable<ItemType>::TotalElems(){    return totElems;}/* End of TotalElems */ template<class ItemType>int HashTable<ItemType>::BucketSize(int key){    return(!IsEmpty(key)) ? bucketSize[key]:0;}/* End of BucketSize */ template<class ItemType>int HashTable<ItemType>::Count(ItemType searchItem){    int key = Hash(searchItem);    int search = 0;     if(IsEmpty(key))    {        //std::cout<<"nCOUNT ERROR - HASH TABLE EMPTYn";    }    else    {        for(node* tempPtr = head[key];tempPtr!=NULL;tempPtr=tempPtr->next)        {            if(tempPtr->currentItem == searchItem)            {                ++search;            }        }    }    return search;}/* End of Count */ template<class ItemType>void HashTable<ItemType>::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 <<std::endl;                head[x] = head[x]-> next;                delete temp;            }        }        bucketSize[x] = 0;    }}/* End of MakeEmpty */ template<class ItemType>HashTable<ItemType>::~HashTable(){    MakeEmpty();    delete[] head;    delete[] bucketSize;}/* End of ~HashTable */ //   END OF THE HASH TABLE CLASS// -----------------------------------------------------------//   START OF THE HASH TABLE ITERATOR CLASS template <class ItemType>class HashTable<ItemType>::Iterator :        public std::iterator<std::forward_iterator_tag,ItemType>,        public HashTable<ItemType>    {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    // HashTable.    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;    }    ItemType& 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.    ItemType& operator*()    {        // Return "junk" data        // to prevent the program from crashing        if(itHead == NULL)        {            return junk;        }        return itHead->currentItem;    }    ItemType* operator->()    {        return(&**this);    }private:    node* itHead;    ItemType junk;};#endif // http://programmingnotes.org/ ```

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

The iterator class starts on line #368, and is built to support most of the standard relational operators, as well as arithmetic operators such as ‘+,+=,++’ (pre/post increment). The * (star), bracket [] and -> arrow operators are also supported. Click here for an overview demonstrating how custom iterators can be built.

The rest of 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 many of its STL template class counterparts. Here are sample programs demonstrating its use.

``` #1 - Demonstrate Basic Use C++ // DEMONSTRATE USE OF THE REMOVE AND SORT FUNCTIONS #include <iostream> #include <ctime> #include <string> #include <cstdlib> #include <iomanip> #include "HashTable.h" using namespace std; // iterator declarations typedef HashTable<string>::Iterator strIterDec; // hash table size const int TABLE_SIZE = 5; int main() { // delcare variables srand(time(NULL)); const string 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"}; int nameLen = sizeof(names)/sizeof(names); // Hash table class declarations HashTable<string> strHash(TABLE_SIZE); // insert 10 items into each hash table for(int x=0; x < (TABLE_SIZE*2); ++x) { // place all data in bucket 0 // NOTE: you dont want to place all data into one // bucket, this is done for demo purposes only // Normally use the "Insert" function instead strHash.Append(0,names[rand()%(nameLen-1)]); } // assign the iterator to bucket 0 strIterDec it = strHash.begin(0); // display bucket size cout<<"Bucket #0 has "<<strHash.BucketSize(0)<<" items"<<endl; // display the first item cout<<"The first element in bucket #0 is "<< it <<endl; // remove the first item in bucket 0 // NOTE: the second parameter is optional // but since we know we want bucket 0, we use it here strHash.Remove(it,0); // update the iterator to the new table state it = strHash.begin(0); // display the new first item cout<<"nNow bucket #0 has "<<strHash.BucketSize(0)<<" items"<<endl; cout<<"The first element in bucket #0 is "<< it <<endl; // display all the items within the "strHash" table cout<<"nThe unsorted items in strHash bucket #0:n"; for(int x=0; x < strHash.BucketSize(0); ++x) { cout << "it[] = " << it[x] << endl; } // sort the items in bucket 0 strHash.Sort(0); // display all the items within the "strHash" table cout<<"nThe sorted items in strHash bucket #0:n"; for(int x=0; x < strHash.BucketSize(0); ++x) { cout << "it[] = " << it[x] << endl; } return 0; }// http://programmingnotes.org/ 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586 // DEMONSTRATE USE OF THE REMOVE AND SORT FUNCTIONS#include <iostream>#include <ctime>#include <string>#include <cstdlib>#include <iomanip>#include "HashTable.h"using namespace std; // iterator declarationstypedef HashTable<string>::Iterator strIterDec; // hash table sizeconst int TABLE_SIZE = 5; int main(){ // delcare variables srand(time(NULL)); const string 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"};  int nameLen = sizeof(names)/sizeof(names);   // Hash table class declarations HashTable<string> strHash(TABLE_SIZE);  // insert 10 items into each hash table for(int x=0; x < (TABLE_SIZE*2); ++x) { // place all data in bucket 0 // NOTE: you dont want to place all data into one // bucket, this is done for demo purposes only // Normally use the "Insert" function instead strHash.Append(0,names[rand()%(nameLen-1)]); }  // assign the iterator to bucket 0 strIterDec it = strHash.begin(0);  // display bucket size cout<<"Bucket #0 has "<<strHash.BucketSize(0)<<" items"<<endl;  // display the first item cout<<"The first element in bucket #0 is "<< it <<endl;   // remove the first item in bucket 0 // NOTE: the second parameter is optional // but since we know we want bucket 0, we use it here strHash.Remove(it,0);  // update the iterator to the new table state it = strHash.begin(0);  // display the new first item cout<<"nNow bucket #0 has "<<strHash.BucketSize(0)<<" items"<<endl; cout<<"The first element in bucket #0 is "<< it <<endl;  // display all the items within the "strHash" table cout<<"nThe unsorted items in strHash bucket #0:n"; for(int x=0; x < strHash.BucketSize(0); ++x) { cout << "it[] = " << it[x] << endl; }  // sort the items in bucket 0 strHash.Sort(0);  // display all the items within the "strHash" table cout<<"nThe sorted items in strHash bucket #0:n"; for(int x=0; x < strHash.BucketSize(0); ++x) { cout << "it[] = " << it[x] << endl; }  return 0;}// http://programmingnotes.org/ ```

SAMPLE OUTPUT:

```Bucket #0 has 10 items The first element in bucket #0 is Homer```

``` Now bucket #0 has 9 items The first element in bucket #0 is Tamra The unsorted items in strHash bucket #0: it[] = Tamra it[] = Lyndon it[] = Johanna it[] = Perkins it[] = Alva it[] = Jordon it[] = Neville it[] = Lawrence it[] = Jetta ```

```The sorted items in strHash bucket #0: it[] = Alva it[] = Jetta it[] = Johanna it[] = Jordon it[] = Lawrence it[] = Lyndon it[] = Neville it[] = Perkins it[] = Tamra ```

``` #2 - Display Items C++ // DISPLAY ALL DATA INSIDE TABLE USING STD::STRING / INT / STRUCT #include <iostream> #include <ctime> #include <string> #include <cstdlib> #include <iomanip> #include "HashTable.h" using namespace std; // sample struct demo struct MyStruct { string name; }; // iterator declarations typedef HashTable<string>::Iterator strIterDec; typedef HashTable<int>::Iterator intIterDec; typedef HashTable<MyStruct>::Iterator strctIterDec; // hash table size const int TABLE_SIZE = 10; int main() { // delcare variables srand(time(NULL)); const string 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"}; int nameLen = sizeof(names)/sizeof(names); // Hash table class declarations HashTable<string> strHash(TABLE_SIZE); HashTable<int> intHash = TABLE_SIZE; HashTable<MyStruct> strctHash = TABLE_SIZE; // access struct element MyStruct strctAccess; // insert 20 items into each hash table for(int x=0; x < (TABLE_SIZE*2); ++x) { // Use the "insert" function to place data into the hash table // this function automatically hashes the basic datatypes // i.e: int, double, char, char*, string strHash.Insert(names[rand()%(nameLen-1)]); intHash.Insert(rand()%10000); // The "insert" function cant be used on a struct, so we // use the "append" function for the struct declaration. // We use the "strHash" class declaration to use its // hash function, then place the struct in an appropriate // hashed bucket strctAccess.name = names[rand()%(nameLen-1)]; int strctHashKey = strHash.Hash(strctAccess.name); strctHash.Append(strctHashKey,strctAccess); } // display all the items within the "strHash" table for(int x=0; x < strHash.TableSize(); ++x) { if(!strHash.IsEmpty(x)) { cout<<"nstrHash Bucket #"<<x<<":n"; for(strIterDec it = strHash.begin(x); it != strHash.end(x); it+=1) { // access elements using the * (star) operator cout << "*it = " << *it << endl; } } } // creates a line seperator cout<<endl; cout.fill('-'); cout<<left<<setw(80)<<""<<endl; // display all the items within the "intHash" table for(int x=0; x < intHash.TableSize(); ++x) { intIterDec it = intHash.begin(x); if(!intHash.IsEmpty(x)) { cout<<"nintHash Bucket #"<<x<<":n"; for(int y = 0; y < intHash.BucketSize(x); ++y) { // access elements using the [] operator cout << "it[] = " << it[y] << endl; } } } // creates a line seperator cout<<endl; cout.fill('-'); cout<<left<<setw(80)<<""<<endl; // display all the items within the "strctHash" table for(int x=0; x < strctHash.TableSize(); ++x) { if(!strctHash.IsEmpty(x)) { cout<<"nstrctHash Bucket #"<<x<<":n"; for(strctIterDec it = strctHash.begin(x); it!=strctHash.end(x); it=it+1) { // access struct/class elements using the -> operator cout << "it-> = " << it->name << endl; } } } return 0; }// http://programmingnotes.org/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122 // DISPLAY ALL DATA INSIDE TABLE USING STD::STRING / INT / STRUCT#include <iostream>#include <ctime>#include <string>#include <cstdlib>#include <iomanip>#include "HashTable.h"using namespace std; // sample struct demostruct MyStruct{ string name;}; // iterator declarationstypedef HashTable<string>::Iterator strIterDec;typedef HashTable<int>::Iterator intIterDec;typedef HashTable<MyStruct>::Iterator strctIterDec; // hash table sizeconst int TABLE_SIZE = 10; int main(){ // delcare variables srand(time(NULL)); const string 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"};     int nameLen = sizeof(names)/sizeof(names);   // Hash table class declarations HashTable<string> strHash(TABLE_SIZE); HashTable<int> intHash = TABLE_SIZE; HashTable<MyStruct> strctHash = TABLE_SIZE;  // access struct element MyStruct strctAccess;   // insert 20 items into each hash table for(int x=0; x < (TABLE_SIZE*2); ++x) { // Use the "insert" function to place data into the hash table // this function automatically hashes the basic datatypes // i.e: int, double, char, char*, string strHash.Insert(names[rand()%(nameLen-1)]); intHash.Insert(rand()%10000);  // The "insert" function cant be used on a struct, so we // use the "append" function for the struct declaration. // We use the "strHash" class declaration to use its // hash function, then place the struct in an appropriate // hashed bucket strctAccess.name = names[rand()%(nameLen-1)]; int strctHashKey = strHash.Hash(strctAccess.name); strctHash.Append(strctHashKey,strctAccess); }  // display all the items within the "strHash" table for(int x=0; x < strHash.TableSize(); ++x) { if(!strHash.IsEmpty(x)) { cout<<"nstrHash Bucket #"<<x<<":n"; for(strIterDec it = strHash.begin(x); it != strHash.end(x); it+=1) { // access elements using the * (star) operator cout << "*it = " << *it << endl; } } } // creates a line seperator cout<<endl; cout.fill('-'); cout<<left<<setw(80)<<""<<endl;  // display all the items within the "intHash" table for(int x=0; x < intHash.TableSize(); ++x) { intIterDec it = intHash.begin(x); if(!intHash.IsEmpty(x)) { cout<<"nintHash Bucket #"<<x<<":n"; for(int y = 0; y < intHash.BucketSize(x); ++y) { // access elements using the [] operator cout << "it[] = " << it[y] << endl; } } }  // creates a line seperator cout<<endl; cout.fill('-'); cout<<left<<setw(80)<<""<<endl;  // display all the items within the "strctHash" table for(int x=0; x < strctHash.TableSize(); ++x) { if(!strctHash.IsEmpty(x)) { cout<<"nstrctHash Bucket #"<<x<<":n"; for(strctIterDec it = strctHash.begin(x); it!=strctHash.end(x); it=it+1) { // access struct/class elements using the -> operator cout << "it-> = " << it->name << endl; } } }  return 0;}// http://programmingnotes.org/ ```

SAMPLE OUTPUT:

``` strHash Bucket #0: *it = Cinderella *it = Perkins *it = Krystal *it = Roger *it = Roger```

``` strHash Bucket #1: *it = Lilliam *it = Lilliam *it = Theda strHash Bucket #2: *it = Arie strHash Bucket #3: *it = Magda strHash Bucket #6: *it = Edda *it = Irvin *it = Kati *it = Lyndon strHash Bucket #7: *it = Deb *it = Jaime strHash Bucket #8: *it = Neville *it = Victoria strHash Bucket #9: *it = Chery *it = Evelia -------------------------------------------- intHash Bucket #0: it[] = 2449 it[] = 6135 intHash Bucket #1: it[] = 1120 it[] = 852 intHash Bucket #2: it[] = 5727 intHash Bucket #3: it[] = 1174 intHash Bucket #4: it[] = 2775 it[] = 3525 it[] = 8375 intHash Bucket #5: it[] = 4322 it[] = 8722 it[] = 5016 intHash Bucket #6: it[] = 5053 it[] = 7231 it[] = 1571 intHash Bucket #7: it[] = 1666 it[] = 4510 it[] = 1548 it[] = 3646 intHash Bucket #9: it[] = 2756 -------------------------------------------- strctHash Bucket #0: it-> = Cherilyn it-> = Roger strctHash Bucket #1: it-> = Tamra it-> = Alex it-> = Theda strctHash Bucket #2: it-> = Nigel it-> = Alva it-> = Arie strctHash Bucket #4: it-> = Basil strctHash Bucket #5: it-> = Tod strctHash Bucket #6: it-> = Irvin it-> = Lyndon strctHash Bucket #7: it-> = Amina it-> = Hillary it-> = Kenneth it-> = Amina strctHash Bucket #8: it-> = Gene it-> = Lemuel it-> = Gene ```

```strctHash Bucket #9: it-> = Albertina ```

## 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()```