Linked List

I have been trying to stick to this rule where I'll never use a pre-made implementation of an advanced programming concept without first creating my own version of it. The Objective-C stuff I've been working on has me frequently using the Foundation version of a linked list (NSArray and NSMutableArray). I've never created my own linked list implementation so this morning I sat down and hashed out the creation, adding of things, and deletion of a doubly linked list of character pointers. To make it complete I'll have to include insertion and deletion of nodes at any arbitrary point, but that shouldn't be too hard.

Here is what I came up with. My notes of what went right and wrong and some questions to address later are below.

DLinkedList.h

DLinkedList.c

main.c


What went right is that it seems to work. I'd like to add a list traversal function that prints out all the data in the node (node address, head pointer, tail pointer, and data) so that I can verify it's doing exactly what I think it's doing.

What went wrong is that I'm not sure if my AddWord() function is following the best practice for shuffling around variables. I'm always worried that I will treat pointers as special and not do the same thing I'd do if it was an integer. A new node being created in that function is always addressed "through" the node that preceded it. I should have created a temporary node pointer to hold the address of the newly created node and then assign the next/previous/data from that. The weirdness came from literally translating my hand-written notes to code.

What's left is to do the verification, stress test it, and add in some safety checks for all the malloc() calls. Then I can move on to adding in the insert and delete node functions and think of something clever to do with all of it.

I made the nodes rather specifically hold pointers to strings in memory. The next iteration of this needs to make it hold anything. I think I can do this by (in the event of strings) allocating the space, doing strcpy(), and then casting the pointer to void to store in the node. Getting the data back out means needing to re-cast, probably. I messed around with going to and from void a while back and I don't recall having any difficulty.

The list struct which holds the head and tail of the list is so that it's quick to find the last node. Otherwise I would have had to always have the last node's "next" pointer be NULL.

Right, so I think I can give this little side-project another run through in a few days and then I'll feel good about using fancier canned library versions of it!