4-Way LinkedList

• Download source code - 18.7 KB

Introduction

This article describes how to a build a linked list which grows in multiple directions, and how to manipulate it without memory leak.

Background

I have read many articles explaining how to manage single and double linked lists. But, when I needed a linked list which grows in more than two directions, I couldn't find any. If you know the basics of linked list, you can go ahead with this article.

Using the code

I have generated a linked list CMultiLinkedList which will be used to simulate the structure of a tree control. So, the linked list will be used as the data storage and the tree control will be used to visualize the list. I have added the code to insert and delete nodes in the list. The way the list is deleted leaves you with zero memory leak. To create a linked list and to show it in a tree control, just specify the hierarchy in a text file with % as the delimiter, and once the file is imported, you will have the linked list and the tree.

/***************************************************************************
/DESCRIPTION:
/-----------
/            To delete all the linked nodes of a given node.
/            Given a node this function loop through using next pointer till the end
/            of the branch and delete all the linked nodes
/
/PARAM
/------
/        pNode[IN]    -    Node whose all the linked nodes to be deleted
/
/RESULT:
/-------
/        void
*/
void CMultiLinkedList::DeleteLinkedNodes(Node* pNode)
{
    for( ; pNode != NULL;  )
    {
        Node* delNode =  pNode;
        pNode      =  pNode->m_pNext;

        //If branch found i.e, if pNode has children delete all of them
        if( delNode->m_pRight )
            DeleteChildren(delNode->m_pRight );

        //If the node is start node in a branch,then move the next node of the pNode
        //as the start node of the branch
        if( delNode->m_pLeft )
        {
            //If the node is a start node in a branch and it has a sibling
            if( delNode->m_pNext )
            {
                delNode->m_pLeft->m_pRight = delNode->m_pNext;
                delNode->m_pNext->m_pLeft  = delNode->m_pLeft;
            
                if( delNode->m_pPrev )
                    delNode->m_pNext->m_pPrev = delNode->m_pPrev;
                else
                    delNode->m_pNext->m_pPrev = NULL;
            }
            else
                delNode->m_pLeft->m_pRight = NULL;
            
        }
        delete delNode;
        delNode = NULL;

                    
    }    
}
/***************************************************************************
/DESCRIPTION:
/-----------
/            To delete all the associated children of a given node
/
/PARAM
/------
/        pNode[IN]    -    Node whose children to be deleted
/
/RESULT:
/-------
/        void
*/
void CMultiLinkedList::DeleteChildren( Node* pNode,bool flag  )
{
    //If branch found i.e, if pNode has children delete all of them
    if( pNode->m_pRight )
    {
        DeleteChildren(pNode->m_pRight);     
    }

    //If the node is start node in a branch,then move the next node of the pNode
    //as the start node of the branch
    if( pNode->m_pLeft )
    {
        if( pNode->m_pNext )
        {
            pNode->m_pLeft->m_pRight = pNode->m_pNext;
            pNode->m_pNext->m_pLeft  = pNode->m_pLeft;
            
            if( pNode->m_pPrev )
            {
                pNode->m_pNext->m_pPrev  = pNode->m_pPrev;
                pNode->m_pPrev ->m_pNext = pNode->m_pNext;
            }
            else
                pNode->m_pNext->m_pPrev = NULL;
            
        }
        else
            pNode->m_pLeft->m_pRight = NULL;
    }
    if( pNode->m_pRight )
    {
        DeleteChildren(pNode->m_pRight);     
    }

    //Delete all the linked nodes of the pNode
    DeleteLinkedNodes( pNode );

}

Points of Interest

It was quite interesting to create the linked list which grows in four directions, and the way the list is deleted is really good.

History

This is the first version of the code, and it might have bugs and issues. Based on feedback from users, I'll be fixing them and updating the code.