Programmers Dojo

Now for a forest of trees. Trees are likely the most varied of all data structures.  There are specialized trees for applications in computer graphics, astrophysics, engineering, text processing, databases, and compression (just to name a few).  Trying to categorize trees into a small number of bins is somewhat pointless but I'll describe some of the broader types. First some terminology. The top of the tree is the root.   This is the only node in the tree which has no parents. The parent of a node is the node which is higher in the tree.  A node will only ever have one parent. The children  of a node are all the nodes which are connected and one step lower in the tree. An interior  node is one which has both a parent and at least one child. A  leaf  node is one which has no children. The height  of a tree is the distance from the root to the lowest child. The depth of a node is the distance from the root to that node. Now for s...

Hashes begin with an array.  That array is indexed with a mathematical function called a hash function.  Since the hash function is based on the key of the element you can jump "close" to the right element very quickly. The main distinction between types of hashes is in how they handle collisions. In a closed hash you iterate through the array to find the next open slot in the array. In a chained hash there is actually a linked list in each slot in the array.  Each element is simply added to the list. Both types of hashes have pros and cons but I'll elaborate those in a later post.

Lists are another very basic data structure.  Despite that they are actually quite varied. Essentially a list consists of blocks of memory linked together with pointers.  How they are linked and how they are accessed determines the type of list. The first distinguishing factor is the number of links.  If there is only one link this is a singly linked list.  Singly linked lists can only be traversed in one direction, but are quite small because they only have one pointer.  Lists with both a forward and back pointer are called double linked lists.  These lists can be traversed both forward and backwards.  Also you can easily delete an element from the center of a list since you have pointers to both the last element and the next element.  Finally there are lists with more than two links.  They generally allow you to traverse your data in more than one way and are only used for specialized purposes. The second distinguishing factor is the l...

Arrays are one of the earliest data structures.  They are essentially just a block of memory which is accessed by offset.  Despite their simplicity there are still several broad categories each with their own sets of algorithms. Is the array a fixed size or can it grow as you add elements to it? A fixed size array is called a static array and one that can grow is called a dynamic array. Are the element all of the same type or can they be different? If they must all be the same type then the array are called homogeneous.  Otherwise it is a heterogeneous array. Finally, how many dimensions (subscripts) does the array have? For example, a 2 dimensioned array is a matrix. The number of dimensions doesn't change the structure of the array but changes the way elements are accessed. 

For our purposes I will propose 5 classes of data structures.  These being the array, list, tree, hash, and graph. Arrays Arrays are one of the most basic data structures and are characterized by direct access to every element in the structure.  It is easy to picture them as a line of numbered buckets where you can place an element into or remove an element from any bucket. Lists Lists are another very basic data structure.  In a list each node has one of more connections to other nodes.  Access to the list is only at one or both ends.  From any given element you can access any element which you have a connection to.  Here is an example of a simple list. Trees Trees are similar to lists in that each element has connections to other elements but in a tree the connections are more structured.  Each element in a tree can have children.  The number of children an element can have is an important property of a tree.  The top element in ...

Like a dojo I hope this blog to be a place of instruction and hopefully study. The primary focus will be on data structures, algorithms, and programming languages.  There will be lots of programming problems thrown in and likely a few rat holes to who knows where. Like anything else improvement requires practice so I encourage you to work the problems. The first post will be an introduction to basic data structures followed by an exploration of the main branches of data structures.  Then we will implement some of these in a few languages to see the differences the programming language makes. Please feel free to comment, criticize or request and I'll see what I can do.