Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Reversing a linked list

Reply
Thread Tools

Reversing a linked list

 
 
Malcolm McLean
Guest
Posts: n/a
 
      09-16-2011
On Sep 16, 6:28*pm, ImpalerCore <(E-Mail Removed)> wrote:
>
> 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?
>

It's the bool problem. Clever Dick writes

typedef int BOOL;

BOOL solvestoppingproblem(char *program);

The problem is now everyone who want to call solvestoppingproblem()
has got to import the typedef of BOOL. Clever Dick has no business
defining something as fundamental and atomic as a boolean type in a
high-level function file like solvestoppingproblem(). In fact the
integration problems become so severe that people just research their
own solvestoppingproblem() functions instead, because it's easier to
redo Clever Dick's work than to mess about with BOOLs and Bools and
boolean_t's all about the place.

You've got the same problem in declaring a generic linked list type.
Great if you're only writing all of only one program and you're the
configuration manager, so can insist that everyone uses it, but a
nightmare if you don't have that sort of controlled environment. Most
of the time, it's a lot easier to lay out the structures you need, and
just add a "next" member. Then you can manipulate the linked list by
hand, avoiding a dependency. That's why people are always writing new
string libraries, or linked list abstractions for C, and they never
catch on.

--
10 rules of programming
http://www.malcolmmclean.site11.com/www

 
Reply With Quote
 
 
 
 
Edward A. Falk
Guest
Posts: n/a
 
      09-16-2011
In article <(E-Mail Removed)>,
ImpalerCore <(E-Mail Removed)> wrote:
>>
>> You can cut that code down to just this


Thank you. Elegant and simple. Explains the process without
being verbose.

>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.


Totally agree. My rule of thumb in programming is: if you find your
self writing the same code for the third time, it's time to make it
into a function.

--
-Ed Falk, http://www.velocityreviews.com/forums/(E-Mail Removed)
http://thespamdiaries.blogspot.com/
 
Reply With Quote
 
 
 
 
ImpalerCore
Guest
Posts: n/a
 
      09-16-2011
On Sep 16, 12:28*pm, Malcolm McLean <(E-Mail Removed)>
wrote:
> On Sep 16, 6:28*pm, ImpalerCore <(E-Mail Removed)> wrote:
>
> > 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?

>
> It's the bool problem. Clever Dick writes
>
> typedef int BOOL;
>
> BOOL solvestoppingproblem(char *program);
>
> The problem is now everyone who want to call solvestoppingproblem()
> has got to import the typedef of BOOL. Clever Dick has no business
> defining something as fundamental and atomic as a boolean type in a
> high-level function file like solvestoppingproblem(). In fact the
> integration problems become so severe that people just research their
> own solvestoppingproblem() functions instead, because it's easier to
> redo Clever Dick's work than to mess about with BOOLs and Bools and
> boolean_t's all about the place.
>
> You've got the same problem in declaring a generic linked list type.
> Great if you're only writing all of only one program and you're the
> configuration manager, so can insist that everyone uses it, but a
> nightmare if you don't have that sort of controlled environment. Most
> of the time, it's a lot easier to lay out the structures you need, and
> just add a "next" member. Then you can manipulate the linked list by
> hand, avoiding a dependency. That's why people are always writing new
> string libraries, or linked list abstractions for C, and they never
> catch on.


Thank you, that was insightful. To me, it seems like the only
plausible solution (which I admit is very unlikely to happen) to the
problem (abstracting a generic linked list interface) is to have some
kind of "boost" for C, have some part of the library get so popular
and use its popularity as a springboard to fight to standardize the
interface. At least there is some evidence that the process can lead
to a positive impact on changing the C++ standard.

Best regards,
John D.
 
Reply With Quote
 
Ben Bacarisse
Guest
Posts: n/a
 
      09-16-2011
jacob navia <(E-Mail Removed)> writes:
<snip>
> Concerning the "preconditions" term, Betrand Meyer uses it as one of the
> two parts of a function contract: The preconditions and the postconditions.
>
> The first ones are the ones that the function requires from its
> caller, and the second ones are the ones that the function
> ensures to its users. They are part of the Eiffel language that Meyer
> designed.


