C PROGRAMMING:

Q1: BETTER INSERTING

A better way to insert into a linked list in C (insert() function must insert in order)

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.

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

Starter code provided below:

#include

#include

struct item {

int key;

int data;

struct item *next;

};

struct item *head = NULL;

int main()

{

extern void insert(int key, int data), delete(int key), printall();

extern int search(int key);

insert(38, 3);

insert(20, 2);

insert(5, 0);

insert(22, 6);

insert(46, 18);

printf("With all five items: ");

printall();

/*

printf("After delete(22): ");

delete(22);

printall();

printf("After delete(5): ");

delete(5);

printall();

printf("delete(30) shouldn't do anything: ");

delete(30);

printall();

*/

return(0);

}

void insert(int key, int data)

{

struct item *new, *prev;

/* create the new item */

if ((new = malloc(sizeof(struct item))) == NULL) {

fprintf(stderr, "out of memory! "); /* unlikely */

exit(1);

}

new->key = key;

new->data = data;

/* find the node it goes after; NULL if it goes at the front */

if (head == NULL || head->key >= key) {

prev = NULL;

} else {

for (prev = head;

prev->next && prev->next->key < key;

prev = prev->next)

;

}

/* link it in */

if (prev == NULL) {

/* goes at the head of the list */

new->next = head;

head = new;

} else {

/* goes after 'prev' */

new->next = prev->next;

prev->next = new;

}

}

/*delete is for Q2*/

void delete(int key)

{

}

int search(int key) /* returns -1 if not found */

{

struct item *p;

for (p = head; p && p->key < key; p = p->next)

;

if (p && p->key == key)

return(p->data);

else

return(-1);

}

void printall()

{

struct item *p;

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

printf("%d: %d ", p->key, p->data);

printf("[end] ");

}