Thursday, November 17, 2005

Data Structure Patterns

Teaching and books have a profound impact on how we think and solve problems.

In college when I learnt data structures, I was taught to embed the element in the data structure (list)


struct x {
struct x *next, *prev;
int element;
};


But I soon realized that I did not always want "int" as the type of the element, so I learnt the magical type void *

Here is another way to achieve the same thing


struct list {
struct list *next, *prev;
};

struct y {
int element;
struct list l;
};


This way, I could embed the list in anything without building any type information in list. Cool right?

If tomorrow I decided to use a tree, I could simply change


struct y {
int element;
struct tree t;
};


This way the impact on my code for "y" is minimal. In the traditional approach, I would have to use


struct tree xt {
int element;
struct tree *left, *right;
};


and redo most of the code.

The moral of the story

Embed the data structure in the data type and not the other way around





Figure illustrating the differences b/w embedding the data type in the data structure versus embedding the data structure in the data type
Post a Comment