Sunday, 5 April 2015

Double linked list example code in C++ using templates


Double linked list example code in Cpp using templates:

The below listed functions are used to manipulate the double linked list.

GetHeadNode: This function gets the head node from the list.
GetLastNode: This function gets the last node from the list.
GetCount (): This function gets the number of nodes in the list.
AddNode:This function adds the new node nto the list.
RemoveAt: This function remove the node at the given index.
GetAt:This function gets the node at the given index.
Destroy:This function destroys the entire list.


See the diagram that the double linked list is structures and


The below is the header file.
#ifndef _DOUBLE_LINKEDLIST_TEMPLATES_H_
#define _DOUBLE_LINKEDLIST_TEMPLATES_H_
template <class DoubleList>
class DoubleLinkedList_Templates{
private:
 struct stNode {
  stNode* pstPrevious;
  stNode* pstNext;
  DoubleList pstCurrent;
 };
 stNode* m_pcLast;  
 stNode* m_pcHead;
 int m_iListCount;    
public:
  DoubleLinkedList_Templates ();
 ~DoubleLinkedList_Templates ();
  DoubleList GetHeadNode ();
  DoubleList GetLastNode ();
 int GetCount ();


 void AddNode (DoubleList DoubleList);
 void RemAt (int iIndex);
 DoubleList GetAt (int iIndex);
 void Destroy ();
};
#endif //_DOUBLE_LINKEDLIST_TEMPLATES_H_

The below function is the default constructor of the class is used to initialize the member variables
template <class DoubleList>

DoubleLinkedList_Templates<DoubleList>::DoubleLinkedList_Templates ()

  { m_iListCount = -1;   m_pcLast = NULL;   m_pcHead = NULL; }

This function is used to destroy the instance of DoubleLinkedList_Templates<DoubleList> is called in order to free memory which was previously occupied by the dynamically allocated list items.
template <class DoubleList>
DoubleLinkedList_Templates<DoubleList>::~DoubleLinkedList_Templates ()
{
 if (m_iListCount > -1)
    { Destroy (); }
}

This function is used to Add the new node to the existing list. If the list is empty - In this case, the last and the first item of the list point to the same ocNewNode. If there is already at least one item in the list it is enough to reconnect the pointers between the (former) last, the first, and the newly added list item.


template <class DoubleList>
void DoubleLinkedList_Templates<DoubleList>::AddNode(DoubleList ocNewNode)
{
 stNode* pLItem = new stNode;
 pLItem->pstCurrent = ocNewNode;
 if (m_iListCount > -1) {
  pLItem->pstNext = m_pcHead;
  pLItem->pstPrevious = m_pcLast;
  m_pcLast->pstNext = pLItem;
  m_pcLast = pLItem;
  m_iListCount++;
 }
 else if (m_iListCount == -1){
  m_pcHead = pLItem;
  m_pcHead->pstNext = pLItem;
  m_pcHead->pstPrevious = pLItem;
  m_pcLast = pLItem;
  m_pcLast->pstNext = pLItem;
  m_pcLast->pstPrevious = pLItem;
  m_iListCount = 0;
 }
}

This function is used to Remove node from the given iIndex position in the list and decrements the count by 1

template <class DoubleList>
void DoubleLinkedList_Templates<DoubleList>::RemAt(int iIndex){
 if (iIndex < m_iListCount){
  stNode* pLItem = m_pcLast;
  for (int i = 0; i <= iIndex; i++){
   pLItem = pLItem->pstNext;
  }
  pLItem->pstPrevious->pstNext = pLItem->pstNext;
  pLItem->pstNext->pstPrevious = pLItem->pstPrevious;
  delete pLItem; pLItem = NULL;
  m_iListCount--;
 }
}

This function is used to get a DoubleList from a given iIndex position
In case that there is no DoubleList stored at the given iIndex of the List
this method will return a random value, or may lead to a Memory read exception.

template <class DoubleList>
DoubleList DoubleLinkedList_Templates<DoubleList>::GetAt (int iIndex)
{
 stNode* pLItem = m_pcHead;
 if (iIndex <= m_iListCount && iIndex > -1) {
  int i = 0;
  while (i < iIndex) {
   pLItem = pLItem->pstNext;
   i++;
  }
 }
 return pLItem->pstCurrent;
}

This fucntion is used to get the head node from the list
template <class DoubleList>

DoubleList DoubleLinkedList_Templates<DoubleList>::GetHeadNode ()

  { return m_pcHead->pstCurrent; }


This fucntion is used to get the tail item from the list
template <class DoubleList>

DoubleList DoubleLinkedList_Templates<DoubleList>::GetLastNode()

  { return m_pcLast->pstCurrent; }

This function is used to gets the number of ListItems in the List
template <class DoubleList>
int DoubleLinkedList_Templates<DoubleList>::GetCount ()
  {  return m_iListCount; }

This function is used to delete the content of the List.
template <class DoubleList>
void DoubleLinkedList_Templates<DoubleList>::Destroy ()
{
 stNode* pLItem = m_pcHead;
 while (m_iListCount > -1) {
  stNode* pstTEmp = pLItem;
  pLItem = pLItem->pstNext;
  delete pstTEmp;
  m_iListCount--;
 }
}


No comments: