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.
void CMultiLinkedList::DeleteLinkedNodes(Node* pNode)
{
for( ; pNode != NULL; )
{
Node* delNode = pNode;
pNode = pNode->m_pNext;
if( delNode->m_pRight )
DeleteChildren(delNode->m_pRight );
if( delNode->m_pLeft )
{
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;
}
}
void CMultiLinkedList::DeleteChildren( Node* pNode,bool flag )
{
if( pNode->m_pRight )
{
DeleteChildren(pNode->m_pRight);
}
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);
}
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.