1. Lab 08 part 3 intro
2. Traversing
3. Searching
4. Inserting
5. Better insert
6. Deleting
Grading

[All of lab 08]
[All labs]
[Course home page]

Inserting into a linked list in C

Now please abandon your solution so far, or my 2s.c or 3s.c, and continue instead with /u/csc209h/summer/pub/lab/08/4.c , which removes the awkward "filllist()" function and instead wants an "insert()" function.

If you run the 4.c program as is, it will output that the list is empty because nothing has actually been inserted because insert() is empty.

Your task is to write insert() now. The insert() function will insert in order, maintaining the property that the linked list is sorted at all times, as is relied on in search(). So you have to traverse the linked list until you find either the end of the list or an item with a greater key, and insert a new item at that point, calling malloc(sizeof(struct item)) to get space for the new list item. (Don't worry about the case where there is already a node with that key -- you will just add a second node with that key -- let's not make this a special case.)

If malloc returns null indicating out of memory, we will make this a fatal error for simplicity. (I.e. print an error message and exit(1).)

Debugging suggestion: add printall() calls after each insert(), and maybe other printf statements. (Or use gdb.)

Please work on this in a file named "4.c". To get the full marks for the lab you need to submit this file, but unlike the other submitted files, this one need not be working for full credit, although like the other submitted files, it does need to compile with "gcc −Wall" with no errors or warning messages. As always, submit with

	submit -c csc209h -a lab08 4.c


After you've spent sufficient time on this and submitted your file, click here for further discussion.