Search This Blog

Sunday, February 11, 2007

Dynamic Linked List Tree

if you want to see the Artical in better view


            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


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




            // don't forget to deallcate the memory






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)


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

CurrentInstanceChild1.Parent = &CurrentInstance;


//same as CurrentInstanceChild1


//same as CurrentInstanceChild1

CurrentInstanceChild2.Parent = &CurrentInstance;


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



CurrentInstanceChild1_1.Parent = &CurrentInstance;



CurrentInstanceChild2_1.Parent = &CurrentInstanceChild2;


CurrentInstanceChild2_2.Parent = &CurrentInstanceChild2;


CurrentInstanceChild2_3.Parent = &CurrentInstanceChild2;



CurrentInstanceChild2_2_1.Parent = &CurrentInstanceChild2_2;



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




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: