Re: Reversing a linked list

From	jacob navia <jacob@spamsink.net>
Newsgroups	comp.lang.c
Subject	Re: Reversing a linked list
Date	2011-09-17 17:47 +0200
Organization	lccwin
Message-ID	<j52ff0$qej$1@speranza.aioe.org> (permalink)
References	<j4uqda$dqt$1@speranza.aioe.org><0.58bc9b9dbe16eaa00140.20110916125127BST.87sjnwyabk.fsf@bsb.me.uk><j4vept$ok$1@speranza.aioe.org><0.552aade6637246f13e43.20110916215650BST.871uvgxl2l.fsf@bsb.me.uk><3yScq.15582$Ll3.5918@newsfe16.iad> <0.87f686ca631b2d0e9de9.20110917024813BST.87aaa4vt0i.fsf@bsb.me.uk> <9hUcq.6223$bp5.4990@newsfe22.iad> <j51bt5$3kg$1@speranza.aioe.org> <4e74a735.162351176@text.giganews.com>

Show all headers | View raw

Le 17/09/11 17:07, Richard Harter a écrit :
>
> Well, no, it wouldn't.  The cost of checking whether a linked list
> terminates in a cycle is of the same order as the cost of reversing
> the list.

Yes.

>  One could even integrate cycle checking into the reversal
> code.

This is a VERY good idea, I didn't even think about that but now
that you mention it, it is obvious.

Easy since we have already one pointer that goes through the list. We
could setup a second pointer, incrementing it twice as fast. This
would cost for a list of length N:

1) A test for pointer equality (N times)
2) A conditional jump (N times)
3) A test for NULL (N / 2 times)
4) An extra pointer dereferencing. (N / 2 times)

In a modern machine with a pipeline depth of 32 instructions (say)
the 1 and 2 would cost not even a cycle since the conditional branch
would be correctly predicted. For a pipeline depth of 32 it would
cost (2/32 --> 1/16 cycle)

The same analysis for 3: also a cost of 1/16 makes 1/8 cycle for
a pipeline depth of 32.

For 4 we have the extra cost of loading a cache line when
the "next" pointer dereferences data that is not in the cache.

For the worst case when the list is too big to fit into the L1 or L2
caches (several MB) we would double the cost of loading the list into
the cache, probably doubling the running time or more.

Mmmmmm... That would be the real show stopper.

> If one does that one could also reverse a cycle terminated
> linked list by defining the new head as the node that joined the
> cycle.  I don't suppose you would want to do that but it could be done
> cheaply enough.
>

More or less, see the analysis above. But it is a very good idea. I will
integrate it into the solved exercises.


Thank you very much for this contribution.

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