-----------------------------------

wtd

Wed Dec 20, 2006 3:43 am


Data Structures and Boolean Logic

-----------------------------------

Pointers and Data Structures: The Real Story

In Data Structures classes that use C, C++, and Java, it is not at all uncommon to use pointers.  Yes, even in Java, pointers are used.  You just don't see that reflected in the syntax.  

The real question, though, is why pointers are used.

Pointers permit one very important thing in these languages.  They permit boolean logic with any given type.  Normally we think of boolean logic as being limited to "true" and "false," but really it applies to any "one or the other" situation.

With pointers, a variable is either a valid pointer to some piece of data, or it's null.  

Consider a simple linked list.  A null pointer would symbolize an empty list.  Anything else is a non-empty list.

Variant Types

Pointers can be avoided if boolean logic can be symbolized in some other way.  Variant types permit just such a thing.

Consider an O'Caml linked list.

type linked_list = Empty | Node of int * linked_list

Dynamic Typing

In yet other languages, static-typing is not required, and we can achieve this same logic by assigning a different type of value to the same "next" variable we would have created in the earlier languages.

For instance, in Ruby, rather than having next be another object representing a node, we might assign to it the nil object.

The Point

Using pointers, or using variant types, or dynamic typing, the logic remains the same.  It is important to see past the particular implementation strategy and grasp this fundamental truth when learning about data structures.


-----------------------------------

Null

Wed Dec 20, 2006 9:36 am



-----------------------------------

I think that code should actually read:


type linked_list = Null | Node of int * linked_list;;


but I'm not positive.

:)


-----------------------------------

wtd

Wed Dec 20, 2006 11:18 am



-----------------------------------

Yes, yes it should.  Though I didn't include the double semi-colon.