Velocity Reviews - Computer Hardware Reviews

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

Reply
Thread Tools

Reversing a linked list

 
 
Michael Press
Guest
Posts: n/a
 
      09-28-2011
In article <(E-Mail Removed)>,
http://www.velocityreviews.com/forums/(E-Mail Removed) (Richard Harter) wrote:

> On Sat, 17 Sep 2011 07:40:54 +0200, jacob navia <(E-Mail Removed)>
> wrote:
>
> >Le 17/09/11 05:15, Tony a écrit :
> >>>> Maybe at one time lack of argument checking could have been
> >>>> considered a "quality of implementation" issue, but today (and long
> >>>> has been) that is a difference between professional code and
> >>>> Programming 101 student
> >>>> code.
> >>>

> >Ben wrote:
> >
> >>> How do conclude, from what I said, that I am advocating a lack of due
> >>> diligence or not checking arguments?
> >>

> >And Tony answered:
> >> By suggesting that documentation can preclude doing argument checking,
> >> thereby "throwing the problem over the wall" making it the programmer's
> >> problem for not reading "the directions".
> >>
> >>

> >
> >Not all preconditions can be tested. For instance I proposed a routine
> >to test if a list is circular. It involves examining all the list.
> >
> >If a library (like the C Containers library) would do that, its
> >performance would be close to zero.

>
> 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. One could even integrate cycle checking into the reversal
> code. 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.


Here is the canonical linked list reversal.

struct ure
{
struct ure *link;
int data;
};

struct ure *list_head = NULL;

...

/* Build up the linked list. */

...

{
struct ure *tail;

tail = list_head;
list_head = NULL;
for(; tail != NULL; tail = next)
{
struct ure *next;

next = tail->link;
tail->link = list_head;
list_head = tail;
}
}

Given a linked list with a loop, this code terminates;
reversing the cycle, and leaving invariant the
transient and the node that has two nodes pointing at it.

list_head -> a -> b -> c -> d -> e -> c

list_head -> NULL | tail -> a -> b -> c -> d -> e -> c
list_head -> a -> NULL | tail -> b -> c -> d -> e -> c
list_head -> b -> a -> NULL | tail -> c -> d -> e -> c
list_head -> c -> b -> a -> NULL | tail -> d -> e -> c
list_head -> d -> c -> b -> a -> NULL | tail -> e -> c
list_head -> e -> d -> c -> b -> a -> NULL | tail -> c
list_head -> c -> e -> d -> c | tail -> b -> a -> NULL
list_head -> b -> c -> e -> d -> c | tail -> a -> NULL
list_head -> a -> b -> c -> e -> d -> c | tail -> NULL


We can analyze a linked list with a loop in O(1) space
and O(n) time. This is done in three stages using two
separate variables to traverse the list:

Leader
Follower

In Stage 1 we need to test for a NULL that will show
that the linked list is NULL terminated, and prevent
dereferencing NULL.

Stage 1:
L <- list_head
F <- list_head
At each step F traverses one node, and L traverses two
nodes. Eventually we have F = L, and F and L are
pointing at a node in the cycle.

Stage 2:
Save the value of L, then let L traverse nodes until L
is back at its saved value. Now we know the value of c,
the length of the cycle.

Stage 3:
L <- list_head
F <- list_head
Let L traverse c nodes. Now L and F step in tandem, one
node each for each step until L = F. Now L and F point
at the node that has two nodes pointing at it.

--
Michael Press
 
Reply With Quote
 
 
 
 
Tim Rentsch
Guest
Posts: n/a
 
      01-24-2012
James Kuyper <(E-Mail Removed)> writes:

> On 09/20/2011 08:48 PM, henry eshbaugh wrote:
>> On Sep 19, 12:56 pm, Keith Thompson <(E-Mail Removed)> wrote:
>>> The only code it would break is already broken.
>>>
>>> It's completely pointless to use identifiers starting with "__".
>>> By doing so, you risk colliding with identifiers used by the
>>> implementation. By using identifiers that start with letters,
>>> you avoid that risk -- at no cost.
>>>
>>> I don't *care* whether any compilers use the name "__foo" internally,
>>> because I don't define reserved identifiers in my own code.
>>>
>>> Exactly what benefit do you get by calling your own function "__foo"
>>> (rather than, say, "foo__")?
>>>
>>> You have a choice between writing code with well defined behavior and
>>> writing code with undefined behavior. Why do you chose the latter?

>>
>> It's a coding style issue. I use them for internal functions.

>
> "coding style" is not a term ordinarily used to describe deliberate
> adoption of practices that, according to the C standard, have undefined
> behavior.
>
>> And it's not just me. You know who else happens to do that? The small
>> army of Linux kernel programmers.

>
> Guess what: the Linux kernal is part of a C implementation. [snip]


