Data Structure Halloween Costumes

Posted October 31, 1998 at 9:00 am 2 Comments

Happy Halloween! Looking for some ideas for a good Halloween costume? You could succumb to tradition and dress up as a ghost or a witch, but you won’t succeed in scaring anyone with a tired old cliché like that. Here’s an idea for a costume that’s truly frightening, particularly if you’re in the company of computer science majors: a data structure.

If you’d like to keep the costume simple, dress up as one of the most basic of data structures: a linked list. In the picture on the right, some friends and I have dressed up as a singly linked list. Each person in the list points to the next person in the list, except of course for Shawn there on the end, who represents NULL.

linked-list.jpg (18768 bytes)

An unordered singly linked list.

Want to get a little more complicated? Try a doubly linked list! In this list, everyone points to the person behind them and the person in front of them. The only exceptions in the picture at right are me, the sentinel, and Shawn, who once again is NULL, much to his disappointment. This linked list is unsorted, but you could also choose to sort your list by age, height, or another criterion.

doublell.jpg (17638 bytes)

An unordered doubly linked list.

Another option is a circularly linked list. The advantage here is that nobody has to be NULL. Another benefit is the ease of insertion. When you arrive at the party, lots of other people will probably want to join in the fun, and if you’re dressed as an ordered singly linked list, this may require a recursive insertion function. In an unsorted circularly linked list, they can be added in anywhere in in the list with a single constant time operation.

circ-ll.jpg (14971 bytes)

A circularly linked list.

If you’re a real CS badass, you and your friends can try dressing up as some variety of tree. The obvious implementation is a basic binary tree, shown at right. Shawn is happy in this picture, because he’s no longer NULL, and is instead the root node. Dan, Jeff, Adam, and Dennis are leaf nodes, and Kevin and I are interior nodes. See if you can guess the sorting criterion.Looking for an even greater challenge? Dress up as a splay tree, adding people one by one. “Wait,” you’ll be thinking at each stage, “which do we need to do here, a zig-zag splay or a zag-zig splay?” If you have enough red and black shirts, dress up as a red-black tree! Keep in mind that you’ll have to swap shirts whenever you’re involved in a tree rotation.

tree.jpg (18915 bytes)

A balanced binary tree.

If you can’t get anyone to dress up as a data structure with you, you can always go to the Halloween party as a NULL pointer. Just put your arms inside your shirt (since you’re not pointing anywhere) and look lonely.

null-pointer.jpg (14447 bytes)

Dan dressed as a NULL pointer.

2 Comments »

RSS feed for comments on this post. TrackBack URI

  1. geek…!!!???

    Comment by geek hunter. — February 11, 2007 #

  2. You guys are the reason I doubt myself as a CS major.

    Comment by KanKan — October 1, 2007 #

Leave a comment

XHTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Powered by WordPress with Pool theme design by Borja Fernandez.
Entries and comments feeds.