Data Structures – What Do Programmers Mean by Data Structures?

Trees, like lists, are "abstract data types" which can be implemented in different ways. Each way has it's advantages and disadvantages.

In the first example, the main advantage of this structure is that you can access any child in O(1). The disadvantage is that appending a child might sometimes be a little more expensive when the array has to be expanded. This cost is relatively small though. It is also one of the simplest implementation.

In the second example, the main advantage is that you always append a child in O(1). The main disadvantage is that random access to a child costs O(n). Also, it may be less interesting for huge trees for two reasons: it has a memory overhead of one object header and two pointers per node, and the nodes are randomly spread over memory which may cause a lot of swapping between the CPU cache and the memory when the tree is traversed, making this implementation less appealing for them. This is not a problem for normal trees and applications though.

One last interesting possibility which was not mentioned is to store the whole tree in a single array. This leads to more complex code, but is sometimes a very advantageous implementation in specific cases, especially for huge fixed trees, since you can spare the cost of the object header and allocate contiguous memory.

OO, according to Alan Kay is all about message passing, and that's it. You will see that qualities such as polymorphism and encapsulation are actually derived from message passing.

Now that stance is in fact very extreme, because it basically means that only Smalltalk and languages alike would qualify.

I think you can define OO as building your system on entities, that fully encapsulate their state, and that are rendered exchangeable due to their inherent polymorphous qualities. One could thus argue a purely OO language ensures these two core qualities are always met. What renders OO languages "impure" would be mechanisms that allow the creation of constructs that do not meet these criteria, such as the possibilities to:

• declare public fields
• declare variables that can only hold instances of a specific class and its subclasses (i.e. variables should be typed against interfaces, which is what the biological objects communicate through in Kay's anology), which is rendered even narrower if the class in question is final, as that leaves even less room for polymorphism
• declare primitives

Then again, IMHO language purity is more a weakness than a strength. OO is not a silver bullet. No single paradigm is.