Abstract Binary Search Tree Implementation in C

There are several ways to store data using different data structures like Array, Linked Lists , Trees, Graphs, Hashmaps etc. The choice of the data structure depends on the application which extracts that data. On searching the web , one can easily find out which data structure is required for their application. Binary Search Tree is one such data structure which is generally used for storing data.

A binary search tree consists of members called as nodes which have the data embedded in them. Generally, a BST node contains address fields and data field. The structure of a BST is something like this :

Each node can have a left subtree and right subtree which may or may not have any nodes.

Binary Search tree has some properties which identifies it :

• The left subtree members have a value which is always less than the value at the root node
• The right subtree members have a value which is always greater than the value at the root node
• Both the subtrees must be also a BST.

The implementation provided in this post uses an abstract data type (void). To use this implementation as it is, one must implement these two functions 

1. Comparison Function - This function compares the data between two nodes. This function must return -1, 0 or 1 only.  The signature for this function is int <function-name> (void * data1, void * data2).
1. Function should return 1 when data1 is greater than data2.
2. Function should return -1 when data1 is lesser than data2.  
3. Function should return 0 when data1 is equal to data2.  
2. Display Function - This function is used for display purposes only. It displays the node data.

A sample implementation of these two functions is presented in the driver example(bstdriver.c) for the BST. This sample implementation uses int type as data.

 
/*bst.h*/
typedef struct bstNode
{
    struct bstNode *left;       /*Left Child*/
    struct bstNode *right;      /*Right Child*/
    struct bstNode *parent;     /*Parent Child*/
    void *data;                 /*Data*/
}BSTNode;

void BSTDestroy(BSTNode *root);
void BSTInsert(BSTNode **root, void *data, int (*cmp_fn)(void *, void *));
void BSTDelete(BSTNode **root, void *data, int (*cmp_fn)(void *, void *));
BSTNode* BSTSearch(BSTNode *root, void *data, int (*cmp_fn)(void *, void *));
void BSTDisplay(BSTNode *root, void (*display_fn)(BSTNode *));

 
/*bst.c*/
#include <stdio.h>
#include <stdlib.h>

#include "bst.h"

/* @brief Function to determine if a child is a left child or right child in a BST
 * @param data Pointer to the data to be used
 * @return LEFT - if left child
 *         RIGHT - if right child
 */
static inline const char* BSTFindChildLoc(BSTNode *parent, BSTNode *child)
{
    return (((parent->left)==(child))?"LEFT":"RIGHT");
}

/* @brief Function to swap data between two nodes in a BST
 * @param data Pointer to the data to be used
 * @return void
 */
static inline void BSTSwapNodeData(BSTNode **node1, BSTNode **node2 )
{
    void *tmp;
    tmp = (*node1)->data;
    (*node1)->data = (*node2)->data;
    (*node2)->data = tmp;
}

/* @brief Function to create a node in a BST
 * @param data Pointer to the data to be used
 * @return Address of the node created
 */
BSTNode* BSTCreateNode(void *data)
{
    /*Allocate memory*/
    BSTNode* node= (BSTNode*)malloc(sizeof(BSTNode));

    if(NULL == node)
    {
        printf("Error: Memory Allocation could not be completed\n");
        return NULL;
    }

    /*Initialize links*/
    node->left = NULL;
    node->right= NULL;
    node->parent= NULL;
    node->data = data;

    printf("Allocated Node with address %p\n", node);
    return node;
}

/* @brief Function to destroy all nodes in a BST
 * @param root Pointer to the root of the BST
 * @return void
 */
void BSTDestroy(BSTNode *root)
{
    if(root)
    {
        /*Traverse down the left subtree*/
        if(root->left)
            BSTDestroy(root->left);
        /*Traverse down the right subtree*/
        if(root->right)
            BSTDestroy(root->right);
        /*Free the memory*/
        free(root);
        printf("DeAllocated Node with address %p\n", root);
    }
}

/* @brief Function to insert a node in a BST
 * @param root Pointer to pointer to the root of the BST
 * @param data Pointer to the data to be inserted
 * @param cmp_fn Funtion Pointer to the comparison function for BST[Provided by user]
 * @return void
 */
void BSTInsert(BSTNode **root, void *data, int (*cmp_fn)(void *, void *))
{
    BSTNode *tmp = NULL;
    BSTNode *ptr = NULL;

    if(NULL == root)
    {
        printf("Error: Null root\n");
        return;
    }


    if(!(*root))
    {
        /*Create a node*/
        tmp = BSTCreateNode(data);

        if(NULL == tmp)
        {
            printf("Error: Node insertion failed\n");
            return;
        }

        /*Root Node*/
        *root = tmp;
        return;
    }

    ptr = *root;

    /*If data is greater than the current node's data*/
    if(cmp_fn(data,ptr->data) == 1)
    {
        /*data > ptr->data : Insert to right*/
        if(ptr->right == NULL)
        {
            /*Create a node*/
            tmp = BSTCreateNode(data);

            if(NULL == tmp)
            {
                printf("Error: Node insertion failed\n");
                return;
            }

            tmp->parent = ptr;
            ptr->right = tmp;
            return;
        }
        else
        {
            BSTInsert(&(ptr->right), data, cmp_fn);
        }
    }
    /*If data is lesser than the current node's data*/
    else if(cmp_fn(data,ptr->data) == -1)
    {
        /*data > ptr->data : Insert to right*/
        if(ptr->left == NULL)
        {
            tmp = BSTCreateNode(data);

            if(NULL == tmp)
            {
                printf("Error: Node insertion failed\n");
                return;
            }

            tmp->parent = ptr;
            ptr->left = tmp;
            return;
        }
        else
        {
            BSTInsert(&(ptr->left), data, cmp_fn);
        }
    }
    /*If data is equal to the current node's data*/
    else
        printf("Error: Duplicate\n");
}

