Heterogenous linked lists

Thursday, October 05, 2006

I am taking this OOP(Object Oriented Programming) class right now. So far most of the stuff has been pretty familiar to me. I have never had much experience working with linked lists. That is part of the reason I took this class. Not that I plan on using them for my job or ever again after school, but many of the classes I have to take depend heavily on them. So, I decided to become very intimate with them.

"What is a linked list", you ask? Well, A linked list is the concept of using memory pointers to link a bunch of items together. For example, if you wanted to maintain a list of names that could grow or shrink you would probably want to use a linked list. The programming language I use at school is C++. In C++ they force you to learn how to manage lists the hard way and then show you the built in stuff to make your life easier. So, for now we have to change up all these pointers and take caution not to produce memory leaks. In many programming languages you have more modern techniques for building lists of items the can grow and shrink as necessary.

Now for the heterogenous part. That just means mixed or not of the same kind. So, an example might be a list of animals. Some are cats, some are dogs and some might be penguins. Building and managing these lists can become a huge pain in the arse. It is not so difficult to loop through all the items in the list. Adding, removing and sorting is where things start to get a little rough.

Sure, it seems simple to just say I want to move item 1 to item 3. But in reality you would have to take into account if item 1 was at the front of the list, if item 3 was at the back of the list, carefully repoint them to their new 'next' and 'previous' items and finally repoint their former 'next' and 'previous' neighbors to the updated location of the items now that they have moved.

Hmmm... kinda like the hassle of trying to change your address in the US. They always seem to screw something up. They keep sending mail to your old address or send it back because they don't have a forwarding address on file.

Anyway, I made 3 separate attempts at getting a sorting algorithm to work. On the 3rd I finally got it. I was not correctly repointing the neigboring items in the list. Kind of like if you move and don't tell anyone. Well, then how can anyone get a hold of you? There is an idea! Needless to say I finally got it, learned from my mistakes and decided that next time I would steal someone else code rather than figure it out for myself.

So, thats it. If you came to this page from a google search on linked lists hoping to get some free code, sucks to be you. Keep searching. Check out the Linked List basics on Stanford's site. They even have a cute little clay-mation video example. Reminds me of Mr. Bill from way back in the day.

Go code yourself into an infinite loop.

 

posted by: ndicenso @ 2:47 PM   2 Comments | Post a Comment