We've started learning C++ the easy way: trial by fire. "Make a linked list," Ms. Marium said. "Go."
Well, it's done. That was fun. I knew enough about the language already to begin with a struct:
struct node{
int value;
node * next;
};
The only troublesome part was the pointer. CPlusPlus has a good tutorial. Anyways, that combined with my previous knowledge let me write a library of helpful functions in five minutes.
addNodeAfter(node n, int value);
addNodeToEnd(node n, int value);
insertNode(node n, int index, int value);
deleteNode(node n, int index);
Notice some problems? Some quick experimentation led to some more research. The "&" character in a function call allows one to pass a value by reference... now my nodes be linked from a given node rather than a local copy. No more memory leaks!
I also had some fun with pointer operators. "So you mean *(&(*(&(*(&(*(&(*(&n))))))))) ≡ n? Neat!" I found the arrow operator later. For a few minutes, my code was filled with the following:
(*n).value;
instead of
n->value;
But I figured it out soon enough. I also had some trouble returning pointers, but solved it eventually. Unfortunately, I don't have the bad code on hand; it's all fixed now :). Anyways, I now have a complete singly-linked list library for integers. But there was one more problem.
Just for fun, I tried to make a sorting function for the lists using a merge sort with the form:
void sortList(struct node & head);
I'd take in a list and modify it within the function. Problem is, it'd never work. For days I tried to track down the bug: the function would never return, crash the program, or something of that ilk. Rewriting didn't help. Three different times. But today I had more luck; it's fixed! I had taken in the head of a list by reference, sorted the list (thereby putting the head in a different position), then linked the head to the beginning of the list so the user of the function could use the result. See the problem? I'd link the list to itself - an infinite loop! Not good at all. My solution was to create a clone node to sort the list with and then delete it when the function exits. My test program outputs "0 1 2 3 4 5 6 7 8 9". QED. Perfect. Project done.