4-Way LinkedList - CodeProject

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

}