/* @brief Function to find the minimum valued node in the left subtree of a node
 * @param node Pointer to the node whose min valued child in left subtree has to be found
 * @return Address of the minimum valued node in the left subtree
 */
static BSTNode* BSTMinVal(BSTNode* node)
{
    BSTNode* current = node;

  /*Go to the leftmost member of the tree */
  while (current->left != NULL)
  {
    current = current->left;
  }
  return current;
}

/* @brief Function to find the Inorder successor of a node in a BST
 * @param node Pointer to the node whose inorder successor has to be found
 * @return Address of the Inorder successor
 */
static BSTNode* BSTInorderSuccessor(BSTNode* node)
{
    BSTNode *inOrdSucc = NULL;
    if(NULL == node)
        return NULL;

    /*Traverse the right subtree and find the minimum value */
    if( node->right != NULL )
        return BSTMinVal(node->right);

    inOrdSucc = node->parent;

    while(inOrdSucc != NULL && node == inOrdSucc->right)
    {
        node = inOrdSucc;
        inOrdSucc = inOrdSucc->parent;
    }
    return inOrdSucc;

}

/* @brief Helper Function to update the parent node links in a BST
 * @param node Pointer to pointer to the node whose parent will be updated
 * @param ptr Target Link
 * @return void
 */
static inline void updateParent(BSTNode **node, BSTNode *ptr)
{
    /*If the child is a left child*/
    if(BSTFindChildLoc((*node)->parent, *node) == "LEFT")
    {
        (*node)->parent->left = ptr;
    }
    /*If the child is a right child*/
    else
    {
        (*node)->parent->right = ptr;
    }
}

/* @brief Function to delete a node in a BST
 * @param root Pointer to pointer to the root of the BST
 * @param data Pointer to the data to be searched
 * @param cmp_fn Funtion Pointer to the comparison function for BST[Provided by user]
 * @return void
 */
void BSTDelete(BSTNode **root, void *data, int (*cmp_fn)(void *, void *))
{
    BSTNode *ptr = NULL;
    BSTNode *tmp = NULL;

    if(NULL == root)
    {
        printf("Error: Null root\n");
        return;
    }

    /*Search if the node exists in the BST*/
    ptr = BSTSearch(*root, data, cmp_fn);

    if(NULL == ptr)
    {
        printf("Error: Node not found\n");
        return;
    }

    /*If the node has no children*/
    if(ptr->left == NULL && ptr->right == NULL)
    {
        /*No children*/
         tmp = ptr;

         /*Non-Root Node*/
         if(ptr->parent)
            updateParent(&ptr, NULL);   /*Update the parent's link*/
         /*Root Node*/
         else
             *root = NULL;

         ptr = NULL;
         free(tmp);
         printf("DeAllocated Node with address %p\n", tmp);
    }
    /*If the node has single child*/
    else if((ptr->left != NULL && ptr->right == NULL) || (ptr->left == NULL && ptr->right != NULL))
    {
        tmp = ptr;

        /*Single Child*/
        if((ptr->left != NULL) && (ptr->right == NULL))
        {
            ptr->left->parent = ptr->parent;

            /*Non-Root Node*/
            if(ptr->parent)
                updateParent(&ptr, ptr->left);   /*Update the parent's link*/
            /*Root Node*/
            else
                *root = ptr->left;
        }
        else
        {
            ptr->right->parent = ptr->parent;   /*Update the parent's link*/
            /*Non-Root Node*/
            if(ptr->parent)
                updateParent(&ptr, ptr->right);
            /*Root Node*/
            else
                *root = ptr->right;
        }

        free(tmp);
        printf("DeAllocated Node with address %p\n", tmp);
    }
    /*If the node has two children*/
    else if((ptr->left != NULL) && (ptr->right != NULL))
    {
        /*Find the inorder successor of the node*/
        BSTNode *inOrdSucc = BSTInorderSuccessor(ptr);

        /*Swap the node's data with inorder successor's data*/
        BSTSwapNodeData(&ptr, &inOrdSucc);

        /*Delete the inorder successor node*/
        BSTDelete(&inOrdSucc, data, cmp_fn);
    }
}

/* @brief Function to search a data in a BST
 * @param root Pointer to the root of the BST
 * @param data Pointer to the data to be searched
 * @param cmp_fn Funtion Pointer to the comparison function for BST[Provided by user]
 * @return Address of the node found
 *         NULL if node not found
 */
BSTNode* BSTSearch(BSTNode *root, void *data, int (*cmp_fn)(void *, void *))
{
    BSTNode *ptr = NULL;

    if(NULL == root)
        return NULL;

    ptr = root;

    /*If the data is found*/
    if(cmp_fn(data, ptr->data) == 0)
    {
        return ptr;
    }
    /*If data is greater than the current node's data*/
    else if(cmp_fn(data, ptr->data) == 1)
    {
        return BSTSearch(ptr->right, data, cmp_fn);
    }
    /*If data is lesser than the current node's data*/
    else if(cmp_fn(data, ptr->data) == -1)
    {
        return BSTSearch(ptr->left, data, cmp_fn);
    }

    return NULL;
}

