Sunday, 5 April 2015

Linked list implementation using Templates in C++

Linked list implementation using Templates in Cpp:

Working example for different operations on the linked list using the templates. The below is the header file of the linked list contains below list of functions

Insert: this function is used to add the new node into the list.
Delete: this function is used to delete the requested node from the linked list
Search: this function is used to search the node requested node from the linked list
Reverse. This function is used to reverse the linked list.

Sort: This function is used to sort the list using merge merge sort algorithm
Merge: This function is used to merge the sorted nodes in the list.

#ifndef _LINKEDLIST_TEMPLATES_H_
#define _LINKEDLIST_TEMPLATES_H_
template <class TemplateClass>
struct stNode {
  TemplateClass TData;
  stNode * stNext;
};
template <class TemplateClass>
class LinkedList_Templates
{
public:
  LinkedList_Templates (void);
  virtual ~LinkedList_Templates (void);
 
/* this fucntion is used to insert the new node into the existing list */
  bool Insert (TemplateClass TData);
 
/* this function is used to delete the requested node from the linked list */
  bool Delete (TemplateClass TData);

  /* this fucntion is used to search the node requested node from the linked list */
  stNode<TemplateClass> * Search (TemplateClass TData);
 
/* This function is used to dump the data from the linked list */
  void Dump ();

  /* This fucntion is used to reverse the linked list */
  void Reverse ();
 
/* This fucntion is used to sort the list using merge merge sort algorithm */
  void Sort ();

private:
  stNode<TemplateClass> * m_pcHeadNode;
  int m_iLength;

  /* this fucntion is used to destroy the allocated memory for the linked list.
     This function should be called in the destructor of the class */
  void Destroy ();

  /* This function is used to implement the sort algorithm */
  stNode<TemplateClass>* Sort (stNode<TemplateClass> * m_pcHeadNode, int iLength);

  /* This function is used to merge the sorted nodes in the list */
  stNode<TemplateClass>* Merge (stNode<TemplateClass>* pcLeftNode, int iLCnt,      stNode<TemplateClass>* pcRightNode, int iRCnt);

  /* This function is used to dump the list */
  void Dump (stNode<TemplateClass> * pcTempNode);
#endif // _LINKEDLIST_TEMPLATES_H_

This is the constructor of the class used to intialize all the local variables of the class
template <class TemplateClass>
LinkedList_Templates<TemplateClass>::LinkedList_Templates (void) :  m_pcHeadNode (NULL), m_iLength (0)

  { }

This is the destructor of the class used to destroy the allocated memory for the linked list
template <class TemplateClass>

LinkedList_Templates<TemplateClass>::~LinkedList_Templates (void)

