Tuesday, December 13, 2005

yirae: lists complete

Yesternite, I was able to wrap up the episode on Singly and Doubly linked lists for libyirae. I’ll upload the code later in the evening.

Some cool things happened as usual during the coding process, that allowed me to refactor out more Node manipulations, like Make_Next_Node, Make_First_Node (this for doubly linked lists, as singly linked lists don’t have any differentiating features for the *first* node), etc.


Most important of all, was that implementing the Doubly Linked List class ydList.c allowed me to see my algorithms more clearly, and had me going back to ysList (the singly linked class), to clean stuff up.


Right now, I have a number of todo’s but my next target Data Structure is a Hashtable.


Just before I get there though, I have to refactor the core operations of the linked lists class, I have a lot of operations, push, pop, insert, insertsorted, etc, and I think its not necessary. I want to settle on some core ops that can be used to perform the rest. For instance. Insert(), should be able to be used to implement both Append() and Pop(), even though that’s not what I’m doing currently. But before I move on the larger issue of Hashtables I have to clean up that (and probably, since it will be childs play, implement a Stack and Queue class).


After cleaning up the operations, I want to make the lists, generic. Right now, the DATA member of the lists are just ints. I want to make these into void * so I can use the lists as a generic carrier for _any_ type of data class.


Also, related to the immediate above point, I’m not sure how to structure the Hashtable. I have two options…


  1. struct yHashTable {

void *data;

char *key;

struct yHashTable *next;





  1. struct yhtData {

void *data;

char *key;



            Struct yHashTable {

                  struct yhtData *content;

                  struct yHashTable *next;




There seem to be advantages for each implementation. In 1 above, I have simplicity of representation and initial implementation, but I will have to rewrite most of my linked list code to support stuff like sorting by key, etc. in 2 above, I can pass in a different function pointer each time I need to sort, one for sorting by data, one for sorting by keys, and I won’t need to modify my linked list code much when inheriting to create the HashTable. I tend to favour method 2 above though, but I’ve not made up my mind yet which way to go. I’ll finish that operations clean up first, and then when I get to that bridge, I’ll just have to cross it.


It appears I’m still on target for my end of yr goal for Data Structures… the one I’m apprehensive about is Binary Trees. I don’t know *anything* about them apart from the fact that they’re pretty tall, and come in two flavours (b i n a r y   t r e e s…. get? :;) ) I guess that pretty much sums up my understanding of those :D


Anyways… back to other things now… I’ll post when yirae-0.3 is uploaded.


Essien… out.


Post a Comment

<< Home