2 ms·
> a simple, standard, procedure to copy a linked list: Using the same argument for the input and output, when making a copy, is idiotic, not standard. Well, m
by kazinator 5y ago
> a simple, standard, procedure to copy a linked list:
Using the same argument for the input and output, when making a copy, is idiotic, not standard.
Well, maybe idiotic is standard, but that's another discussion.
Copying linked lists is not a widespread practice in C programs, by the way; if we don't count C programs that are Lisp interpreters. It creates memory handling problems.
In this example, the nodes carry data consisting of integer values. These are referenced by pointers. The copy is shallow-copying these pointers, which could be an issue. If the integers are dynamically allocated, who cleans them up? They have to persist as long as either list is still reachable.
The average embedded C programmer's imagination doesn't even extend to the idea that a linked list would ever be copied.
"Like whaddya mean? The list nodes are embedded in the task control blocks ... you'd have to duplicate the actual processes themselves. It makes no sense."
Idiomatic C code uses structs for linked lists, not void * pointers to binary cells consisting of two void * pointers, one of which is actually an int value.
I also don't understand why the example function is casting (void **) r when r already has that type.
Here is something more reasonable, still with the shallow-copy issue of the pointers-to-integer, and no handling of a null out of malloc. The code is very easy to follow:
struct cons {
int *car;
struct cell *cdr;
};
struct cons *listcopy(struct cons *list)
{
if (list == 0) {
return list;
} else {
struct cons *ncell = malloc(sizeof *ncell);
ncell->car = list->car;
ncell->cdr = listcopy(list->cdr);
return ncell;
}
}
If the lists can be long, the stack growth can be a problem; this isn't tail recursive. You want something iterative. One possibility is a two pass version:
struct cons *listcopy(struct cons *list)
{
struct cons *copy = 0;
struct cons *out = 0;
struct cons *cdr;
/* walk list, allocating new nodes, pushing
* them onto copy stack
*/
for (; list; list = list->cdr) {
struct cons *ncell = malloc(sizeof *ncell);
ncell->car = list->car;
ncell->cdr = copy;
copy = ncell;
}
/* Reverse copy stack in place by popping
* all nodes and pushing them onto the out
* stack.
*/
for (; copy; copy = cdr) {
cdr = copy->cdr;
copy->cdr = out;
out = copy;
}
return out;
}
Here we can separately verify whether the copy stack is correctly produced, and then correctly reversed into out.
The average seasoned C pro will probably jump to this sort of solution, but not use any cons/car/cdr terminology he or she never heard of:
struct cons *listcopy(struct cons *list)
{
struct cons *copy = 0;
struct cons **pcdr = ©
for (; list; list = list->cdr) {
struct cons *ncell = malloc(sizeof *ncell);
ncell->car = list->car;
ncell->cdr = 0;
*pcdr = ncell;
pcdr = &ncell->cdr;
}
return copy;
}
Using a dummy node on the stack to serve as the list parent, we can notationally eliminate the ** pointer:
struct cons *listcopy(struct cons *list)
{
struct cons dummy = { 0 }, *tail = &dummy;
for (; list; list = list->cdr) {
struct cons *ncell = malloc(sizeof *ncell);
ncell->car = list->car;
ncell->cdr = 0;
tail->cdr = ncell;
tail = ncell;
}
return dummy.cdr;
}