Let us reverse a list, only by re-linking the pointers! Write a C program to read numbers till 0 is observed, and prints the list at the end. Then, call the list reversing function and print the list again.
Solution
The solution is strikingly simple. We just need to take an element from the head of the original list and put it to the head of the reversed list, till the original list gets empty.
/* Reverses a linked list and
* returns the pointer to the head of the reversed one.
* Attention: the original list will be gone! The function uses
* the elements of the original list to build the reversed one.
* Usage:
* numbers = list_reverse(numbers);
*/
Number *list_reverse(Number *list) {
Number *original = list;
Number *reversed = NULL;
while (original != NULL) {
Number *relinked = original, *next = original->nxt;
relinked->nxt = reversed; /* add to the reversed */ /* 1 */
reversed = relinked; /* 2 */
original = next; /* take next from orig.*/ /* 3 */
}
return reversed;
}
The entire program is available to download from here: reverselist.c.
Assume we have a list storing integer numbers. After every even number found in the list, insert two new elements: a zero, and then the found (even) number again. Thus, starting with a list 2,3,4,5 we should get 2,0,2,3,4,0,4,5.
Solution
This is easy, since inserting new elements after the current one is simple. We traverse the list, and each time we find an even number we insert the zero and the number itself. There are two pitfalls, though. If we insert the two new numbers in this order, then they will be located in a reverse order in the list, hence, first the number must be inserted, then the zero. The next pitfall is that the iterator variable (p) needs to be incremented in a proper way to avoid the processing of the even number just inserted into the list.
/* Inserts a zero and the list element each time
* an even number is found in the list
*/
void list_202(Number *list) {
for (Number *iter = list; iter != NULL; iter = iter->nxt)
if (iter->num % 2 == 0) {
Number *newnum, *newzero;
newnum = (Number*) malloc(sizeof(Number));
newnum->num = iter->num;
newnum->nxt = iter->nxt;
newzero = (Number*) malloc(sizeof(Number));
newzero->num = 0;
newzero->nxt = newnum;
iter->nxt = newzero;
/* jump over the newly inserted elements */
iter = iter->nxt->nxt;
}
}
The entire program is available to download from here: list202.c.
Assume we have a list consisting of words. Let us delete those whose length is exactly 4!
Solution
We need to take care of the first element, it is possible that we have to delete it. In this case the head pointer changes, too. The following cases have to be distinguished:
- Once we have deleted the first element, it is possible that the second one is of length 4, too. In this case we have to delete that, too. Consequently, the checking of the first element is not just a simple "if" statement, it is a loop. Till there is a length 4 word in the head of the list, we need to delete it.
- While deleting, the list may become empty (if all the words stored are of length 4).
The loop can be implemented as follows:
while (list != NULL && strlen(list->word) == 4) {
Word *todelete = list;
list = todelete->nxt;
free(todelete);
}
Here we have exploited the lazy evaluation of the && oprtator. If the pointer is
NULL, then the list->word expression does not get evaluated, since the overall value of the expression
can be only FALSE. This is important, because we should never dereference the NULL pointer.
Consequently, the two terms of the logical expression must not be swapped!
After the loop there are cases:
- The list got empty, we have nothing more to do.
- There are still elements in the list, but it starts with a non-length-4 word, hence the head of the list wont be modified after the rest of the algorithm terminates.
When deleting an element from the list, we need to modify the "next" pointer of the previous list element. Thus, there are
two solutions. We either stop at the previous element, or we maintain an other, delayed pointer that points to the previous element.
The solution below makes use of the second approach: it is based on a delayed pointer.
Observe that, when an element is deleted, the delayed pointer does not get updated, only the iterator pointer (iter) does!
Otherwise, they both are updated, they move together. The corresponding program segment is as follows:
if (list != NULL) {
Word *delayed = list;
Word *iter = list->nxt;
while (iter != NULL) {
Word *next = iter->nxt;
if (strlen(iter->word) == 4) {
delayed->nxt = next; /* 1 */
free(iter); /* 2 */
} else
delayed = iter;
iter = next; /* 3 */
}
}
The entire program is available to download from here: erase11.c.