Month: June 2016

Building a Pugly-Linked List

Meet Janie. Janie has an ever-changing menagerie of pugs, and would like to use a data structure to keep track of them. What data structure would be most suitable? Janie could keep her pugs in an array, but this isn’t a good choice for several reasons. Arrays are best for collections of constant size, while the size of her menagerie varies. Further, any ordering of the pugs will require re-sorting the array as pugs enter and leave, and without this ordering we lose the benefit of being able to find a given pug in O(1) time by indexing into...

Read More

Interfaces in C#

Consider test-driving a new car, of a make and model you’re not familiar with. It’s unlikely you’ll need any instruction in how to do it: rightmost pedal makes the car go, pedal next to it makes the car stop. Even though there are many different cars, they have a reasonably consistent interface that allows most people to drive most cars. Subclassing Car Suppose we want to implement this in code. Let’s say I want to use a Camry object. A Camry “is a” car, so it makes sense that the Camry class inherits (possibly indirectly) from the Car class. We would never actually instantiate a generic “car” object, so Car can be an abstract class. What methods would Car have? Two obvious ones could be ApplyGas and ApplyBrake. Maybe they’re implemented something like this: In this case, the comments are standing in for some code that physically allows more gas into the engine or applies the brakes. This works fine….as long as every car works exactly the same way. But what happens if we have, for example, a Prius? Now stomping on the gas pedal may or may not actually be sending more gas to the engine, which means that we need to override the behavior in the derived class. More generally, for each type of car that derives from the Car class and uses different hardware, we’ll need...

Read More