/* @brief Function to traverse all nodes in a BST in InOrder
 * @param root Pointer to the root of the BST
 * @param display_fn Funtion Pointer to the display function for BST[Provided by user]
 * @return void
 */
static void BSTInOrder(BSTNode *root, void (*display_fn)(BSTNode *))
{
    if(NULL == root)
    {
        printf("Error: NULL root\n");
        return;
    }

    if(root->left)
        BSTInOrder(root->left, display_fn);

    printf("[%p]",root->data);
    display_fn(root);

    if(root->right)
        BSTInOrder(root->right, display_fn);

}

/* @brief Function to traverse all nodes in a BST in PostOrder
 * @param root Pointer to the root of the BST
 * @param display_fn Funtion Pointer to the display function for BST[Provided by user]
 * @return void
 */
static void BSTPostOrder(BSTNode *root, void (*display_fn)(BSTNode *))
{
    if(NULL == root)
    {
        printf("Error: NULL root\n");
        return;
    }

    if(root->left)
        BSTPostOrder(root->left, display_fn);

    if(root->right)
        BSTPostOrder(root->right, display_fn);

    printf("[%p]",root->data);
    display_fn(root);
}

/* @brief Function to traverse all nodes in a BST in PreOrder
 * @param root Pointer to the root of the BST
 * @param display_fn Funtion Pointer to the display function for BST[Provided by user]
 * @return void
 */
static void BSTPreOrder(BSTNode *root, void (*display_fn)(BSTNode *))
{
    if(NULL == root)
    {
        printf("Error: NULL root\n");
        return;
    }

    printf("[%p]",root->data);
    display_fn(root);

    if(root->left)
        BSTPreOrder(root->left, display_fn);

    if(root->right)
        BSTPreOrder(root->right, display_fn);

}

/* @brief Function to display all nodes in a BST
 * @param root Pointer to the root of the BST
 * @param display_fn Funtion Pointer to the display function for BST[Provided by user]
 * @return void
 */
void BSTDisplay(BSTNode *root, void (*display_fn)(BSTNode *))
{
    printf("InOrder ->",root->data);
    BSTInOrder(root,display_fn);
    printf("\n",root->data);

    printf("PreOrder ->",root->data);
    BSTPreOrder(root,display_fn);
    printf("\n",root->data);

    printf("PostOrder ->",root->data);
    BSTPostOrder(root,display_fn);
    printf("\n",root->data);
}

 
/*bstdriver.c*/
/*
 * Compile: gcc -o test bst.c bstdriver.c
 * Run: ./test
 */
#include <stdio.h>
#include "bst.h"

int data[]={9,1,6,3,8,4,2,5,7};

/*Comparison function*/
int cmp_fn(void *data1, void *data2)
{
    if(*((int*)data1) > *((int*)data2))
        return 1;
    else if(*((int*)data1) < *((int*)data2))
        return -1;
    else
        return 0;
}

/*Display Function*/
static void displayNode(BSTNode *node)
{
    if(node)
        printf("%d ",*((int*)node->data));
}

int main()
{
    BSTNode *root = NULL;

    int i,sVal=-1;
    int size = sizeof(data)/sizeof(data[0]);

    for(i=0; i < size; i++)
        BSTInsert(&root, &data[i], cmp_fn);

    BSTDisplay(root, displayNode);

    printf("Search Value : ");
    scanf("%d", &sVal);

    if(NULL == BSTSearch(root, &sVal, cmp_fn))
        printf("Not Found\n");
    else
        printf("Found\n");

    printf("Delete Value : ");
    scanf("%d", &sVal);
    BSTDelete(&root, &sVal, cmp_fn);
    BSTDisplay(root, displayNode);

    BSTDestroy(root);
}

Circular Queue using Array

This is a simple implementation of Circular Queue using arrays.
A Circular Queue is a Data Structure in which the data is stored in a circular manner , i.e. the array can be reused from the front also.

 #include <iostream>
#include <stdlib.h>

void err_quit(char* msg)
{
  printf("%s\n",msg);
  exit(0);
}

using namespace std;
class cirq{

  int cirq_len;
  int *queue;
  
  public:
    
  int front;
  int rear;
  cirq(int size);
  ~cirq();
  void insert_rear(int item);
  void delete_front();
  void show();
};

cirq::cirq(int size = 0)
{
  front = -1;
  rear = -1;
  cirq_len = size;

  queue = new int[size]; 
}
cirq::~cirq()
{
  delete[] queue;
}

void cirq::insert_rear(int item)
{

  if((front == 0)&& (rear == cirq_len - 1) || (rear + 1 == front))
  {
    err_quit("Queue Overflow!!!");
  }
  
  if(rear == -1)
  {
      front = rear = 0;
  }
  else if(rear == (cirq_len - 1))
  {
      rear  = 0;
  }
  else 
    rear++;
  
  queue[rear] = item;

}
       
void cirq::delete_front()
{ 
  if(front == -1 || rear == -1)
  {
    err_quit("Queue Underflow!!!");
  }
  front++;
 
}
       
