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
- Complete the Darned Sorted Singly Linked lists,
- Inherit and implement Doubly Linked Lists
- Implement Basic Hashtables
- 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.