A better way to insert into a linked list in C

To avoid an 'if' statement where we assign either to "head" or to "something−>next", since these are both "struct item *" variables we can use a pointer to "struct item *". In other words, a "struct item **".

After writing

	struct item **pp;

, it is suitable to assign "&head" to pp.

Then accesses formerly to 'p' now can be made to "*pp".

Instead of "p = p−>next;", we would now need to write the slightly awesome

	pp = &(*pp)->next;

The "&" is applying to all of "(*pp)−>next"; no further parentheses are needed there. However, the parentheses around "*pp" are needed because of the operator precedence. So this is slightly awkward. (But it will be worth it below!)

Let's look at the new-style loop

	for (pp = &head; *pp; pp = &(*pp)->next)

and compare it to the old-style loop

	for (p = head; p; p = p->next)

In all cases, 'pp' in the first is a pointer to a variable containing the same value as 'p' in the second. Specifically, pp is a pointer to the variable containing the pointer to the struct-item we're looking at (whether it's stored in 'head' or in some other item's 'next' value).
So if the linked list is of length at least three, and p ends up being the values of head, head−>next, and head−>next−>next in subsequent loop iterations;
then pp will be the values &head, &head−>next, and &head−>next−>next in subsequent loop iterations.

So it doesn't sound so different so far. But we then have a very useful situation once we do find the item. Instead of the 'if's around whether this new item is going at the head of the list or in the middle, we can simply write:

	new->next = *pp;
	*pp = new;

and this takes care of both cases:
If pp is still a pointer to 'head', this assigns new−>next the former value of 'head', and changes 'head' to point to the new item.
If pp is a pointer to the 'next' field in some struct item, this assigns new−>next to the former value of that 'next' field , and changes that 'next' field to point to the new item.

Eliminating these special cases is good. Code for this revised style of linked-list manipulation is slightly more complex in one sense, but that's something about pointers which you will get more and more used to. And it's simpler in all other respects. Once you are comfortable with all these pointers, it will be less error-prone to implement linked lists in this new style.

There is, however, no point in revising the search() function to use this new strategy. Since search() does not modify the list, nothing would be gained by having it manipulate pointers to the pointers, instead of the pointers themselves as it already does. So keep search() simple.

So, copy either your 4.c or my 4s.c to a new 5.c, revise the insert() function to use this new strategy, and submit your revised file with

	submit -c csc209h -a lab08 5.c

As you can see, the new insert() is much shorter than the other one.

Note: To get the mark for 5.c, you must eliminate all special cases -- no 'if' around whether the insertion is at the beginning of the list, or any other special cases.

Solutions from this point forward will be provided only after the lab submission deadline is past. However, partial marks will be awarded for this lab if you complete at least 2.c, 3.c, and 4.c, and at least 2.c and 3.c work fully, and all three compile with "gcc −Wall" with no warning or error messages. (For full marks, of course, you need to complete all five programs, and all but 4.c need to work fully.)

Finally, we will write code to delete from the linked list. It will be much easier to do this using our extra level of indirection.