void cirq::show()
{
  int i;
  if( front == -1 || rear == -1)
  {
    cout<<"Queue is empty!!!";
    return;
  }

  if(front < rear)
    for(i = front ; i <= rear; i++)
      cout<<queue[i]<<" ";

  else
  {
    for(i = front ; i <= (cirq_len - 1); i++)
      cout<<queue[i]<<" ";
    for(i = 0 ; i <= rear ; i++)
      cout<<queue[i]<<" ";
      
  }
  cout<<endl;
}

       
int main()
{
  int ch;
  cirq c1(5); 
  c1.show();
  c1.insert_rear(1);
  c1.show();
  c1.insert_rear(2);
  c1.show();
  c1.insert_rear(3);
  c1.show();
  c1.insert_rear(4);
  c1.show();
  c1.insert_rear(5);
  c1.show();

  c1.delete_front();
  c1.show();
  c1.delete_front();
  c1.show();
  c1.insert_rear(6);
  c1.show();
  c1.insert_rear(7);
  c1.show();
  c1.insert_rear(7);
  c1.show();
  c1.insert_rear(7);
  c1.show();
  
}

Stack Implementation in C++

A Stack is a data structure which works on the principle LIFO(Last In, First Out).The basic operations in a Stack are :

1. Push : In which we push the data into the stack.
2. Pop : In which we remove an element from the Stack.

All insertions and removals are done only from one side of the Stack , which is called the 'top' of the Stack.

A stack is generally used in function calls where the local variables are pushed onto the Stack and when the function returns , it pops the variables from the Stack.

This is a simple implementation of Stack in C++.

#include <iostream>

using namespace std;

class Stack
{
private:
    int *p;
    int top,length;

public:
    Stack(int = 0);
    ~Stack();

    void push(int);
    int pop();
    void display();
};

Stack::Stack(int size)
{
    top=-1;
    length=size;
    if(size == 0)
        p = 0;
    else
        p=new int[length];
}

Stack::~Stack()
{
    if(p!=0)
        delete [] p;
}

void Stack::push(int elem)
{
    if(p == 0)                //If the stack size is zero, allow user to mention it at runtime
    {
        cout<<"Stack of zero size"<<endl;
        cout<<"Enter a size for stack : ";
        cin >> length;
        p=new int[length];
    }
    if(top==(length-1))     //If the top reaches to the maximum stack size
    {
        cout<<"\nCannot push "<<elem<<", Stack full"<<endl;
        return;
    }
    else
    {
        top++;
        p[top]=elem;
    }
}
int Stack::pop()
{
    if(p==0 || top==-1)
    {
        cout<<"Stack empty!";
        return -1;
    }
    int ret=p[top];
    top--;
    return ret;
}

void Stack::display()
{
    for(int i = 0; i <= top; i++)
        cout<<p[i]<<" ";
    cout<<endl;
}

int main()
{
    Stack s1;             //We are creating a stack of size 'zero'
    s1.push(1);
    s1.display();
    s1.push(2);
    s1.push(3);
    s1.push(4);
    s1.push(5);
    s1.display();
    s1.pop();
    s1.display();
    s1.pop();
    s1.display();
    s1.pop();
    s1.display();
    s1.pop();
    s1.display();
}

Doubly Linked List in C++

Here's a simple implementation of doubly linked list using C++

//dll.hpp
class dnode
{
public:
    dnode();
    dnode *prev;
    int data;
    dnode *next;
    ~dnode();
};

class DLL
{
private:
    dnode *front;
    dnode *rear;
    dnode *newnode;
public:
    DLL();
    dnode* create_node(int data);
    void insertAtFront(int data);
    void insertAtRear(int data);
    void insertBefore(int data, dnode *node);
    void insertAfter(int data, dnode *node);
    void deleteFront();
    void deleteLast();
    void del(int data);
    dnode* search(int data);
    void display();
    ~DLL();
};

//dll.cpp
#include <iostream>
#include "dll.hpp"

using namespace std;

dnode::dnode()
{
    cout<<"dnode()"<<endl;
}

dnode::~dnode()
{
    cout<<"~dnode()"<<endl;
}

DLL::DLL()
{
    front = NULL;
    rear = NULL;
    cout<<"DLL()"<<endl;
}

dnode* DLL :: create_node(int data)
{
    newnode = new dnode;
    newnode->data = data;
    newnode->prev = NULL;
    newnode->next = NULL;
    return newnode;
}

void DLL::insertAtFront(int data)
{
    dnode* newnode = create_node(data);

    if(front == NULL)
    {
        front = newnode;
        rear = newnode;
    }
    else
    {
        newnode -> next = front;
        front -> prev = newnode;
        front = newnode;
    }
}

void DLL::insertAtRear(int data)
{
    dnode *prev,*ptr;
    dnode* newnode = create_node(data);

    if(front == NULL)
    {
        front = newnode;
        rear = newnode;
    }
    else
    {
        for(prev = front, ptr = front -> next ; ptr ; prev = ptr, ptr = ptr -> next);

        if(ptr == NULL)
        {
            prev -> next = newnode;
            newnode -> prev = prev;
            rear = newnode;
        }
    }
}

