Better Method of Creating/Deleting Linked Lists Nodes

Environment: Any flavor of C++

Introduction


In this article I am going to present to you a better way to create and delete linked lists. The idea
involves using double pointers. This approach will make you use less code, which makes it more efficient,
more easily understood (if you are comfortable using double pointers). I am not sure whether this topic has
been approached before by other programmers, but so far I haven’t seen something like this on the web, nor
have I seen anyone of my fellow programmers using this method, so I thought of writing it, and letting more
people benefit from it. The idea behind this article can also be used to work with more complex data structures.

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

Here I’ll present both the traditional means of appending a node to a linked list (explaining the advantages and disadvantage)
and then I’ll introduce my method.

The Traditional Method

This is the traditional method that we all have learned at one time or another.


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


Now I will present to you the “double pointer approach” method that I call the pp method (pointer-to-pointer).


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

Now, I’ll present both the traditional means of deleting a node from a linked list (explaining
the advantages and disadvantage) and then I’ll introduce my method.

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


As you can see, the code is better, smaller, and easier to understand. Of course these ideas here
can be carried on to more complex data structures, trees for example. It will also make deletion and
addition in trees much easier and with less code. Using the pp method in more complex data structures
will reduce their complexity and enhance readability, make processing faster and smaller code.

I hope you will benefit from this idea over here.

Downloads

Download demo project – 5 Kb

Download source – 1 Kb

More by Author

Get the Free Newsletter!

Subscribe to Developer Insider for top news, trends & analysis

Must Read