Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #10328

Re: Reversing a linked list

From jacob navia <jacob@spamsink.net>
Newsgroups comp.lang.c
Subject Re: Reversing a linked list
Date 2011-09-16 16:47 +0200
Organization lccwin
Message-ID <j4vnhd$nrf$1@speranza.aioe.org> (permalink)
References <j4uqda$dqt$1@speranza.aioe.org> <0.58bc9b9dbe16eaa00140.20110916125127BST.87sjnwyabk.fsf@bsb.me.uk> <51096d0a-12c9-4eb2-9b85-cd42c2c79513@r21g2000yqr.googlegroups.com>

Show all headers | View raw

Le 16/09/11 16:21, ImpalerCore a écrit :
>  From my perspective, a precondition for a function is independent of
> the method used to handle its violations.  This is what contrasts the
> defensive programming from the design by contract paradigm.  They both
> see the same function preconditions; they respond to them differently.
>

I would agree with that. For instance, "Reverse" needs a list with no
cycles.

It would be hugely expensive to test this precondition (I gave the code
for the test in an answer to Ben) since implies going through all the
list. But you are right that all the preconditions should be explicitely
documented, even if untested in the code.

The other precondition is that the list must be terminated by a NULL
pointer and all the Next pointer must be valid.

The first part can be easily tested with:

if (l->count > 0) assert(l->Last->Next == NULL);

This is cheap to do because the header structure stores a pointer
to the last element. But if there is no pointer to the last element
we have to go through the whole list, what makes testing for that
precondition extremely expensive.

I will add a commentary with this content to the preconditions
part.