void DLL::insertBefore(int data, dnode *node)
{
    dnode *prev,*ptr;
    dnode* newnode = create_node(data);

    if(front == NULL)
    {
        front = newnode;
        rear = newnode;
    }
    else
    {
        node->prev->next = newnode;
        newnode -> prev = node -> prev;
        newnode -> next = node;
    }
}

void DLL::insertAfter(int data, dnode* node)
{
    dnode *prev,*ptr;
    dnode* newnode = create_node(data);

    if(front == NULL)
    {
        front = newnode;
        rear = newnode;
    }
    else
    {
        newnode -> next = node -> next;
        node->next = newnode;
        newnode -> prev = node;
    }

}

void DLL::deleteFront()
{
    dnode *temp;
    
    temp = front;
    front = front -> next;
    front -> prev = NULL;

    delete temp;
}

void DLL::deleteLast()
{
    dnode *temp;
    
    temp = rear;
    rear -> prev -> next = NULL;
    rear = rear -> prev;
    delete temp;
}

void DLL::del(int data)
{
  if(front == NULL)
  {
    cout<<"List is empty"<<endl;
    return;
  }

  dnode *searchNode;

  if((searchNode = search(data)) != NULL)
  {
    cout<<"SNData :"<<rear->data<<endl; 
    if(front == searchNode)
    {
      cout<<"front"<<endl;
      deleteFront();
    }
    else if(rear == searchNode)
    {
      cout<<"last"<<endl;
      deleteLast();
    }
    else
    {
      dnode *temp;
      temp = searchNode;

      searchNode -> prev -> next = searchNode -> next;
      searchNode -> next -> prev = searchNode -> prev;

      delete temp;
    }
  }
}

dnode* DLL::search(int data)
{
  dnode *prev,*ptr;
  for(ptr = front ; ptr ; ptr = ptr -> next)
  {
    if(ptr -> data == data)
      return ptr;
  }
    
  return NULL;
}


void DLL::display()
{
    dnode *ptr;

    if(front == NULL)
    {
        cout<<"List is empty"<<endl;
        return;
    }

    for(ptr = front ; ptr ; ptr = ptr ->next)
        cout<<"->"<<ptr->data;

    cout<<endl;
}

DLL::~DLL()
{
    while(front)
    {
        dnode* temp = front;
        front  = front ->next;
        delete temp;
    }
    cout<<"~DLL()"<<endl;
}

int main()
{
    DLL d1;

    d1.insertAtFront(4);
    d1.insertAtFront(2);
    d1.insertAtFront(23);
    d1.insertAtRear(12);
    d1.insertAtRear(27);
    d1.insertAtRear(42);
    d1.display();
    d1.deleteFront();
    d1.display();
    d1.deleteLast();
    d1.display();
    d1.del(27);
    d1.display();
}

Simple Stack using Arrays

A Simple stack using arrays.

#include <iostream>
#include <stdlib.h>
using namespace std;

class Base{
  
  public:
  virtual void push(int) = 0;
  virtual int pop() = 0;
};

class Stack : public Base{
 
  int *arr;
  int stack_len; 
  public:
    
   int top;
   Stack(int size);
  ~Stack();

 void push(int);
 int pop();
 void print_stack();
};

Stack::Stack(int size)
{
   arr = new int[size];
   top = -1;
   stack_len = size;
}

Stack::~Stack()
{
  delete[] arr;
}

void Stack::push(int item)
{
  if((top + 1) < stack_len)
  { 
    cout<<"Pushed "<<item<<endl;
    arr[++top] = item;
    print_stack();
  }
  else
    {
   cout<<"Stack Full!!!";
   exit(0);
 }
}

int Stack::pop()
{
  if(top!= -1)
  {
    cout<<"Popped "<<arr[top]<<endl;
    --top;
    print_stack();
  }
  else
    {
   cout<<"Stack Empty!!!";
   exit(0);
 }
}

void Stack::print_stack()
{
  int i;
  for(i = top ; i > -1 ; i--)
  {
    cout<<" "<<arr[i];
  }
  cout<<endl;
}

int main()
{
  Stack s1(5);

  s1.push(1);
  s1.push(2);
  s1.push(3);
  s1.push(4);
  
  s1.pop();
  s1.pop();

}

Hash Table

Hashing is one of the best techniques when it comes to storing a large amount of random data or it can be unrandom data too :)

It is generally easy to store your data into an array or a linked list. But the searching becomes very hectic and time consuming when this data grows to millions of records.

So the big guys came up with hashing as an alternative to store and retrieve large amounts of data. The search became much faster upto O(1) if there are no collisions!!

Well lets discuss how hashing works if you really want that whatever I have written above starts making sense.

We store data into Hash tables on the basis of a key generated by a hash function.
This hash function uses some formula to generate a key which is in the range of indexes of the Hash Table. And then we store that data into the Hash Table with the help of this key.

key = hash(data);
HashTable[key] = data ;

Now you may be wondering that how this function works.
Take an example :-
If the data to be stored are integers we can define our hash function to return

data % prime

where prime is any prime number(preferably a big prime number)

But now one more problem arises. If we are taking such a formula then the key could be duplicated. Well this situation is called a 'Collision'.

There are various methods for Collision Resoultion.
e.g. Rehashing , Separate Chaining

Separate Chaining is being used by the code snippet below.
Normally data is stored one at a single index. But to resolve collision, at each index we maintain a linked list instead to which we can add our data when the collision occurs. When at the time of searching we get an index , we actually reach at the head of the linked list and then we can continue searching the Linked List.

