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


Comments

  • HYmlnb hh FI HHk eJbl Wy

    Posted by VYoIofereZ on 04/29/2013 09:07pm

    tramadol online order tramadol online with cod - tramadol kidney

    Reply
  • help

    Posted by Legacy on 07/05/2002 12:00am

    Originally posted by: sons of liberty

    "keep a list of "deleted" nodes without actually destroying them. Then when you create a new node, check the unused-node list first, and only create one if you have none just hanging around waiting to be used. "

    Can anyone provide me with a concrete example that would explain the above quote?

    Thanks a lot

    Reply
  • If you want to add in tail in a list

    Posted by Legacy on 04/03/2002 12:00am

    Originally posted by: silverstar

    //If you want to keep the head of the list and add nodes to //the tail just create a LastNode 
    
    Node_t Head
    Node_t* LastNode
    //the Head and LastNode are global variables
    LastNode = &Head
    LastNode->pNext= NULL
    //for inserting the NewNode in list
    insert(Node_t* NewNode)
    {
    LastNode->pNext=NewNode;
    LastNode=LastNode->pNext;
    LastNode->pNext = NULL
    }
    //this is useful when you use the list in other part of the //program

    Reply
  • copy constructor?

    Posted by Legacy on 01/28/2002 12:00am

    Originally posted by: magneto

    Could some show the best way to implement a copy constructor for the linked list? Thanks.

    Reply
  • Not a good idea

    Posted by Legacy on 08/31/2001 12:00am

    Originally posted by: andi payn

    All you're doing is wrapping the test for null (no nodes
    
    yet) and the test for empty (last node in the list) up in
    one place. This is similar to the following trick:

    int big_strlen(const char* sz)
    {
    if (!sz)
    return 0;
    int i = 0;
    while (*sz++)
    ++i;
    return i;
    }

    int spiffy_strlen(const char* sz)
    {
    int i = 0;
    while (sz && *sz++)
    ++i;
    return i;
    }

    I reduced the line count by 50%, so it must be better,
    right?

    Wrong. I also added in a check for null at every step
    through the loop. Instead of one comparison, there's now
    two, so it now takes 4/3 as long (mileage may vary
    depending on CPU, compiler, and optimizer, but you get the
    idea).

    Worse yet, many optimizers can recognize a loop like that
    in the first one, but won't recognize the second version,
    so it may hurt efficiency even more.

    Similarly, your code does an extra dereference at each step
    in the loop (as well as various other places). In other
    words, (*ppNode)->pNext takes a dereference, an add, and
    another dereference, so your code takes 3/2 as long.

    Is it worth saving a few lines of typing (especially code
    that you should just type once, in a library, and then
    reuse again and again) if it makes the program run that
    much slower?

    Reply
  • Very Silly

    Posted by Legacy on 08/12/2001 12:00am

    Originally posted by: Kenneth Kasajian

    Someone should check this stuff before it gets posted on this web site.

    What the heck is this code supposed to be for?

    I have *never* heard of walking the *entire* linked list to add an item to it. I am very surprised that anyone would do that. There is nothing traditional about this method. You just never do that. Think about it! You are walking the entire list to add an item. How silly is that? To add an item, you simply point the head to the new item and point to new item's next pointer to the original head item. Dah!

    Second, what's this about there not being a doubly-linked list anywhere on the net? What about the one that comes with C++? It's in a header file called list. You include it by typing:

    #include <list>

    And it's automatically doubly-linked, which means you can walk backwards of forward.

    Now, give me a good template that of an efficient singly-linked list (not not the SGI stuff), and I'm all ears.

    Reply
  • For optimizing speed

    Posted by Legacy on 06/25/2001 12:00am

    Originally posted by: Alok Govil

    Firstly, I must say that this is a very good job.
    I have been trying to write linked-list code that "looked" good, but have never been able to.

    All coding champions should ignore what follows, you know it already.

    When adding a node, do not have to parse the list to get to the end:

    while (p->next != NULL)
    {
    p = p->next;
    };

    Rather, just add nodes to the start of the list:

    temp = p_first_node;
    p_first_node = new class_name;
    p_first_node->data = data_you_provided;
    p_first_node->next = temp; //Add to the beginning
    //and forget temp

    Or alternatively, just keep a pointer to the end of the list also.

    This also easily and speedily lets you create a list of deleted nodes, deleted but not purged for future additions.
    Thought the just impoverished the code above might not work, the idea works very well.

    Reply
  • Better Method of Creating/Deleting Linked Lists Nodes

    Posted by Legacy on 05/25/2001 12:00am

    Originally posted by: Alex Russell

    A more tradidional way to eliminate the extra check for a NULL list is to have a header node that is never deleted, and doesn't hold any data. For doubley-linked lists you have a dummy head and tail node. Doing this simplifies all your add/delete code by guarnteeing that the list is never empty.
    
    

    typedef struct node
    {
    data_t data;
    struct node *next;
    }
    node_t;

    // global head
    node_t head;

    add(node_t *n)
    {
    node_t *tn;

    tn=&head;
    while ( tn->next )
    tn=tn->next;

    tn->next=n;

    }

    Reply
  • Checker boarding Ram?

    Posted by Legacy on 04/18/2001 12:00am

    Originally posted by: OutsideTheBox

    If your program constantly adds and deletes nodes then you may find that system performance is degraded. I am not certain about why, but i believe it could be related to checker boarding. It may be more efficient to keep a list of "deleted" nodes without actually destroying them. Then when you create a new node, check the unused-node list first, and only create one if you have none just hanging around waiting to be used.

    I have implemented something similar to this and it suited my needs. Your program requirements should be considered before just arbitrarily adding that level of complexity. My requirements justified creating a class to handle linked lists.

    Linked lists are like folks from Georgia, They're fun to be around once you get to know them.

    Reply
  • Adding and deleting nodes in linked lists

    Posted by Legacy on 03/17/2001 12:00am

    Originally posted by: Chris Keith

    Do you know of a good way to sort a linked list?

    Thanks,
    Chris

    Reply
Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • Live Event Date: August 20, 2014 @ 1:00 p.m. ET / 10:00 a.m. PT When you look at natural user interfaces as a developer, it isn't just fun and games. There are some very serious, real-world usage models of how things can help make the world a better place – things like Intel® RealSense™ technology. Check out this upcoming eSeminar and join the panel of experts, both from inside and outside of Intel, as they discuss how natural user interfaces will likely be getting adopted in a wide variety …

  • Live Event Date: August 14, 2014 @ 2:00 p.m. ET / 11:00 a.m. PT Data protection has long been considered "overhead" by many organizations in the past, many chalking it up to an insurance policy or an extended warranty you may never use. The realities of today makes data protection a must-have, as we live in a data-driven society -- the digital assets we create, share, and collaborate with others on must be managed and protected for many purposes. Check out this upcoming eSeminar and join Seagate Cloud …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds