Programmers Dojo

For our list of primes we need a list (naturally).  The best way to understand data structures is to implement them in a low level language.  Since I don't feel like inflicting ASM on everyone (although I do like assembler) we will use the next best thing.  C Out list needs a data element (the found prime) and a pointer to the next element. In C that looks like this. struct prime_elem_s {   uint64_t prime;   struct prime_elem_s *next; }; typedef struct prime_elem_s prime_elem_t; We define a structure containing the current prime and a pointer to the next element.  Then we define a type prime_elem_t to refer to that structure. In this case we want to add elements to the end of the list so we will also need a tail pointer.  We will create a list header which will keep a head and tail pointer as well as the number of elements in the list. typedef struct {   uint64_t length;   prime_elem_t *head;   prime_elem_t *tail; } pri...

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...

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 ...