This has reduced our searching time from searching a million records to few hundreds.So enjoy the code.

P.S : As I am a normal human being , there would be bugs in this code too. Please point out those so that I can improve the quality of the code here.

//linklist_impl.hpp
#include<string>
using namespace std;
class linklist
{
    int c;
    struct node
    {
    public:
        string data;
        node *link;
    } *p;
public:
    linklist();
    void append(string &str);
    void del(string &str);
    void display();
    string getData();
    int searchlist(string);
    bool isListEmpty();
    ~linklist();
};

//linklist_impl.cpp
#include 
#include 
#include 
#include "linklist_impl.hpp"
using namespace std;


linklist::linklist()
{
    p = NULL;
    c = 0;
}

void linklist::append(string &str)
{
    node *q, *t;
    if(p==NULL)
    {
        p = new node;
        p->data = str;
        p->link = NULL;
        c += 1;
    }
    else
    {
        q = p;
        while(q->link != NULL)
        {
            q = q->link;
        }
        t = new node;
        t->data = str;
        t->link = NULL;
        q->link = t;
        c += 1;
    }
}

void linklist::del(string &str)
{
    node *q, *r;
    q = p;
    if(q->data == str)
    {
        p = q->link;
        delete q;
        c -= 1;
        return;
    }
    r = q;
    while(q != NULL)
    {
        if(q->data == str)
        {
            r->link = q->link;
            delete q;
            c -= 1;
            return;
        }
        r = q;
        q = q->link;
    }
    cout<<"Element "<<str<<" not found"<<endl;
}

void linklist::display()
{
    node *q;
    int i;
    for(q = p, i = 0; q != NULL, i < c; q = q->link, i++)
    {
        cout<<"\t"<<i<<": "<<q->data<<endl;
    }
}

string linklist::getData()
{
  return p->data;
}

bool linklist::isListEmpty()
{
    node *q;
    int i,flag = 0;
    for(q = p, i = 0; q != NULL, i < c; q = q->link, i++)
    {
      if(q->data != "")
        flag = 1;
    }
    if(flag == 1)
      return false;
    else 
      return true;
}

int linklist::searchlist(string searchItem)
{
    node *q;
    int i;
    for(q = p, i = 0; q != NULL, i < c; q = q->link, i++)
    {
      if(q -> data == searchItem)
        return i;
    }
    return -1;
}

linklist::~linklist()
{
    node *q;
    if(p == NULL)
    {
        return;
    }
    while(p != NULL)
    {
        q = p->link;
        delete p;
        p = q;
    }
}

//schashtable.cpp
#include<iostream>
#include<sys/time.h>
#include<stdlib.h>
#include<stdio.h>
#include<limits>
#include<cstring>
#include "linklist_impl.hpp"

using namespace std;
struct timeval starttime,endtime,timediff;
enum {FILLED = 0 , ALL};
const int sizeHTable = 5;


class table
{

private:
    linklist *items;
    int nel;
    int strhash(const char *str); 
public:
    table(int size);
    ~table();
    void addItem();
    int searchTable(string);
    void delItem();
    void display( int mode);
    int getCount();
    bool isEmpty();
};

#define BAD_INPUT_CUTOFF 3
unsigned int getIntInRange(unsigned int min, unsigned int max, 
                           const char *prompt)
{
    int input, //used to get input
    bad_count=0; //used to keep track of how many bad attempts.
    do
    {
        std::cout << prompt; 
        std::cin >> input; 
        if (!std::cin.good() || input < min || input > max)
        {
            std::cout << "\nInvalid Input!" << std::endl;
            std::cin.clear(); //resets the state flag
            
//clears out the buffer
std::cin.ignore(std::numeric_limits<std::streamsize>::max(),'\n'); 
                   
            bad_count++; //User made a bad input, count it
            input = 0;   // user did not enter a valid number
        }
        //See if this is a valid number (users are mean/stupid sometimes)
    }
    while (input == 0 && bad_count < BAD_INPUT_CUTOFF);
    return input;
}


table::table(int size)
{
    items = new linklist[size];
    for(int i = 0; i<sizeHTable ;i++)
    nel = 0;
}

table::~table()
{   
    if(items)
    delete[] items;
}

int table::strhash(const char *str) {
    unsigned long hash = 0;
      int i=0;
        while(i <= strlen(str)) {
              hash = hash + (hash<<5) + (unsigned long)(str[i]); 
                  i++;
                    }
          return (hash%sizeHTable); //return the hashed number which must be  
                                    //between 0 an size-1, this is why I used
                                    //hash%size
}

void table::addItem()
{
        string str;
        
        cout<<"\nEnter Data : ";
        cin>>str;

        
        int i = strhash(str.c_str());
        if( i >= 0 && i < sizeHTable )
        {
            items[i].append(str);
            cout<<"\nInserted";
            nel++;
            return;
        }

}

int table::searchTable(string searchItem)
{
    int pos;
    
    int i = strhash(searchItem.c_str());

    if((pos = items[i].searchlist(searchItem)) != -1 )
    {
        cout<<"Bucket["<<i<<"] -> pos : "<<pos<<"\t" <<"\t"<< endl;
        return i;
    }
    else
    {
            cout<<"Data "<<searchItem<<" not present in the table" << endl;
            return -1;
    }
}