No, it isn't. A Linux _distribution_ may include parts of
a C implmentation, but just the kernel does not.
 
Reply With Quote
 
 
 
 
Tim Rentsch
Guest
Posts: n/a
 
      01-24-2012
Ben Bacarisse <(E-Mail Removed)> writes:

> Keith Thompson <(E-Mail Removed)> writes:
>
>> Phil Carmody <(E-Mail Removed)> writes:
>>> henry eshbaugh <(E-Mail Removed)> writes:
>>>> > "coding style" is not a term ordinarily used to describe deliberate
>>>> > adoption of practices that, according to the C standard, have undefined
>>>> > behavior.
>>>>
>>>> I used a term where you didn't expect to see it. Deal with it.
>>>>
>>>> > Guess what: the Linux kernal is part of a C implementation. The key
>>>> > reason why you're not supposed to use these names is because they ARE
>>>> > supposed to use them. They're NOT supposed to use the names that are
>>>> > reserved for your use.
>>>>
>>>> The Linux kernel is _not_ a C implementation. Glibc is a C
>>>> implementation.
>>>
>>> You think the linux kernel links to glibc? So you believe that
>>> kernel code could just include a call to, say strtok(), and
>>> that would get resolved to glibc's implementation?

>>
>> [...]
>>
>> I didn't see anything in what henry eshbaugh wrote that implies
>> that the Linux kernel links to glibc. He was merely refuting
>> (correctly, I believe) someone else's claim that the kernel is part
>> of a C implementation.

