Skip to main content

Categories of Data Structures

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 a tree is called the root.  The root in the only element which can be accessed externally.  Any element with no children is called a leaf.  An example of a binary tree might look like this.


Hashes
A hash is similar to an array but the elements are accessed according to a mathematical function.
Sometimes the elements in the hash will have lists coming form them.



Graphs
Unlike the other data structures graphs may or may not have much structure.  We will get to these much later.

 Each of these categories has many variants variants with different properties.
 There are literally hundreds of different data structures and if you've never seen the one you need then you will never know when to use it.  We will examine each of these categories in more detail with following posts.
Labels:

Comments

Post a Comment

Popular posts from this blog

Duck typing considered harmful.

I've had a chance to work on a fairly large chunk of Python at this point and have decided that Python (like Perl) is completely untenable at scale.  <rant><rave><drool>  but wait!  I have reasons! Programmers spend most of their time reading code.  We read massive amounts of code.  After we read massive amounts of code we write one... or change one... To make a change to a piece of code you first have to understand what it does and how it interacts with the system around it.  Then we start reading massive amounts of code again.  Anything you can do to minimize the amount of code a programmer has to understand to make a change becomes a huge gain in productivity. Duck typing causes the amount of code you need to read to make a change to grow very large. For example lets look at two functions, one in C++ and one in Python. First in C++ int function(type1 arg1, type2 arg2) {   return arg1->method(arg2); } In this fun...
1 comment
Read more

Microprocessor Architectures in the top500 list.

The  top500 list has been swamped by x86 machines over the last several years.  Anyone who knows me is aware that I am NO fan of the x86 ISA. Somewhat heartening is that the most recent list seen a resurgence in other architectures.  The Power architecture from IBM has been a fixture on the list for a long and is still a strong contender even though it has fallen to No. 12 from No. 9 last time and No. 1 in November of 2007. A Sparc machine has captured the No. 1 place this year and is actually as powerful as the the No. 2 through No. 6 systems combined. The Chinese MIPS based Loongson processor is starting to make some noise and the Dawning 6000 is reported to eventually reach a Petaflop in computing power. One other note is that an increasing number of machines in the top500 list rely heavily on GPUs.  The No. 2 machine on the current list, the Chinese Tianhe-1a machine, is comprised of 14,336 Intel Xeon processors and 7,168 Nvidia Tesla GPUs. Now ...
Post a Comment
Read more

Staking Claims: A History of Programming Language Design Claims and Evidence

Found on  Lambda the Ultimate  ( a great programming languages blog btw ) A great article  on programming languages through history and the truth of their claims. From the article: While still a relatively young field, computer science has a vast body of knowledge in the domain of programming languages. When a new language is introduced, its designers make claims which distinguish their language from previous languages. However, it often feels like language designers do not feel a pressing need to back these claims with evidence beyond personal anecdotes. Peer reviewers are likely to agree. In this paper, we present preliminary work which revisits the history of such claims by examining a number of language design papers which span the history of programming language development. We focus on the issue of claim-evidence correspondence, or determining how often claims are or are not backed by evidence. These preliminary results confirm that unsupported claims have been ...
Post a Comment
Read more