Data Structures - Some meta knowledge worth having

A sound knowledge of Data structures and Algorithms is necessary to have a good career in software development. At least , there was a time when this belief was very much in the mainstream. With the advent of Standard data structure libraries and Open source libraries, people are able to write applications without hearing about the term Data structures.

The natural question one can ask now is ..."we have got collection classes in java , C# and C++ [STL,it's container]. why one should know about data structures ?". The question is a valid one. if your into application software development , one can be perfectly happy with vector , map and other classes available with these libraries. But, there are cases where we might have to create hybrid data structures to solve a problem @ hand.

The first classical data structure , we come across is some thing called a Linked List. This is also called Linked Linear List.There was a time when most programming languages had a restriction that the number of array elements in a language has to be declared at the compile time. Then creation of a Linked list was the only option available for the developer to have a dynamically sizable data structure. The Linked list data structure has got variations like Double linked list , Circular Linked list etc. The wiki entry for the Linked list cann be found

http://en.wikipedia.org/wiki/Linked_list



The next most investigated data structure is a tree. A tree is a data structure which has got a left node and a right node. The left node will always contain a value which is lexicographically smaller than the node and the right will have a bigger value than the current node. Tree is a recursive data structure. we can consider each node a sub tree. The traversal algorithm for a tree can be written very easily using recursion. Most standard data structure books show u how to insert , search and traverse trees. Some of them leave delete as an excersise to the reader. The tree can quickly degenerate into a list , if it gets only value which is greater or small than the root node. Then researchers brought in tree balancing heuristics to the table. There are trees like AVL , Red black trees which does a good
job rebalancing the tree once we have inserted the elements. The MAP collection classes in most languages are implemented using Red black trees. Once we have got an intuitive appreciation of trees , one can sneak in. The wiki entry for Tree can be located @

http://en.wikipedia.org/wiki/Tree_%28data_structure%29


The other data structure which are of great importance are STACKS and QUEUES. STACK is some time called Push down stack. The stack is LIFO (Last in first out ) model.
STACK is a data structure commonly used for evaluating expressions , remebering the traversal path in a tree or graph etc. Recursive routines which implicitly uses processor stack can be converted into an iterative one by a software stack (data structure). Queues are data structures where we read data from the front and write the data in the rear. Queues are also called Circular Queues.
The wiki page for Queue and stack is located @
http://en.wikipedia.org/wiki/Stack_(data_structure)
http://en.wikipedia.org/wiki/Queue_(data_structure)


The title of king of data structures will probably go to the GRAPH data structure. A literature which will take a person's life time to read has been written about it. We are concerned mostly about the algorithmic graph theory. How graphs can be realized on a computer to efficiently process it will be our primary concern. Tree is a specialized case of a Graph where there are no cycles in the graph. So, GRAPH can be considered as a super structure.

http://en.wikipedia.org/wiki/Graph_(data_structure)

The knowledge of List , Tree , Stack,Queue and Graph with it's associated algorithms will make u a better programmer. Armed with this knowlege , u can choose the collection class for the occasion with confidence.

There are some domain specific data structures like QuadTree ( Computational Geometry ), Octree ( Color reduction Algorithms ) , BSP ( Binary space partition tree - for visibility ordering ), Winged Edge Data structures ( Solid modelling ) , R-trees ( for spatial layout ) and others , which one can tackle armed with the knowledge of the above classical data structures.