Thanks for your input.

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Reversing a linked list jacob navia <jacob@spamsink.net> - 2011-09-16 08:30 +0200
  Re: Reversing a linked list jacob navia <jacob@spamsink.net> - 2011-09-16 08:33 +0200
  Re: Reversing a linked list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-09-16 12:51 +0100
    Re: Reversing a linked list jacob navia <jacob@spamsink.net> - 2011-09-16 14:18 +0200
      Re: Reversing a linked list jacob navia <jacob@spamsink.net> - 2011-09-16 14:26 +0200
        Re: Reversing a linked list Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-09-16 07:09 -0700
          Re: Reversing a linked list ImpalerCore <jadill33@gmail.com> - 2011-09-16 08:28 -0700
            Re: Reversing a linked list falk@rahul.net (Edward A. Falk) - 2011-09-16 16:34 +0000
            Re: Reversing a linked list Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-09-16 09:28 -0700
              Re: Reversing a linked list ImpalerCore <jadill33@gmail.com> - 2011-09-16 11:12 -0700
                Re: Reversing a linked list "Tony" <nospamme@ever.net> - 2011-09-16 20:01 -0500
      Re: Reversing a linked list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-09-16 21:56 +0100
        Re: Reversing a linked list "Tony" <nospamme@ever.net> - 2011-09-16 20:16 -0500
          Re: Reversing a linked list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-09-17 02:48 +0100
            Re: Reversing a linked list "Tony" <nospamme@ever.net> - 2011-09-16 22:15 -0500
              Re: Reversing a linked list jacob navia <jacob@spamsink.net> - 2011-09-17 07:40 +0200
                Re: Reversing a linked list "Tony" <nospamme@ever.net> - 2011-09-17 01:24 -0500
                Re: Reversing a linked list cri@tiac.net (Richard Harter) - 2011-09-17 15:07 +0000
                Re: Reversing a linked list jacob navia <jacob@spamsink.net> - 2011-09-17 17:47 +0200
                Re: Reversing a linked list jacob navia <jacob@spamsink.net> - 2011-09-17 17:54 +0200
                Re: Reversing a linked list Michael Press <rubrum@pacbell.net> - 2011-09-27 19:21 -0700
              Re: Reversing a linked list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-09-17 12:00 +0100
                Re: Reversing a linked list "Tony" <nospamme@ever.net> - 2011-09-17 23:53 -0500
    Re: Reversing a linked list ImpalerCore <jadill33@gmail.com> - 2011-09-16 07:21 -0700
      Re: Reversing a linked list jacob navia <jacob@spamsink.net> - 2011-09-16 16:47 +0200
        Re: Reversing a linked list Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-09-16 08:20 -0700
        Re: Reversing a linked list "Tony" <nospamme@ever.net> - 2011-09-16 20:25 -0500
      Re: Reversing a linked list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-09-16 22:32 +0100
      Re: Reversing a linked list pete <pfiland@mindspring.com> - 2011-09-16 17:53 -0400
    Re: Reversing a linked list "Tony" <nospamme@ever.net> - 2011-09-16 19:48 -0500
      Re: Reversing a linked list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-09-17 02:41 +0100
        Re: Reversing a linked list "Tony" <nospamme@ever.net> - 2011-09-16 22:57 -0500
          Re: Reversing a linked list "BartC" <bc@freeuk.com> - 2011-09-17 12:48 +0100
            Re: Reversing a linked list jacob navia <jacob@spamsink.net> - 2011-09-17 13:55 +0200
            Re: Reversing a linked list "Tony" <nospamme@ever.net> - 2011-09-17 23:39 -0500
  Re: Reversing a linked list HENRY Eshbaugh <henryeshbaugh@gmail.com> - 2011-09-16 16:56 -0700
    Re: Reversing a linked list Ian Collins <ian-news@hotmail.com> - 2011-09-17 12:09 +1200
      Re: Reversing a linked list HENRY Eshbaugh <henryeshbaugh@gmail.com> - 2011-09-16 19:53 -0700
        Re: Reversing a linked list "Tony" <nospamme@ever.net> - 2011-09-16 23:00 -0500
          Re: Reversing a linked list Jonathan Leffler <jleffler@earthlink.net> - 2011-09-16 23:20 -0700
          Re: Reversing a linked list Keith Thompson <kst-u@mib.org> - 2011-09-17 13:46 -0700
            Re: Reversing a linked list henry eshbaugh <henryeshbaugh@gmail.com> - 2011-09-17 19:51 -0700
              Re: Reversing a linked list Keith Thompson <kst-u@mib.org> - 2011-09-18 01:28 -0700
                Re: Reversing a linked list henry eshbaugh <henryeshbaugh@gmail.com> - 2011-09-18 15:39 -0700
                Re: Reversing a linked list Kleuskes & Moos <kleuske@somewhere.else.net> - 2011-09-18 22:43 +0000
                Re: Reversing a linked list henry eshbaugh <henryeshbaugh@gmail.com> - 2011-09-18 17:54 -0700
                Re: Reversing a linked list James Kuyper <jameskuyper@verizon.net> - 2011-09-18 21:20 -0400
                Re: Reversing a linked list Keith Thompson <kst-u@mib.org> - 2011-09-18 17:30 -0700
                Re: Reversing a linked list henry eshbaugh <henryeshbaugh@gmail.com> - 2011-09-18 17:51 -0700
                Re: Reversing a linked list James Kuyper <jameskuyper@verizon.net> - 2011-09-18 21:34 -0400
                Re: Reversing a linked list Robert Wessel <robertwessel2@yahoo.com> - 2011-09-18 21:25 -0500
                Re: Reversing a linked list Keith Thompson <kst-u@mib.org> - 2011-09-19 09:56 -0700
                Re: Reversing a linked list gazelle@shell.xmission.com (Kenny McCormack) - 2011-09-19 17:16 +0000
                Re: Reversing a linked list Willem <willem@toad.stack.nl> - 2011-09-19 17:25 +0000
                Re: Reversing a linked list Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-09-19 23:40 -0700
                Re: Reversing a linked list henry eshbaugh <henryeshbaugh@gmail.com> - 2011-09-20 17:55 -0700
                Re: Reversing a linked list henry eshbaugh <henryeshbaugh@gmail.com> - 2011-09-20 17:48 -0700
                Re: Reversing a linked list Geoff <geoff@invalid.invalid> - 2011-09-20 19:12 -0700
                Re: Reversing a linked list henry eshbaugh <henryeshbaugh@gmail.com> - 2011-09-21 10:15 -0700
                Re: Reversing a linked list David Resnick <lndresnick@gmail.com> - 2011-09-22 08:43 -0700
                Re: Reversing a linked list Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-09-23 02:45 -0700
                Re: Reversing a linked list David Resnick <lndresnick@gmail.com> - 2011-09-23 05:38 -0700
                Re: Reversing a linked list Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-09-23 07:58 -0700
                Re: Reversing a linked list David Resnick <lndresnick@gmail.com> - 2011-09-23 08:15 -0700
                Re: Reversing a linked list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-09-23 18:00 +0100
                Re: Reversing a linked list David Resnick <lndresnick@gmail.com> - 2011-09-23 10:49 -0700
                Re: Reversing a linked list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-09-23 20:05 +0100
                Re: Reversing a linked list pete <pfiland@mindspring.com> - 2011-09-23 18:05 -0400
                Re: Reversing a linked list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-09-24 00:19 +0100
                Re: Reversing a linked list ImpalerCore <jadill33@gmail.com> - 2011-09-23 09:25 -0700
                Re: Reversing a linked list Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-09-22 22:49 +0300
                Re: Reversing a linked list Keith Thompson <kst-u@mib.org> - 2011-09-20 19:51 -0700
                Re: Reversing a linked list henry eshbaugh <henryeshbaugh@gmail.com> - 2011-09-21 09:51 -0700
                Re: Reversing a linked list Keith Thompson <kst-u@mib.org> - 2011-09-21 11:21 -0700
                Re: Reversing a linked list James Kuyper <jameskuyper@verizon.net> - 2011-09-20 23:00 -0400
                Re: Reversing a linked list henry eshbaugh <henryeshbaugh@gmail.com> - 2011-09-21 09:47 -0700
                Re: Reversing a linked list Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-09-23 11:22 +0300
                Re: Reversing a linked list Keith Thompson <kst-u@mib.org> - 2011-09-23 08:20 -0700
                Re: Reversing a linked list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-09-23 18:12 +0100
                Re: Reversing a linked list Tim Rentsch <txr@alumni.caltech.edu> - 2012-01-24 13:13 -0800
                Re: Reversing a linked list Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-09-23 23:49 +0300
                Re: Reversing a linked list James Kuyper <jameskuyper@verizon.net> - 2011-09-24 08:15 -0400
                Re: Reversing a linked list Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-09-24 20:15 +0300
                Re: Reversing a linked list Tim Rentsch <txr@alumni.caltech.edu> - 2012-01-24 13:28 -0800
                Re: Reversing a linked list Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-02-12 01:41 +0200
                Re: Reversing a linked list Tim Rentsch <txr@alumni.caltech.edu> - 2012-03-08 09:08 -0800
                Re: Reversing a linked list Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-03-13 17:21 +0200
                Re: Reversing a linked list Tim Rentsch <txr@alumni.caltech.edu> - 2012-01-24 13:04 -0800
                Re: Reversing a linked list Seebs <usenet-nospam@seebs.net> - 2011-09-23 01:46 +0000
                Re: Reversing a linked list James Kuyper <jameskuyper@verizon.net> - 2011-09-18 21:17 -0400
            Re: Reversing a linked list "Tony" <nospamme@ever.net> - 2011-09-17 23:50 -0500
              Re: Reversing a linked list Keith Thompson <kst-u@mib.org> - 2011-09-18 01:29 -0700
        Re: Reversing a linked list Seebs <usenet-nospam@seebs.net> - 2011-09-18 07:03 +0000
    Re: Reversing a linked list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-09-17 02:13 +0100
      Re: Reversing a linked list HENRY Eshbaugh <henryeshbaugh@gmail.com> - 2011-09-16 19:52 -0700
        Re: Reversing a linked list Willem <willem@toad.stack.nl> - 2011-09-17 08:58 +0000
          Re: Reversing a linked list henry eshbaugh <henryeshbaugh@gmail.com> - 2011-09-18 15:32 -0700
            Re: Reversing a linked list James Kuyper <jameskuyper@verizon.net> - 2011-09-18 21:36 -0400
              Re: Reversing a linked list cri@tiac.net (Richard Harter) - 2011-09-19 05:24 +0000
                Re: Reversing a linked list James Kuyper <jameskuyper@verizon.net> - 2011-09-19 08:21 -0400
                Re: Reversing a linked list cri@tiac.net (Richard Harter) - 2011-09-19 14:28 +0000
                Re: Reversing a linked list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-09-19 17:01 +0100
                Re: Reversing a linked list cri@tiac.net (Richard Harter) - 2011-09-19 16:25 +0000
                Re: Reversing a linked list henry eshbaugh <henryeshbaugh@gmail.com> - 2011-09-21 10:41 -0700
                Re: Reversing a linked list Kleuskes & Moos <kleuske@somewhere.else.net> - 2011-09-21 17:58 +0000
                Re: Reversing a linked list James Kuyper <jameskuyper@verizon.net> - 2011-09-21 14:07 -0400
                Re: Reversing a linked list Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-09-21 11:15 -0700
                Re: Reversing a linked list Keith Thompson <kst-u@mib.org> - 2011-09-21 11:37 -0700
                Re: Reversing a linked list Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-09-23 11:50 +0300
                Re: Reversing a linked list Seebs <usenet-nospam@seebs.net> - 2011-09-23 01:46 +0000
    Re: Reversing a linked list Geoff <geoff@invalid.invalid> - 2011-09-18 18:22 -0700
  Re: Reversing a linked list "Tony" <nospamme@ever.net> - 2011-09-16 19:37 -0500
    Re: Reversing a linked list jacob navia <jacob@spamsink.net> - 2011-09-17 07:52 +0200
      Re: Reversing a linked list "Tony" <nospamme@ever.net> - 2011-09-17 02:09 -0500
        Re: Reversing a linked list Ian Collins <ian-news@hotmail.com> - 2011-09-17 19:35 +1200
          Re: Reversing a linked list "Tony" <nospamme@ever.net> - 2011-09-17 03:35 -0500
        Programming languages jacob navia <jacob@spamsink.net> - 2011-09-17 22:14 +0200
          Re: Programming languages "Tony" <nospamme@ever.net> - 2011-09-18 00:11 -0500
            Re: Programming languages jacob navia <jacob@spamsink.net> - 2011-09-18 08:37 +0200
            Re: Programming languages Seebs <usenet-nospam@seebs.net> - 2011-09-18 07:03 +0000
              Re: Programming languages jacob navia <jacob@spamsink.net> - 2011-09-18 09:50 +0200
              Re: Programming languages Keith Thompson <kst-u@mib.org> - 2011-09-18 01:31 -0700
                Re: Programming languages James Kuyper <jameskuyper@verizon.net> - 2011-09-18 06:43 -0400
                Re: Programming languages Nick Keighley <nick_keighley_nospam@hotmail.com> - 2011-09-18 07:42 -0700
                Re: Programming languages "Tony" <nospamme@ever.net> - 2011-09-18 04:05 -0500
            Re: Programming languages Nick Keighley <nick_keighley_nospam@hotmail.com> - 2011-09-18 07:40 -0700
  Re: Reversing a linked list Gene <gene.ressler@gmail.com> - 2011-09-22 06:59 -0700

csiph-web