Monday, December 05, 2005

On implementing singly linked lists

This weekend, on account of a friend’s assignment, I had to delve into implementing linked lists. (Yeah, I admit, I’ve never taken time to study the implementation of these babies, all I knew was the concept). Jumping in with my usual optimistic, how hard can it be… I mean, I’ve written kernel modules to boot ;)


Anyways, to be honest… the singly linked list was not hard to implement at all. I got all the basic operations, Create(), Free() (oh… I love to valgrind my stuff, it gives me a good feeling ;) ), Add() and Remove(), these were relatively painless (for the Add(), I had to implement a Find_Last(), so I could always append at the end of the list, being that I wasn’t holding a tail pointer anywheres).


Anyway, the other requirement was for the list to be always sorted in ascending order. And away I went, I mean, how hard can sorting and swapping of pointers and s*** be? I’ll just add this teeny… weeny… BAAAM!!! I hit a road block!!! Suddenly, my understanding of pointers is being stretched to the limit, and much as I would hate to admit on OpenInterWeb™, I DON’T KNOW POINTERS LIKE I THOUGHT I DID!!!


It was a sobering moment, as I kept deceiving myself, fighting with a very annoying segment of code, trying to get the sorting to work and I finally admitted to myself… I’ve been butt kickd!!! DAMN!!! You can imagine how intelligent I was feeling then.


Anyways, I’ve managed to bookmark a lot of articles on advanced pointers and linked lists, and data structures in general (I mean, when I kick this guy in the patella, I’m off to the Races with Hash Tables, and binary trees!!!).


One of the good things I found out tho, was that traversing a list with a for is not quite so neat as with a while. I’ve been so used to all the foreach, for foo in bar ;), constructs, my initial reaction was to traverse with a for loop. When doing things like Remove(), that need a reference to a previous pointer, its somehow *cleaner* to use a while loop, at least, it made my code cleaner when I changed the fors to whiles.


Anyways, I think every hacker worth his salt, should try to implement a couple of things just for the fun of understanding them. And if possible, eat your own dog **** on a couple of projects, so I’m making up a list of stuff I NEED to do before this year runz out finally J


  1. Complete the Darned Sorted Singly Linked lists,
  2. Inherit and implement Doubly Linked Lists
  3. Implement Basic Hashtables
  4. implement a Basic Binary tree


Wow!!! Now that’s a tall order!!! That means, I’m parking/suspending all other hacking endeavours for the next two weeks :(


The other thing I started thinking of, and I’m not so fixated on it now, but I wouldn’t mind attempting an implementation, is a Garbage Collector. This one is really of interest to me, as I’m very MemoryLeak conscious these days.


Oh well… lets see what happens in the next two weeks. I must win I tell you.


Post a Comment

<< Home