Well, We were taught linked list today and I have no clue about it, and he immediately assigned us this HW. Can someone help me understand this assignment.
#1) AddItem
This function allows the caller to add a new integer value to the linked list. The function has two formal parameters: a pointer to the head of the linked list, and the new integer value to insert into the list. It returns a pointer to the (potentially new) head of the list. Since this is a dynamically allocated list, that means that the function will have to use malloc to get enough space to store an LNode structure, copy the new integer value into the structure and insert the new node into the list. But -- where shall you insert the new list node?
In this implementation we're going to maintain the list in sorted ascending order. In other words, every time a new item is inserted into the list, you'll have to locate the appropriate position in the list for the new value. In order to pull this off you can use the "leadPtr/trailPtr" technique you saw in class today. A few other points you should consider:
- How will you know if the list is empty? By the value of the pointer to the head of the list. The main function will always maintain a pointer to the head of the list, and if it has a value of NULL, that means that the list is empty.
- If you find your program crashing, it is often because you're trying to dereference a NULL pointer. If this is happening to you, remember, you can insert a printf statement with a "%p" specifier to display the value a pointer variable contains. If you strategically place statements like this where you think the crash is happening you'll see the memory addresses the pointers are pointing to and might find either a NULL pointer or an uninitialized pointer (also a major cause for crashes). When you do something like this, it really helps to announce the function executing the printf statement, something like:
printf(“AddItem: before loop: nodePtr->next = %p\n”, nodePtr->next);
- Before you even consider writing a line of code, you should first draw pictures representing the list (just like we did in class) so you can derive the steps required for inserting a new node into the list. You should think how the three possible insertions compare -- insertion at the head of the list (this is the easiest to do), insertion to the end of the list (this is the next easiest), and insertion into the middle of the list (this one takes the most work). Not only will this make the entire process much easier and save you from wasting lots of time, it will also tell you if you are clear on what needs to be done. So go ahead and draw the nodes and the lead/trail pointers and see if you can come up with the steps for the algorithm.
#2) RemoveItem
This function allows the caller to remove an integer value from the linked list. The function has two formal parameters: a pointer to the head of the linked list, and the integer value to remove from the list. It returns a pointer to the head of the list. (Note – just for fun, see if you can take advantage of the fact that the list is already in sorted order.)
#3) ReleaseMemory
This function will traverse the list and release all memory allocated for each node, one at a time. True, every time a value is removed from the list its corresponding LNode is released, but this function is called if the user decides to end the program without removing all the items manually. This function has a single formal parameter, a pointer to the head of the list; its return value is is an integer representing the total number of nodes that have been released. (BTW, I suggest writing a quick makefile for your program, it'll make it much easier to rebuild the program as you make changes.)
Linked list