void table::delItem()
{
    string item;
    cout<<"\nEnter an item to delete : ";
    cin>>item;
    
    int index;
    index = strhash(item.c_str());
        items[index].del(item);
        nel--;
}

bool table::isEmpty()
{
    if( nel > 0)
    {
        return false;
    }
    else
    {
        cout<<"\nTable is Empty"<<endl;
        return true;
    }
}

void table::display(int mode = FILLED)
{
    if(isEmpty())
        return;

   if(mode == FILLED)
   {
     int i;
     for(i=0; i<sizeHTable; i++)
     {  
        if(items[i].isListEmpty() == false)
        {
          cout<<"Bucket["<<i<<"] :"<<endl;
          items[i].display(); //call the function of our linked list, 
                              //which outputs it's records with their indexes
        }
     }
   }  
   else if(mode == ALL)
   { 
     int i;
     for(i=0; i<sizeHTable; i++)
     {
        cout<<"Bucket["<<i<<"] :"<<endl;
        items[i].display(); //call the function of our linked list, 
                            //which outputs it's records with their indexes
     }
   }  
}

int table::getCount()
{
    return nel;
}

int main()
{
    int choice;
    
    string item;
    table T1(sizeHTable);
    int mode;

    while(1)
    {
        choice = getIntInRange(1,6,"\n1.Add New Item\n2.Delete Item 
                 \n3.Search Item \n4.Display Hash Table \n5.Get the 
                  number of elements \n6.Exit\nEnter your choice : ");
        
            switch(choice)
            {
            case 1 :
                T1.addItem();
                break;
            case 2 :
                T1.delItem();
                break;
            case 3 :
                if(T1.isEmpty() != true)
                {
                    cout<<"\nEnter an item to search : ";
                    cin>>item;
                    T1.searchTable(item);
                }
                break;
            case 4 :
                cout<<"\nEnter display mode (0 - FILLED / 1- ALL) : ";
                cin>>mode;
                T1.display(mode);
                break;
             case 5 :
                cout<<"Total no. of elements : "<<T1.getCount()<<endl;
                break;
             case 6 :
                exit(0);
            }
        
    }
    
    
}

Run the example in gnu compiler as

user@linux~> g++ linklist_impl.cpp schashtable.cpp
user@linux~> ./a.out

or you can also use makefile.

Linked List

Here's a simple implementation of Singly linked list in C++ , which includes insertion , deletion and searching .

#include <cstdio>
#include <stdlib.h>
#include <iostream>
#include <limits>
#define BAD_INPUT_CUTOFF 3

using namespace std;


struct node
{
    int data;
    struct node* next;
};

struct searchDS
{
    int occurence;
    int posit[100];
};

typedef struct node Node;
typedef struct searchDS SD;

Node *start = NULL;
Node *new1;

void print_list(Node*);
int print_no();
int count();
unsigned int getIntInRange(unsigned int min, unsigned int max, const char *prompt);

Node* create_node()
{
    Node* newnode;

    newnode = (Node*)malloc(sizeof(struct node));

    printf("\nEnter the data (numeric only): ");
    scanf("%d", &newnode -> data);
    newnode -> next = NULL;

    return newnode;
}

int isEmpty()
{
    if(start == NULL)
    {
        printf("\nList is empty");
        return true;
    }
    else
        return false;
}

Node* search(int data)
{
    Node* ptr;

    int flag = 0;

    for(ptr = start ; ptr; ptr = ptr -> next)
    {
        if(ptr -> data == data)
        {
            flag = 1;
            printf("\nData %d found at %x ",data,ptr);
        }
    }

    if(flag == 1 )
    {
        return ptr;
    }
    else
    {
        printf("\nData %d not found !!!",data);
        return NULL;
    }
}

void adv_search(int data, SD* sp)
{

    Node *ptr,*prev;

    int i ,j, pos = 1;

    if(start ==  NULL)
    {
        printf("\nList is empty ");
        return;
    }
    sp->occurence = 0;

    for(i=0,ptr = start; (ptr); ptr = ptr->next,pos++)
    {
        if(ptr -> data == data)
        {
            (sp->occurence)++;
            sp->posit[i++] = pos ;
        }
    }

    if(sp->occurence == 0)
    {
        printf("\nData %d not in the list!!!",data);
        return;
    }
    printf("\nOcc: %d , Positions : ", sp->occurence);
    for(j=0; j<i; j++)
        printf("%d, ",sp->posit[j]);
    printf("\n");
}

void insert_beg()
{
//printf("\n In function %s\n",__func__);

    new1 = create_node();

    if(start == NULL)
    {
        start = new1;
        print_list(start);
        return;
    }
    else
    {
        new1 -> next = start ;
        start = new1;
        print_list(start);
        return;
    }
}
void insert_end()
{
    Node *ptr,*prev;
//printf("\n In function %s\n",__func__);

    new1 = create_node();

    if(start == NULL)
    {
        start = new1;
        print_list(start);
        return;
    }
    else
    {
        for(prev = start , ptr = start -> next ; ptr ; prev = ptr , ptr = ptr -> next);

        prev -> next = new1;
        print_list(start);
    }
}
void insert_at_pos()
{
    Node *ptr , *prev;
    int pos,i;
//printf("\n In function %s\n",__func__);

    new1 = create_node();

    printf("\nWhat position do you want to enter ? ");
    scanf("%d",&pos);

    if (pos < 1 || pos > print_no())
    {
        printf("\n Inserting failed! Out of bounds!!!");
        return;
    }
    else if(pos == 1)
    {
        new1 -> next = start;
        start = new1;
        print_list(start);
    }
    else if(pos > 1)
    {
        for(i = 1 ,prev = start, ptr = start -> next; (ptr) && (i < pos -1); prev = ptr , ptr = ptr->next,i++);
        prev -> next = new1 ;
        new1 -> next = ptr ;

        print_list(start);
    }
}

void delete_node_by_pos()
{
    Node *prev, *ptr, *temp;
    int pos,i;
    //printf("\n In function %s\n",__func__);

    if(isEmpty() != true)
    {
        printf("\nEnter the node no. you want to delete: ");
        scanf("%d",&pos);

        if (pos < 1 || pos > count())
        {
            printf("\n Deletion failed! Out of bounds!!!");
            return;
        }
        else if(pos == 1)
        {
            temp = start;
            start = start -> next;
            free(temp);
            print_list(start);
        }
        else if(pos > 1)
        {
            for(i = 1 ,prev = start, ptr = start -> next; (ptr) && (i < pos -1); prev = ptr , ptr = ptr->next,i++)
            {
                //`printf("\n prev-> data : %d\tptr->data :%d" ,prev-> data, ptr->data);
            }
            temp = ptr;
            prev -> next = ptr -> next;
            free(temp);
            print_list(start);
        }
    }
}

void delete_node_by_data()
{
    Node *ptr,*prev,*temp;
    int info, ch;
    SD sp;
    static int visited = 0;
    //printf("\n In function %s\n",__func__);

    if(isEmpty() != true)
    {
        printf("\nEnter the data you want to delete: ");
        scanf("%d",&info);
        adv_search(info, &sp);

        {
            if(start -> data == info )
            {
                temp = start;
                start = start -> next;
                free(temp);
                print_list(start);
                return;
            }
            for(prev = start , ptr = start -> next ; ptr ; prev = ptr , ptr = ptr -> next)
            {
                if( ptr -> data == info)
                {
                    temp = ptr;
                    prev -> next = ptr -> next;
                    free(temp);
                    print_list(start);
                    return;
                }
            }
        }
        print_list(start);
    }
}


void print_list(Node* start)
{
    Node *ptr;
//printf("\n In function %s\n",__func__);

    printf("\n");
    for(ptr = start; ptr ; ptr = ptr ->next )
    {
        printf("-> %d ",ptr->data);
    }
    printf("\n");
}
int print_no()
{
//printf("\n In function %s\n",__func__);
    printf("\nThe total no. of members in the list are : %d \n", count());
}

int count()
{

    Node *ptr;
    int count = 0;

    ptr = start ;
    while(ptr!=NULL)
    {
        ptr = ptr -> next;
        count++;
    }

    return count;
}

Node* reverse(Node* root)
{
    Node* ret_val;

    if ( root == NULL || root->next == NULL )
    {
        return root;
    }
    ret_val = reverse ( root -> next );

    root -> next->next = root;
    root->next = NULL;
    return ret_val;
}

unsigned int getIntInRange(unsigned int min, unsigned int max, 
                           const char *prompt)
{
    int input, //used to get input
        bad_count=0; //used to keep track of how many bad attempts.
    do
    {
        cout << prompt; //print out our prompt
        cin >> input; //get the input
        if (!cin.good() || input < min || input > max)
        {
            cout << "\nInvalid Input!" << std::endl;
            cin.clear(); //resets the state flag
            cin.ignore(numeric_limits<streamsize>::max(),'\n'); 
                        //clears out the buffer
            bad_count++; //User made a bad input, count it
            input = 0; // user did not enter a valid number
        }
    }
    while (input == 0 && bad_count < BAD_INPUT_CUTOFF);
    return input;
}

int main()
{
    int choice,searchKey,info;
    SD sp;
    Node* temp;
    while(1)
    {

        printf("\n1.Insert a node at beg\n2.Insert a node at end
                \n3.Insert a node at a given position\n4.Delete a 
                node by data\n5.Delete a node by position\n6.Print
                the list\n7.Print the no. of elements\n8.Reverse the 
                list\n9.Search \n10.Advanced Search\n11.Exit\n");

         choice  = getIntInRange(1,11,"\n Choose your option (1-11):\n");

        switch(choice)
        {
        case 1 :
            insert_beg();
            break;
        case 2 :
            insert_end();
            break;
        case 3 :
            insert_at_pos();
            break;
        case 4 :
            delete_node_by_data();
            break;
        case 5 :
            delete_node_by_pos();
            break;
        case 6 :
            print_list(start);
            break;
        case 7 :
            print_no();
            break;
        case 8 :
            start = reverse(start);
            print_list(start);
            break;
        case 9 :
            printf("\nEnter the data you want to search : ");
            scanf("%d",&searchKey);

            if(search(searchKey)!=NULL)
                printf("\nData %d at %x",searchKey , search(searchKey));

            break;
        case 10 :
            printf("\nEnter the data you want to search : ");
            scanf("%d",&searchKey);
            adv_search(searchKey,&sp);
            break;
        case 11 :
            exit(0);

        default :
            printf("\nInvalid input !!!\n");
            break;

        }
    }
}