Better Method of Creating/Deleting Linked Lists Nodes

Introduction

Before I begin I will present to you the structure CNode that will constitute the nodes of the linked list, and the class CLinkedList which uses CNode to implement a linked list.

struct CNode
{
 CNode *pNext;
 int   nData;
 CNode() { pNext = NULL; }
};

class CLinkedList
{
public:	
 CLinkedList();
 ~CLinkedList();

 bool AddNode(int nData);
 bool NewAddNode(int nData);
 bool DeleteNode(int nData);
 bool NewDeleteNode(int nData);

protected:
 CNode *m_pLinkedList;
};

Creating Linked Lists Nodes

The Traditional Method

bool CLinkedList::AddNode(int nData)
{
 // first case, when the head of the linked list is Null
 if (!m_pLinkedList) 
 {
  m_pLinkedList = new CNode;
  
  if (!m_pLinkedList)
   return false;

  // work with your newly created node
  m_pLinkedList->nData = nData;
   return true;
 }

 // second case, where you search for the first pNext
 CNode *pNode = m_pLinkedList; 
 
 // that is Null to fill it in.
 while (pNode->pNext)
  pNode = pNode->pNext;

 // you have to create your linked list in the pNext variable
 pNode->pNext = new CNode;

 if (!pNode->pNext)
  return false;

 // this step is to go to the actual node to work with it
 pNode = pNode->pNext;		

 // work with your newly created node
 pNode->nData = nData;

 return true;
}

The traditional AddNode way can be divided into 2 logical cases.

The first case begins by checking if the pointer to the linked list is NULL. If so then it creates a new node in it and fills it with the appropriate data and then return true, indicating a successful creation.

The second case is when the pointer to the head of the linked list is not empty, In this case, there is at least one node allocated in the linked list. So we allocate a new pointer and set it to the current linked list and then we traverse it in terms of the pNext pointer always, because we need to get to the first NULL pNext pointer. Then we create a new node in the next pointer and then we advance our pointer to its pNext that we have already created. Now we fill the data normally like we did in the first case, notice here that the code that fills our newly created node is redundant. One time in the first case when we create the head of the linked list, and the other in the second case just presented.

The Pointer-to-Pointer Method

bool CLinkedList::NewAddNode(int nData)
{
 // get the address of your linked list head
 CNode **ppNode = &m_pLinkedList; 
 
 // traverse by moving the address to the next             
 while (*ppNode)
  ppNode = &(*ppNode)->pNext;        
 
 // pNext
 // create the node right in the pNext, without worrying 
 *ppNode = new CNode();		
 
 // about your conventional two cases described above
 if (!*ppNode)
  return false;

 // work with your newly created node, without the conventional 
 // step of going to the pNext pointer, and your write this code once
 (*ppNode)->nData = nData;

 return true;
}

Look at this code. The first thing you'll notice is the code being smaller, off course naturally this means better. Let's take a closer look. We allocate a new pointer to a pointer of type CNode ppNode (by allocate I mean on the stack). Then we use this to take the address of the head of the link list. By doing this we get rid of the two cases that we use in the conventional way because now we really don't care where ppNode is pointing to, if it is the head of the link list or some other node. We traverse to the first NULL pNode, and not the pNext. In the traditional case we have to traverse in terms of the pNext, because we need to create the new node in it, or else we will not be able to connect the linked list, but by using a double pointer, this problem is eliminated. The first NULL node that we hit could be the head of the linked list itself or some other node, again the pointer to a pointer feature relives us from worrying about this point. Now we create our new node directly in the ppNode, instead of the next and we use it directly instead of moving to the pNext Node that we create, in the traditional case. And we write the code of filling the new node, once. Smaller code, easier to understand, and off course more efficient.

Deleting Nodes from a Linked List

The Traditional Method

bool CLinkedList::DeleteNode(int nData)
{
 // first case to check the list empty
 if (!m_pLinkedList)	
  return false;

 // second case to check for the deleted node if it is the head
 if (m_pLinkedList->nData == nData)	     
 {
  // you need to hold on to your pNext
  CNode *pConnectAgain = m_pLinkedList->pNext;	
  delete m_pLinkedList;
 
  // you need to connect it again.
  m_pLinkedList = pConnectAgain;			
 
  return true;
 }

 CNode *pNode = m_pLinkedList;

 // third case, your traversing would always be in terms of the pNext
 while (pNode->pNext)	
 {
  // your checking would be in terms of the pNext
  if (pNode->pNext->nData == nData)	  
  {
   CNode *pDeleteNode = pNode->pNext;

   // alot of pNext pointers, don't you think ?
   pNode->pNext = pNode->pNext->pNext;	
   delete pDeleteNode;

   return true;
  }

  pNode = pNode->pNext;
 }

 return false;
}

The traditional DeleteNode can be divided into three logical cases.

First of all we need to make sure that the linked list has at least one node allocated in it, if not then return false. The second case is when we need to check for the node that we want to delete if it is the head of the linked list. This is kind of a special case because we need to update the value of the pointer to the head of the linked list directly. If our node to delete is the head, then we hold on to the pNext and then we delete the head and then update the value of the m_pLinkedList with the Temporary value pConnectAgain that we kept, and we return true.

The third case is when our node to delete is not the head of our linked list, it might be one of the connected nodes or it might not be in our list at all. So allocate a pointer pNode (by allocate I mean on the stack, a variable and not 'new'). We use it to traverse the linked list, again in terms of the pNext and not the node itself. Once we hit our node to delete, we keep a pointer to it pDeleteNode and then we update the pNext by the pNext of the pNext, not very nice, I would say. Then we delete our pDeleteNode and return true. If we pass our while loop, this means we couldn't find our node to delete so we return false.

A Better Method of Deleting Nodes From a Linked List

bool CLinkedList::NewDeleteNode(int nData)
{
 // get the address of your linked list head
 CNode **ppNode = &m_pLinkedList;	
 
 while (*ppNode)
 {
  // you work with your current node and not confusing     
  if ((*ppNode)->nData == nData)	
  
  // pNext nodes
  {
   CNode *pDeleteNode = (*ppNode);
   
   // you don't need to work with pNext->pNext
   (*ppNode) = (*ppNode)->pNext;	
   delete pDeleteNode;
   
   return true;
  }
  ppNode = &((*ppNode)->pNext);
 }
 
 // you have only one case here, compared with conventional 3 cases 
 // for the normal linked list delete !
 return false;
}

Look at this code, if you remove the comments you will end up with 13 lines compared with 22 lines of the conventional way. (counting the lines having the braces)

You have just one case here. You do not need to check for the head of the link list being empty. You do not have to treat the head of the linked list as a special case. And you always work with the node itself and not in it's pNext.

The code starts by getting the address of the pointer of the head of the list. Next we use this pointer to traverse the list and find our data. If our linked list is empty, we will not enter the while loop and we will go to the end of the function where we return false (no special case like case 1 in the traditional way). If we find the node to delete, then we keep a pointer to it, pDeleteNode. Then we advance the our pointer to its pNext, (no two level pNext->pNext like the conventional way). We delete the node we want, pDeleteNode, and we return true. If the while loop exists then we didn't find our node to delete so we return false.

Conclusion

I hope you will benefit from this idea over here.

Downloads