>
> This is tangential to the issue of reserved identifiers, but I've always
> thought of the kernel as part of a C implementation. A (possibly naive)
> reading of this definition:
>
> 3.12
> 1 implementation
>
> particular set of software, running in a particular translation
> environment under particular control options, that performs
> translation of programs for, and supports execution of functions in,
> a particular execution environment
>
> seems to support that view. I would have said that the kernel (of the
> compiler's target system, of course) "supports execution of functions
> in, a particular execution environment".


That's for things like the standard library. A kernel _provides_
an execution environment, but nothing in it is particular or specific
to C. Rather, it is part of a system that may support a conforming
implemention, as mentioned in 1 p2 (last bullet item).
 
Reply With Quote
 
Tim Rentsch
Guest
Posts: n/a
 
      01-24-2012
Phil Carmody <(E-Mail Removed)> writes:

> Keith Thompson <(E-Mail Removed)> writes:
>> Phil Carmody <(E-Mail Removed)> writes:
>> > henry eshbaugh <(E-Mail Removed)> writes:
>> >> > "coding style" is not a term ordinarily used to describe deliberate
>> >> > adoption of practices that, according to the C standard, have undefined
>> >> > behavior.
>> >>
>> >> I used a term where you didn't expect to see it. Deal with it.
>> >>
>> >> > Guess what: the Linux kernal is part of a C implementation. The key
>> >> > reason why you're not supposed to use these names is because they ARE
>> >> > supposed to use them. They're NOT supposed to use the names that are
>> >> > reserved for your use.
>> >>
>> >> The Linux kernel is _not_ a C implementation. Glibc is a C
>> >> implementation.
>> >
>> > You think the linux kernel links to glibc? So you believe that
>> > kernel code could just include a call to, say strtok(), and
>> > that would get resolved to glibc's implementation?

>>
>> [...]
>>
>> I didn't see anything in what henry eshbaugh wrote that implies
>> that the Linux kernel links to glibc. He was merely refuting
>> (correctly, I believe) someone else's claim that the kernel is part
>> of a C implementation.

>
> The kernel contains part of a C implementation at least as much
> as glibc does. Henry magically disappeared the word "part of" in
> his response. 'is' was perhaps overstating the claim, but there
> is undeniably C implementation in the linux kernel (e.g. in the
> include and lib directories).


A Linux distribution can include parts of a C implementation;
a Linux kernel does not.
 
Reply With Quote
 
Phil Carmody
Guest
Posts: n/a
 
      02-11-2012
Tim Rentsch <(E-Mail Removed)> writes:
> Phil Carmody <(E-Mail Removed)> writes:
> > Keith Thompson <(E-Mail Removed)> writes:
> >> Phil Carmody <(E-Mail Removed)> writes:
> >> > henry eshbaugh <(E-Mail Removed)> writes:
> >> >> > "coding style" is not a term ordinarily used to describe deliberate
> >> >> > adoption of practices that, according to the C standard, have undefined
> >> >> > behavior.
> >> >>
> >> >> I used a term where you didn't expect to see it. Deal with it.
> >> >>
> >> >> > Guess what: the Linux kernal is part of a C implementation. The key
> >> >> > reason why you're not supposed to use these names is because they ARE
> >> >> > supposed to use them. They're NOT supposed to use the names that are
> >> >> > reserved for your use.
> >> >>
> >> >> The Linux kernel is _not_ a C implementation. Glibc is a C
> >> >> implementation.
> >> >
> >> > You think the linux kernel links to glibc? So you believe that
> >> > kernel code could just include a call to, say strtok(), and
> >> > that would get resolved to glibc's implementation?
> >>
> >> [...]
> >>
> >> I didn't see anything in what henry eshbaugh wrote that implies
> >> that the Linux kernel links to glibc. He was merely refuting
> >> (correctly, I believe) someone else's claim that the kernel is part
> >> of a C implementation.

> >
> > The kernel contains part of a C implementation at least as much
> > as glibc does. Henry magically disappeared the word "part of" in
> > his response. 'is' was perhaps overstating the claim, but there
> > is undeniably C implementation in the linux kernel (e.g. in the
> > include and lib directories).

>
> A Linux distribution can include parts of a C implementation;
> a Linux kernel does not.


The one I maintain for ${DAYJOB} does. And as I pull from Greg KH's
tree, I think I can speak for his one too, and almost certainly Linus's.
Did you have some other Linux kernel in mind?.

Phil
--
Unix is simple. It just takes a genius to understand its simplicity
-- Dennis Ritchie (1941-2011), Unix Co-Creator
 
Reply With Quote
 
Tim Rentsch
Guest
Posts: n/a
 
      03-08-2012
Phil Carmody <(E-Mail Removed)> writes:

> Tim Rentsch <(E-Mail Removed)> writes:
>> Phil Carmody <(E-Mail Removed)> writes:
>> > Keith Thompson <(E-Mail Removed)> writes:
>> >> Phil Carmody <(E-Mail Removed)> writes:
>> >> > henry eshbaugh <(E-Mail Removed)> writes:
>> >> >> > "coding style" is not a term ordinarily used to describe deliberate
>> >> >> > adoption of practices that, according to the C standard, have undefined
>> >> >> > behavior.
>> >> >>
>> >> >> I used a term where you didn't expect to see it. Deal with it.
>> >> >>
>> >> >> > Guess what: the Linux kernal is part of a C implementation. The key
>> >> >> > reason why you're not supposed to use these names is because they ARE
>> >> >> > supposed to use them. They're NOT supposed to use the names that are
>> >> >> > reserved for your use.
>> >> >>
>> >> >> The Linux kernel is _not_ a C implementation. Glibc is a C
>> >> >> implementation.
>> >> >
>> >> > You think the linux kernel links to glibc? So you believe that
>> >> > kernel code could just include a call to, say strtok(), and
>> >> > that would get resolved to glibc's implementation?
>> >>
>> >> [...]
>> >>
>> >> I didn't see anything in what henry eshbaugh wrote that implies
>> >> that the Linux kernel links to glibc. He was merely refuting
>> >> (correctly, I believe) someone else's claim that the kernel is part
>> >> of a C implementation.
>> >
>> > The kernel contains part of a C implementation at least as much
>> > as glibc does. Henry magically disappeared the word "part of" in
>> > his response. 'is' was perhaps overstating the claim, but there
>> > is undeniably C implementation in the linux kernel (e.g. in the
>> > include and lib directories).

>>
>> A Linux distribution can include parts of a C implementation;
>> a Linux kernel does not.

>
> The one I maintain for ${DAYJOB} does. And as I pull from Greg KH's
> tree, I think I can speak for his one too, and almost certainly Linus's.
> Did you have some other Linux kernel in mind?.


I think we're talking about two different things. What I
think you are talking about is maintaining (part of) a C
implementation as part of Linux kernel /sources/. What I am
talking about is a Linux kernel /executable/, ie, a boot
image. Certainly I can believe that you work on, eg,
various standard header files, as part of work on kernel
source files. However, that has no bearing on whether (part
of) a C implemention is provided by a Linux boot image;
normally all the various C-implementation parts are just
files scattered around the file system of a distribution --
nothing comes directly out of the actual boot image.

It's possible of course that some of the C implementation source
files you work on get shipped along with the boot image, to make
up part of an implementation in that distribution (using
"shipped" and "distribution" as appropriate to your environment).
That still doesn't make them part of the boot image, even if it
happens to be true that both sets of source files were worked on
in concert and simultaneously. All that matters is where the
various pieces of an implementation come from, and normally all
those pieces come out of the file system of the distribution, not
out of the kernel boot image.

Does that make more sense now?
 
Reply With Quote
 
Phil Carmody
Guest
Posts: n/a
 
      03-13-2012
Tim Rentsch <(E-Mail Removed)> writes:
> Phil Carmody <(E-Mail Removed)> writes:
> I think we're talking about two different things.

....
> Does that make more sense now?


It does, yes; thanks for the clarification.

Phil
--
> I'd argue that there is much evidence for the existence of a God.

Pics or it didn't happen.
-- Tom (/. uid 822)
 
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