Click here to Skip to main content
Click here to Skip to main content
Go to top

4-Way LinkedList

, 3 Nov 2008
Rate this:
Please Sign up or sign in to vote.
This linked list allows to connect a node with four adjacent nodes and shows how a node can be navigated in multiple directions.

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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Babu_Abdulsalam
Software Developer
India India
I'm working as Senior software Engineer since 7 years and interested in MFC and COM programming.

Comments and Discussions

 
Generalleft right previous right together are quite misleading Pinmemberf26-Nov-08 11:16 
GeneralRe: left right previous right together are quite misleading PinmemberManish K. Agarwal6-Nov-08 17:33 
GeneralRe: left right previous right together are quite misleading Pinmemberf26-Nov-08 17:52 
Generalnice one PinmemberInnowaze5-Nov-08 19:19 
Questiondatabase? PinmemberNGS 5496724-Nov-08 5:36 
AnswerRe: database? Pinmembersyed_babu4-Nov-08 22:11 
AnswerRe: database? PinmemberBryanWilkins17-Aug-10 6:07 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web04 | 2.8.140916.1 | Last Updated 3 Nov 2008
Article Copyright 2008 by Babu_Abdulsalam
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid