5 ms·

I've been teaching CS101 for two decades. I've never shown (nor seen another instructor show) a two pointer implementation for list traversal, except perhaps as

I've been teaching CS101 for two decades. I've never shown (nor seen another instructor show) a two pointer implementation for list traversal, except perhaps as an example of bad practice (probably by someone who doesn't understand the syntactic sugar of the -> operator). "Every pointer to node is a list, including the trivial case of a null pointer being an empty list" is the way I was taught in CS101 in the early 80s, including a one-pointer implementation of this algorithm in Pascal. I suspect this might a case similar to that of the "Waterfall Method", where we have this unexamined belief that in olden times or academia they just weren't capable of comprehending really obvious things. CompSci instructors, and most of their students, are quite capable of recognizing that two pointers aren't needed, if only because every algorithms textbook they've ever read discusses it. I think that this might be like Bubble Sort: it's discussed in class as a way of illustrating a point. In students' fuzzy memories of school, they remember that bubble sort and 2-pointer traversal were taught, but they forget that they were taught only to show why selection sort and single pointer ("look ahead") traversal are better algorithms. As a side note: I don't like the "elegant" version's use of double indirection. It's not necessary if you return a pointer instead of void, which is also nice because you can treat calls to your list functions as lists themselves and chain them together. It also allows you to avoid warts like `p = &(*p)->next;` at the modest cost of needing `p=remove(p,t)` instead of `remove(p,t)`. Finally, the use of two structs is unnecessary. IntList is just a wrapper around a pointer to IntListNode. Why not just use a naked pointer to IntListNode like the gods intended?

xpe 6y ago
> Finally, the use of two structs is unnecessary. IntList is just a wrapper around a pointer to IntListNode. Why not just use a naked pointer to IntListNode like the gods intended? So Say We All.
xpe 6y ago
> As a side note: I don't like the "elegant" version's use of double indirection. It's not necessary if you return a pointer instead of void, which is also nice because you can treat calls to your list functions as lists themselves and chain them together. Agreed. > It also allows you to avoid warts like `p = &(p)->next;` Does it? Isn't having `p = &(p)->next;` in the while loop necessary? > at the modest cost of needing `p=remove(p,t)` instead of `remove(p,t)`. I may disagree since an API is used many more times than the API function is written.
- ajarmst 6y ago
  The & isn't needed if you're returning a pointer and no longer need a pointer to pointer to return the list as an argument. Also, if you get rid of the struct containing a single pointer and just use pointers, you can have the following instead… ` p=p->next As for the API, returning the pointer allows a function to be an argument for another function, which I find more flexible. ` p= remove(p,find(p,value))// I also like the option to be able to do stuff like: ` p=remove(remove(p,t),t); //remove two or: ` if (!remove(p,t)) {//that was my last node } But that may be an artifact of my preference for functional programming.
  - xpe 6y ago
    Nod, nod, nod. Thanks for clarifying :)
tgv 6y ago
Without the container struct, you'd have to pass the pointer to the pointer of the first element, remove(&head, elem), or assign the return value back to it, head = remove(head, elem). A container also allows you to maintain a counter and a tail pointer, for fast append and insert. Above all, a container makes it harder to return a pointer to just somewhere in the middle of the list and treat that as the head.

xpe 6y ago

> Finally, the use of two structs is unnecessary. IntList is just a wrapper around a pointer to IntListNode. Why not just use a naked pointer to IntListNode like the gods intended? So Say We All.

xpe 6y ago

> As a side note: I don't like the "elegant" version's use of double indirection. It's not necessary if you return a pointer instead of void, which is also nice because you can treat calls to your list functions as lists themselves and chain them together. Agreed. > It also allows you to avoid warts like `p = &(p)->next;` Does it? Isn't having `p = &(p)->next;` in the while loop necessary? > at the modest cost of needing `p=remove(p,t)` instead of `remove(p,t)`. I may disagree since an API is used many more times than the API function is written.

ajarmst 6y ago
The & isn't needed if you're returning a pointer and no longer need a pointer to pointer to return the list as an argument. Also, if you get rid of the struct containing a single pointer and just use pointers, you can have the following instead… ` p=p->next As for the API, returning the pointer allows a function to be an argument for another function, which I find more flexible. ` p= remove(p,find(p,value))// I also like the option to be able to do stuff like: ` p=remove(remove(p,t),t); //remove two or: ` if (!remove(p,t)) {//that was my last node } But that may be an artifact of my preference for functional programming.
- xpe 6y ago
  Nod, nod, nod. Thanks for clarifying :)

tgv 6y ago

Without the container struct, you'd have to pass the pointer to the pointer of the first element, remove(&head, elem), or assign the return value back to it, head = remove(head, elem). A container also allows you to maintain a counter and a tail pointer, for fast append and insert. Above all, a container makes it harder to return a pointer to just somewhere in the middle of the list and treat that as the head.