Yes, I know a little about Eiffel. My point it is that as soon as a
condition moves from being part of the caller's contract to part of the
function's responsibility, it stops being a precondition; it becomes
part of the defined behaviour of the function. In C, since there is no
notation for pre-conditions, I think it's fine to use the term for
things "assert"ed at the top of the function, but I would not use it for
conditions tested in the body.

> It is true that Reverse has other preconditions not mentioned
> explicitely or shown in the code:
>
> o We assume a list that is terminated by a NULL pointer
> o We assume a list without cycles
>
> Testing for the first means
>
> if (l->count > 0) assert(l->Last->Next == NULL);


I am not sure that's enough. First, there are pre-conditions on
l->count but even if you deal with those, the NULL might not be
reachable from l->First. Basically all your list function will have a
precondition that the list is well-formed: no cycles, l->Last can be
reached from l->First in exactly l->count steps, etc. If you can write
this as a predicate you could try to prove that all your list functions
preserve that predicate (provided their pre-conditions are met). I'd
not try a formal proof (almost impossible in C) but informal ones can be
very handy at flushing out peculiar bugs.

> Testing for the second needs
>
> rvp = l->First;
> rvpFast = rvp->Next;
> while (rvpFast) {
> if (rvp == rvpFast) {
> iError.RaiseError("Reverse", CIRCULAR_LIST);
> return ERROR_CIRCULAR_LIST;
> }
> if (rvpFast)
> rvpFast = rvpFast->Next;
> if (rvpFast)
> rvpFast = rvpFast = rvpFast->Next;
> rvp = rvp->Next;
> }
> return 0;


You've made the empty list a special case again. Maybe it doesn't
matter if you want to test for that first but there's no need:

rvpFast = rvp = l->First;
while (rvpFast) {
rvpFast = rvpFast->Next;
if (rvp == rvpFast) {
iError.RaiseError("Reverse", CIRCULAR_LIST);
return ERROR_CIRCULAR_LIST;
}
if (rvpFast)
rvpFast = rvpFast->Next;
rvp = rvp->Next;
}
return 0;

<snip>
--
Ben.
 
Reply With Quote
 
HENRY Eshbaugh
Guest
Posts: n/a
 
      09-16-2011
