Click here to Skip to main content
65,938 articles
CodeProject is changing. Read more.
Articles / Languages / eVC4.0

Dynamic Linked List Tree

1.07/5 (21 votes)
18 Feb 20074 min read 1  
Using Vector and double linked list to create trees

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.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here