A Better approach for creating, deleting linked lists

• Download demo project - 5.32 KB
• Download source - 1.34 KB

Introduction

This article provides a different way of creating linked lists and more complex data structures using double pointers to simplify readability and ease of use.

Explaining the method

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, and make your code more easily understood (if you are comfortable using double pointers). The idea behind this article can also be used to work with more complex data structures. The more complex your data structure is, the more benefit you will get from using the pp method.

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;
};

I - The Traditional way to add a node, AddNode(int nData)

First I will talk about creating a linked list. I will first present the traditional way that we all have learned at one time or another. Then I will present to you, the double pointer approach method, I call it the pp method, (pointer to a pointer).

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.

II - The new (PP) approach, NewAddNode(int nData)

bool CLinkedList::NewAddNode(int nData)
{
    // get the address of your linked list head
    CNode **ppNode = &m_pLinkedList;    
    while (*ppNode)
    // traverse by moving the address to the next pNext
        ppNode = &(*ppNode)->pNext;        
    
    // create the node right in the pNext, without worrying 
    // about your conventional two cases described above
    *ppNode = new CNode();    
    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, this means the code is more readable and 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 linked 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 to the head of the linked 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 relieves 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.

III - The Traditional way to delete a node, DeleteNode(int nData)

Now I will present to you the traditional way that we use to delete a node.

bool CLinkedList::DeleteNode(int nData)
{
    if (!m_pLinkedList)    // first case to check the list empty
        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 using 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.

IV - The New way to delete a node, NewDeleteNode(int nData)

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 pNext nodes
        if ((*ppNode)->nData == nData)    
        {
            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 linked 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 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 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 exits 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.

I hope you will benefit from this idea over here.

History

• Date Posted: April 18, 2003

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here