On Sep 16, 2:30*am, jacob navia <(E-Mail Removed)> wrote:
> This group has lost many people. One of the reasons is that the
> newcomers just ask a question or two, and do not see discussions
> that try to explain code, teaching newcomers to the language how
> a program works.
>
> This is a second example (after hexdump.c) of commented code,
> i.e. explaining step by step how a relatively simple operation
> is done.
>
> Reversing a linked list
> -----------------------
> This is an evergreen of data structures programming. In most classes
> you will get an exercise like this:
>
> Exercise 7: Given a list "L" reverse it without moving its contents.
>
> The solution for this exercise is to go through the list, relinking the
> "Next" pointers in the inverse order, without touching any data that
> the list may hold. We will use the code of the C containers library and
> study how it is done.
>
> The library uses a simple structure "ListElement" whose definition runs
> like this:
>
> typedef struct _ListElement {
> * * *struct _ListElement *Next;
> * * *char Data[];
>
> } ListElement;
>
> We have a pointer to the next element of the list, and a chunk of data
> of unspecified length. This is the basic structure that will be used
> to hold the list data. Besides the list element we have a header of the
> list, containing several fields not relevant to the task of our reverse
> function. We will use only the following fields from that header:
>
> o RaiseError: Pointer to the error function.
> o First: The first element of the list.
> o count: The number of items in the list.
> o Last: A pointer to the last element of the list.
> o timestamp: A counter of the modifications done to the list.
>
> The interface of the reverse function is simple: it receives a list to
> reverse as input and returns an integer result code. A negative result
> means failure (with different negative numbers as error codes) and a
> positive number means success.
>
> * *1 static int Reverse(List *l)
> * *2 {
> * *3 * * ListElement *Previous,*Current,*Next;
> * *4
>
> The first thing to do in a serious program is to check the validity of
> the received arguments, i.e. test the preconditions as Bertrand Meyer
> would say it. We test that the list handed to us is not Null (lines
> 5- and that the list is not read-only (lines 9-12) since we are going
> to modify it.
>
> If anything is wrong we return an error code after calling the error
> function. Note that the error function is a field either in a global
> structure
> called iError (for interface Error) or is a field of the list itself. We
> use the global interface iError in the case that the list is\Null, or the
> list specific error function for the read only error. This is a powerful
> feature of C called function pointers that we will discuss in more detail
> later on.
>
> * *5 * * if (l == NULL) {
> * *6 * * * * iError.RaiseError("iList.Reverse",CONTAINER_ERROR_ BADARG);
> * *7 * * * * return CONTAINER_ERROR_BADARG;
> * *8 * * }
> * *9 * * if (l->Flags & CONTAINER_READONLY) {
> * 10 * * * * l->RaiseError("iList.Reverse",CONTAINER_ERROR_READON LY);
> * 11 * * * * return CONTAINER_ERROR_READONLY;
> * 12 * * }
>
> Then, we test for special conditions, i.e. for degenerate cases.
> Obviously, reversing an empty list or a list with only one element is
> very easy: we have nothing to do. We test for that (line 13) and return
> success immediately if that is the case.
>
> * 13 * * if (l->count < 2)
> * 14 * * * * return 1;
>
> Now, we setup our loop. We start with the first element (that must
> exist since the list has more than one element, line 15). Since we are
> going to reverse the list, the first element will be the last and the
> last will be the first. We setup the last one immediately since we know
> it in line 16. And before we start there is no previous element so we
> set it to NULL.
>
> * 15 * * Next = l->First;
> * 16 * * l->Last = l->First;
> * 17 * * Previous = NULL;
>
> Now we go through the whole list. We save the "Next" value, and advance
> it to the next element. Then, we set the value of the current element's
> pointer to the previous, i.e. our current will point to previous
> reversing the direction of the list.
>
> * 18 * * while (Next) {
> * 19 * * * * Current = Next;
> * 20 * * * * Next = Next->Next;
> * 21 * * * * Current->Next = Previous;
> * 22 * * * * Previous = Current;
> * 23 * * }
>
> OK, we are done. We have gone through the whole list reversing
> pointers, and we arrive at the cleanup. We should first establish our
> "First" pointer, then we should ensure that our last element has
> the Null marker, and that our list is marked as modified. We return a
> positive number meaning success.
>
> * 24 * * l->First = Previous;
> * 25 * * l->Last->Next = NULL;
> * 26 * * l->timestamp++;
> * 27 * * return 1;
> * 28 }


A recursive function is a lot more readable, plus more elegant.

void reverse_list(ListElement *head)
{
if (head == NULL) return;

__reverse_list(head->next, head);

return;
}

void __reverse_list(ListElement *next, ListElement *this)
{
if (this == NULL) return;

if (next->next) __reverse_list(next, next->next);

next->next = this;
return;
}
 
Reply With Quote
 
Ian Collins
Guest
Posts: n/a
 
      09-17-2011
On 09/17/11 11:56 AM, HENRY Eshbaugh wrote:
>
> A recursive function is a lot more readable, plus more elegant.
>
> void reverse_list(ListElement *head)
> {
> if (head == NULL) return;
>
> __reverse_list(head->next, head);


You shouldn't use names starting with a double underscore, they are
reserved for the implementation.

> return;
> }
>
> void __reverse_list(ListElement *next, ListElement *this)
> {
> if (this == NULL) return;
>
> if (next->next) __reverse_list(next, next->next);
>
> next->next = this;
> return;
> }



--
Ian Collins
 
Reply With Quote
 
Tony
Guest
Posts: n/a
 
      09-17-2011

"jacob navia" <(E-Mail Removed)> wrote in message
news:j4uqda$dqt$(E-Mail Removed)...
> This group has lost many people. One of the reasons is that the
> newcomers just ask a question or two, and do not see discussions
> that try to explain code, teaching newcomers to the language how
> a program works.


Wishful thinking? The truth is surely that C/C++ are well within the
black hole now with no chance of escaping its mighty pull.

[snipped "foundations of data structures and algorithms" stuff]

How is "foundations of data structures and algorithms" (via YOUR library,
no less) on topic? Are you not tryig to commandiere this NG to your
personal agenda? Should all library vendors start posting examples in
here about usage of their products? See the point?



 
Reply With Quote
 
Tony
Guest
Posts: n/a
 
      09-17-2011

"Ben Bacarisse" <(E-Mail Removed)> wrote in message
news:0.58bc9b9dbe16eaa00140.20110916125127BST.87sj (E-Mail Removed)...
> jacob navia <(E-Mail Removed)> writes:


>> The first thing to do in a serious program is to check the validity of
>> the received arguments, i.e. test the preconditions as Bertrand Meyer
>> would say it. We test that the list handed to us is not Null (lines
>> 5- and that the list is not read-only (lines 9-12) since we are
>> going to modify it.

>
> This is not what I understand by the phrase "function precondition".
> Maybe Meyer uses it that way but I would be surprised. Almost by
> definition, a precondition is something that you *don't* check.


That would be living dangerously indeed. That kind of programming went
out in the, er, well apparently it hasn't, for you are still doing that!

> It is
> stated in the documentation (and probably as a comment) but as soon as
> you test for it it becomes part of the defined behaviour of the
> function
> and stops being a precondition.


No it doesn't. It just means that when someone violates the precondition,
something controlled and defined happens rather than "anything can
happen". All arguments to public functions need to be verified*.

*Their are techniques that can be used sometimes to ensure that arguments
cannot be wrong and therefore need not be checked. Those functions are
great when you find/create them and worth the effort looking for.

> You can (often during development) use
> something like assert to make sure that your callers are keeping to the
> implied contract of the preconditions, but as soon as this check turns
> into "when l == NULL return error number XYZ" it stops being (at least
> by my understanding of the term) a precondition.


No. (I'm not referring to B. Meyer's definitions though, but rather my
own).

>
> Since this is a teaching exercise,


Of questionable appropriateness in the NG. (Read, I questioned its
appropriateness).


 
Reply With Quote
 
Tony
Guest
Posts: n/a
 
      09-17-2011
ImpalerCore wrote:

> Thank you, that was insightful. To me, it seems like the only
> plausible solution (which I admit is very unlikely to happen) to the
> problem (abstracting a generic linked list interface) is to have some
> kind of "boost" for C, have some part of the library get so popular
> and use its popularity as a springboard to fight to standardize the
> interface. At least there is some evidence that the process can lead
> to a positive impact on changing the C++ standard.
>


Of course, that soon it will be theoretically possible that ALL C users
will be amenable to using one of those "Boost for C" things. It gets more
realistic everyday, for there are less C users everyday. Doesn't "Boost
for C" actually mean, "C++ is right, C is wrong"? The scenario is kind of
like the techie who spends a great deal of his career fighting management
and then becomes "a manager"! Resistance is futile?


 
Reply With Quote
 
Ben Bacarisse
Guest
Posts: n/a
 
      09-17-2011
HENRY Eshbaugh <(E-Mail Removed)> writes:
<snip>
> A recursive function is a lot more readable, plus more elegant.
>
> void reverse_list(ListElement *head)
> {
> if (head == NULL) return;
>
> __reverse_list(head->next, head);
>
> return;
> }
>
> void __reverse_list(ListElement *next, ListElement *this)
> {
> if (this == NULL) return;
>
> if (next->next) __reverse_list(next, next->next);
>
> next->next = this;
> return;
> }


Readable, elegant, correct: pick any two!

--
Ben.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Reversing a singly linked list saki C Programming 2 07-06-2008 06:37 PM
Linked list within a linked list joshd C++ 12 10-02-2006 08:57 AM
Linked list, New try (was:Linked list, no out put,help) fool C Programming 14 07-03-2006 12:29 AM
Generating a char* from a linked list of linked lists Chris Ritchey C++ 7 07-10-2003 10:12 PM
Generating a char* from a linked list of linked lists Chris Ritchey C Programming 7 07-10-2003 10:12 PM



Advertisments