  { Destroy (); }

Function for inserting the node
template <class TemplateClass>
bool LinkedList_Templates<TemplateClass>::Insert (TemplateClass TData)
{
  try {
    stNode<TemplateClass> * pcTempNode = new stNode<TemplateClass>();
    pcTempNode->TData = TData;
    pcTempNode->stNext = m_pcHeadNode;
    m_pcHeadNode = pcTempNode;
    ++m_iLength;
    return true;
  }
  catch(std::exception & ex)
    { return false; }
}

Function for deleting the node, here it will searches the required node is presented in the list or not till the end. And it decrements the count by one
template <class TemplateClass>
bool LinkedList_Templates<TemplateClass>::Delete (TemplateClass TData)
{
  stNode<TemplateClass> *pcCurrentNode = m_pcHeadNode, *prev = NULL;
  while (pcCurrentNode) {
    if (pcCurrentNode->TData == TData)
      { break; }
    prev = pcCurrentNode;
    pcCurrentNode = pcCurrentNode->stNext;
  }
  if (pcCurrentNode) {
    if (prev)
      { prev->stNext = pcCurrentNode->stNext; }
    else
      { m_pcHeadNode = pcCurrentNode->stNext; }
    delete(pcCurrentNode); pcCurrentNode = NULL;
    --m_iLength;
    return true;
  }
  else
    { return false; }
}

This function searches the required node till the list end
template <class TemplateClass>
stNode<TemplateClass> * LinkedList_Templates<TemplateClass>::Search (TemplateClass TData)
{
  stNode<TemplateClass> * pcTempNode = m_pcHeadNode;
  while (pcTempNode) {
    if (pcTempNode->TData == TData)
      { return pcTempNode;  }
    pcTempNode = pcTempNode->stNext;
  }
  return NULL;
}

This is simple function to print the list
template <class TemplateClass>
void LinkedList_Templates<TemplateClass>::Dump (stNode<TemplateClass> * pcTempNode)
{
  bool printNewLine = (pcTempNode) ? true : false;
  while (pcTempNode) {
    std::cout << pcTempNode->TData << ",";
    pcTempNode = pcTempNode->stNext;
  }
  if (printNewLine)
    { std::cout << std::endl; }
}
template <class TemplateClass>
void LinkedList_Templates<TemplateClass>::Dump ()
{
  stNode<TemplateClass> * pcTempNode = m_pcHeadNode;
  bool printNewLine = (pcTempNode) ? true : false;
  while (pcTempNode) {
    std::cout << pcTempNode->TData << "|";
    pcTempNode = pcTempNode->stNext;
  }
  if (printNewLine)
    { std::cout << std::endl; }
}

This function destroys the allocated list of node while the object scope goes out, This function should be called in the destructor of the class
template <class TemplateClass>
void LinkedList_Templates<TemplateClass>::Destroy ()
{
  stNode<TemplateClass> * pcTempNode = NULL;
  while (m_pcHeadNode) {
    pcTempNode = m_pcHeadNode;
    m_pcHeadNode = m_pcHeadNode->stNext;
    //std::cout << "deleting TData " << pcTempNode->TData << std::endl;
    delete (pcTempNode); pcTempNode = NULL;
  }
}

This function reverses the list, the last node in the first and soon till the first node is at the end.
template <class TemplateClass>
void LinkedList_Templates<TemplateClass>::Reverse ()
{
  stNode<TemplateClass> *pcCurrentNode = m_pcHeadNode, *prev = m_pcHeadNode, *save = NULL;
  while (pcCurrentNode) {
    save = pcCurrentNode->stNext;
    pcCurrentNode->stNext = prev;
    prev = pcCurrentNode;
    pcCurrentNode = save;
  }
  m_pcHeadNode->stNext = NULL; m_pcHeadNode = prev;
}

This function uses merge sort to sort the linked list
template <class TemplateClass>
void LinkedList_Templates<TemplateClass>::Sort ()
  { m_pcHeadNode = Sort(m_pcHeadNode, m_iLength); }
/* use merge sort to sort the linked list */
template <class TemplateClass>
stNode<TemplateClass>* LinkedList_Templates<TemplateClass>::Sort (stNode<TemplateClass> * pcHead, int iLength)
{
  if (iLength < 1)
    { return pcHead; }
  if (iLength < 2)
    { pcHead->stNext = NULL; return pcHead;}
  stNode<TemplateClass> * pcCurrentNode = pcHead;
  int iCount = iLength/2;
  while (iCount--)
    { pcCurrentNode = pcCurrentNode->stNext; }
  iCount = iLength / 2;
  pcHead = Sort (pcHead, iCount);
  pcCurrentNode = Sort (pcCurrentNode, iLength - iCount);
  return Merge (pcHead, iCount, pcCurrentNode, iLength - iCount);
}


This function merges the sorted list
template <class TemplateClass>
stNode<TemplateClass>* LinkedList_Templates<TemplateClass>::Merge (stNode<TemplateClass>* pcLeftNode, int iLCnt, stNode<TemplateClass>* pcRightNode, int iRCnt)
{
  stNode<TemplateClass> * pcTempNode1= new stNode<TemplateClass> ();
  pcTempNode1->stNext = NULL;
  stNode<TemplateClass> * pcTempNode = pcTempNode1;
  while (iLCnt > 0 && iRCnt > 0) {   
    if (pcLeftNode->TData < pcRightNode->TData) {
      pcTempNode->stNext = pcLeftNode;
      pcTempNode = pcTempNode->stNext;
      pcLeftNode = pcLeftNode->stNext;
      --iLCnt;
    }
    else if (pcRightNode->TData < pcLeftNode->TData) {
      pcTempNode->stNext = pcRightNode;
      pcTempNode = pcTempNode->stNext;
      pcRightNode = pcRightNode->stNext;
      --iRCnt;
    }
    else {
      pcTempNode->stNext = pcLeftNode;
      pcTempNode = pcTempNode->stNext;
      pcLeftNode = pcLeftNode->stNext;
      --iLCnt;
      pcTempNode->stNext = pcRightNode;
      pcTempNode = pcTempNode->stNext;
      pcRightNode = pcRightNode->stNext;
      --iRCnt;
    }
  }
  while (iLCnt > 0) {
    pcTempNode->stNext = pcLeftNode;
    pcTempNode = pcTempNode->stNext;
    pcLeftNode = pcLeftNode->stNext;
    --iLCnt;
  }
  while (iRCnt > 0) {
    pcTempNode->stNext = pcRightNode;
    pcTempNode = pcTempNode->stNext;
    pcRightNode = pcRightNode->stNext;
    --iRCnt;
  }
  pcTempNode = pcTempNode1;
  pcTempNode1 = pcTempNode1->stNext;
  delete (pcTempNode); pcTempNode = NULL;
  return pcTempNode1;
}

Testing the above class in the main
#include "stdafx.h" 
#include <iostream>
using namespace std;
#include "LinkedList_Templates.h"
int main ()
{
  LinkedList_Templates<int> ocList;
  ocList.Insert (13);
  ocList.Insert (67);
  ocList.Insert (8);
  ocList.Insert (9);
  ocList.Insert (63);
  ocList.Dump ();
  ocList.Reverse ();
  ocList.Dump ();
  ocList.Sort ();
  ocList.Dump ();
  ocList.Delete (3);
  ocList.Delete (3);
  ocList.Delete (4);
  ocList.Dump ();
  ocList.Reverse ();
  ocList.Dump ();
  ocList.Sort ();
  ocList.Dump ();
  if (ocList.Search (13))
   { std::cout << "13 found \n"; }
  if (!ocList.Search (5))
    { std::cout << "5 not found \n"; }
  getchar ();
  return 0;
}

The output of the above program is
 63|9|8|67|13|

13|67|8|9|63|

8|9|13|63|67|

8|9|13|63|67|

67|63|13|9|8|

8|9|13|63|67|

13 found

5 not found


No comments: