ImpalerCore
9/16/2011 3:28:00 PM
On Sep 16, 10:09 am, Malcolm McLean <malcolm.mcle...@btinternet.com>
wrote:
> On Sep 16, 3:26 pm, jacob navia <ja...@spamsink.net> wrote:
>
>
>
> Ypu can cut that code down to just this
>
> NODE *reverselinkedlist(NODE *head)
> {
> NODE *prev = NULL;
> NODE *temp;
>
> while(head)
> {
> temp = head->next;
> head->next = prev;
> prev = head;
> head = temp;
> }
> return prev;
>
> }
>
> This expresses the good things and the bad things about C. The code's
> only a few lines, so it's hardly worthwhile writing a function for it.
Code compression is not the best reason for defining functions. Code
abstraction is. As such, I fail to see how this is a 'bad thing'
about C. I see it as a very good thing, of any programming language
worth using.
> Normally you'll have a linked list consisting of a "next" member
> embedded in some structure or other, and you can just modify the code
> boilerplate. But it would be nicer to be able to make it generic.
It is possible to make it generic if you're willing to place the onus
on the user to be responsible for the keeping track of node's
referenced object type. GLib has a linked list structure with a
void*, and a function like reverse can be implemented independently
from the knowledge of the list's object type.
In my opinion, having one general abstraction for a linked list using
void* is more valuable than packaging the type information in the list
node (so you don't have to cast the node's object pointer). If the
number of types that require linked lists is one or two, or efficiency
is a high priority, then packaging a specific object type in the list
node with a struct can be better.
> Also, the code will crash if passed an invalid list,
You trade safety for efficiency. It's a judgement call; it only looks
good/bad depending on your perspective. The implementors of C
compiler's standard string library in <string.h> usually make a choice
for efficiency. Again this goes back to whether you want to test for
a function's preconditions, and if tested how you respond to them:
early-exit with an error value, argument substitution, use a benign
value, set a global errno, log a message to the screen or to a file,
assert, controlled-crash (like saving user's work), let the OS deal
with it ...
> but it needs no
> special conditions for the empty list or the one-member list case.
> Also, you've got the annoying little dance with a temporary. It's not
> possible to glance at the code and see that it is right,
That's a matter of experience. Sure, maybe the lisp people will get
it right away. I wouldn't necessarily bet that the average C
programmer will "get it" better. I doubt most students learning
linked lists for the first time will be able to visually inspect
either and know that it's right without sitting at a computer (I know
I sure didn't).
This is why you write functions to begin with, to reduce the
complexity into containable pieces (what I refer to as code
abstraction). Users of the linked list reverse function shouldn't
want or need to see that it's done right. Granted if the function is
implemented poorly, it becomes a concern, but that should be visible
with external behavior or tests, not through inspecting the source
code. For example, if one is a Windows applications programmer, you
really don't want to dig down into the source of a Windows API call to
see if it's doing something right or wrong, do ya?
> as you can
> with the performance-insensitive solution.
>
> NODE *inefficientreverse(NODE *head)
> {
> if(head->next == 0)
> return head;
> answer = reverse(head->next);
> append(answer, head);
> return answer;
>
> }
The real advantage of functions is that you've hidden the
implementation details, so if the 'inefficientreverse' function is not
good enough from some limitation, you can modify the function rather
than every manual linked-list reverse spread throughout your program.
When a regular posts that they'd prefer to do linked lists by hand, I
scratch my head and wonder why. Why is the linked list seemingly
impervious in the mindset of some to improvement by abstraction?
(I know you likely already know most of this stuff, just putting my
thoughts out there)
Best regards,
John D.