Search This Blog

Sunday, February 11, 2007

Dynamic Linked List Tree

if you want to see the Artical in better view
http://www.codeproject.com/useritems/externalmenuArgument.asp



Introduction


            First of all I want to thank you for your passion to learn new things, now lets move on for what I am going to tell you, The idea of Linked List Tree is so simple I assume that you have some knowledge about what is linked list.


 What is Linked List Tree?


-          it's some how new concept to speed up dealing with the data which require nested data types and information like family tree and things like that, this idea of Linked List Tree based on the Double linked list, as we know that linked list is a data type that contain a pointer with same type, here is code which I explain what I mean


 


struct DoubleLinkList


{


/* this is pointer of the same data type which will point to the      


   Previous object(instance) for this Type */


      DoubleLinkList *Previous;


     


      wchar_t UserName[50];


 


/* this is pointer of the same data type which will point to the Next


   object(instance) for this Type */


      DoubleLinkList *Next;


}


 


Now let's explain what Linked List Tree, in figure 1, it shows that each instance (object) of the data type will point to more than element, as you can see in the figure each element has a path "?-?-?", for Example let's see the element path "1-3-2" you will notice that this instance is linked with it's parent "1-3" which is related to object instance path "1", now I think it's theoretically clear , it's like double linked list except that it has more than childes, I think we need little peace of code to explain this.


 


 


 



Figure 1


 


 


How to write code that supports Tree Linked List?


The answer is Array of pointers to childes and pointer to parent, and here is the code which explain what I am talking about


 


struct TreeLinkedList


{


      /*    This pointer has the same data type which


            will point to the parent instance of this


            same data type */


      TreeLinkedList* Parent;


     


      wchar_t UserName[50];


     


      /*    Here is the most important part of the


            whole idea, it's an array of poiters


            that will point to the child instances


            of the same data type*/


      std::vector<TreeLinkedList*> Childes;


      // I used vector (one of standard tamplate library)


      // you can find nice articals about it in CodeProject.com


     


      // some how there is problems with WTL and STD so if you


      // don't like or can't use the STD vector, you can do it as


      // structred data type (I mean by that adding some functions


      // that will manage adding new pointers to child pointers array )


     


      ~TreeLinkedList()


      {


            // don't forget to deallcate the memory


            Childes.empty();


      }


};


 


 


How to use what I just wrote?


 


// here we did some instance of our TreeLinkedList Data type


// you can understand from the varible names the hirarchy


// of the tree


TreeLinkedList CurrentInstance;


TreeLinkedList CurrentInstanceChild1;


TreeLinkedList CurrentInstanceChild1_1;


TreeLinkedList CurrentInstanceChild2;


TreeLinkedList CurrentInstanceChild2_1;


TreeLinkedList CurrentInstanceChild2_2;


TreeLinkedList CurrentInstanceChild2_2_1;


TreeLinkedList CurrentInstanceChild2_3;


TreeLinkedList CurrentInstanceChild2_3_1;


 


// Frist assign the root instance pointer to NULL to guarantee that


// this instance is a parent


CurrentInstance.Parent = 0;


// Add the root childs using the vector templat class member (push_back)


CurrentInstance.Childes.push_back(&CurrentInstanceChild1);


// Assgin the parent pointer to this instance of data type


CurrentInstanceChild1.Parent = &CurrentInstance;


 


//same as CurrentInstanceChild1


CurrentInstance.Childes.push_back(&CurrentInstanceChild2);


//same as CurrentInstanceChild1


CurrentInstanceChild2.Parent = &CurrentInstance;


 


// after that you are going to assgin the childs tree and parent pointer


 


CurrentInstanceChild1.Childes.push_back(&CurrentInstanceChild1_1);


CurrentInstanceChild1_1.Parent = &CurrentInstance;


 


CurrentInstanceChild2.Childes.push_back(&CurrentInstanceChild2_1);


CurrentInstanceChild2_1.Parent = &CurrentInstanceChild2;


CurrentInstanceChild2.Childes.push_back(&CurrentInstanceChild2_2);


CurrentInstanceChild2_2.Parent = &CurrentInstanceChild2;


CurrentInstanceChild2.Childes.push_back(&CurrentInstanceChild2_3);


CurrentInstanceChild2_3.Parent = &CurrentInstanceChild2;


 


CurrentInstanceChild2_2.Childes.push_back(&CurrentInstanceChild2_2_1);


CurrentInstanceChild2_2_1.Parent = &CurrentInstanceChild2_2;


 


CurrentInstanceChild2_3.Childes.push_back(&CurrentInstanceChild2_3_1);


CurrentInstanceChild2_3_1.Parent = &CurrentInstanceChild2_3;


 


I think the sample is so clear, but how can we fetch the data the UserName from the  CurrentInstanceChild2_3_1 Instance, simply you will treat it like array of pointer and here it is how to get the UserName for the targeted instance


 


CurrentInstance.Childes[0]->Childes[1]->Childes[2]->Childes[1]->UserName;


 


Someone may think that is may be useless to do something like that , we are still writing a lot of code to add and fetch the data, in this case I will tell you that this theory is used for dynamic trees, or you have to wait until it's need appear.


 


Now really thanks for your time which you spend in reading what I wrote.

No comments: