pruning a linear singly linked list

[Anando]

Hi,

I have a linear singly linked list of 100 elements. I would like to
prune it [i.e delete some nodes] such that only user specified elements
(say only the elements 1, 13, 78 and 100 of the original list) survive
after pruning.

Can somebody show me how to do this ? I am a scientist and not a
computer engineer/student. This will help me develop an application in
data analysis. I will be grateful for your advice.

Cheers,
Anand.

 

[Nick Keighley]

Anando wrote:

this is an algorithm (programming technique) question rather
than a strictly C question. Therefore it would be better asked
on comp.programming

I have a linear singly linked list of 100 elements. I would like to
prune it [i.e delete some nodes] such that only user specified elements
(say only the elements 1, 13, 78 and 100 of the original list) survive
after pruning.

life would be easier with a doubly linked list (that only takes another

100 pointer variables with your example). But if you have use a SLL
you'll need to walk two pointers down the list one to point at the
current
node one to point to its predessor. Then chop out the ones you want.
It may make more sense to seek out the required nodes (1, 13, 78, 100)
and copy them to a new list, then destroy the old.

Can somebody show me how to do this ? I am a scientist and not a
computer engineer/student. This will help me develop an application in
data analysis. I will be grateful for your advice.

--
Nick Keighley

We recommend, rather, that users take advantage of the extensions of
GNU C and disregard the limitations of other compilers. Aside from
certain supercomputers and obsolete small machines, there is less
and less reason ever to use any other C compiler other than for
bootstrapping GNU CC.
(Using and Porting GNU CC)

 

[Anando]

Hi

Thanks for your algorithm. I was thinking of the copy to new list and
destroy old list as well - but when I copied the data it was a shallow
copy (i.e the data in the structure was not copied). Is it possible to
use memcpy or something to copy - if so could you please give a small
example of copying an element such that the data is also copied ?

Many thanks,
Anand.

 

[Bill Pursell]

Nick Keighley' signature contains:

We recommend, rather, that users take advantage of the extensions of
GNU C and disregard the limitations of other compilers. Aside from
certain supercomputers and obsolete small machines, there is less
and less reason ever to use any other C compiler other than for
bootstrapping GNU CC.

I would love to see some discussions about this. I'm constantly
changing my mind about whether or not to use extensions. I most
recently decided to start using extensions, marking them with
__extension__, and stop worrying about it. But I keep worrying about
it. At the moment, the only extensions I'm using are trivial-- enums
with trailing commas, unnamed unions within structures (Am I correct in
calling that trivial?), and very rarely the typeof keyword. I work
exclusively with gcc, and although I'm trying to remain within
standards, the only enforcement mechanism I really have is -pedantic,
so for all I know all of my efforts to be completely standard are
wasted. I'd like to start using typeof more often, but am reluctant to
do so. Is there a way to deteremine which extensions are considered
more acceptable (ie more likely to be incorporated into the standard)
than others?

 

[Ben C]

Nick Keighley' signature contains:


I would love to see some discussions about this. I'm constantly
changing my mind about whether or not to use extensions. I most
recently decided to start using extensions, marking them with
__extension__, and stop worrying about it. But I keep worrying about
it. At the moment, the only extensions I'm using are trivial-- enums
with trailing commas, unnamed unions within structures (Am I correct in
calling that trivial?), and very rarely the typeof keyword. I work
exclusively with gcc, and although I'm trying to remain within
standards, the only enforcement mechanism I really have is -pedantic,

You can use -ansi with gcc, and also -std=c99 or -std=c89

 

[Flash Gordon]

You can use -ansi with gcc, and also -std=c99 or -std=c89

If you want it to attempt to conform to the standard you need both -ansi
(or -std=c89 or -stdc=c99) and -pedantic, however even with that it
still doesn't conform to C99.

Personally I believe one should in general avoid extensions. There are
times when they are required or provide enough benefit to be work it,
but a lot of time they are not.

 

[Nick Keighley]

Nick Keighley' signature contains:

my warped sense of humour catches up with again...

*I* find it amusing that GNU of all "organisations" would be
encouraging
the usage of non-standard extensions. We criticise Microsoft et al for
"extending" standards and hence locking customers in. The same applies
to GNU extensions (and I'm not entirely convinced the motives are any
purer)

I would love to see some discussions about this. I'm constantly
changing my mind about whether or not to use extensions.

I'm at the "extensions are Evil, they rot your teeth, they make your
hair
fall out" end of the spectrum. To be more realistic extensions of some
sort
are always necessary in real world programs. I'd prefer libraries over
compiler extensions and try to confine such extensions to their own
module.

I most recently decided to start using extensions,

just the occaisional use isnt a problem after all you can give up any
time (like heroin )

marking them with __extension__,

eek! That's an identifier in implementation space.

and stop worrying about it. But I keep worrying about
it. At the moment, the only extensions I'm using are trivial-- enums
with trailing commas, unnamed unions within structures (Am I correct in
calling that trivial?),

One I had an argument about was a "flattened" union

So

union A
{
union B
{
int c;
}
};

(apologies if I got the syntax wrong I don't use unions...). With this
extension you could access c with both A.B.c and A.c. The other party
argued "well it's there and it's useful so why not use it?" to my "If
you
can avoid an extension then do so". I work on systems that can outlive
their hardware so I consider this a wise course.

and very rarely the typeof keyword. I work
exclusively with gcc, and although I'm trying to remain within
standards, the only enforcement mechanism I really have is -pedantic,
so for all I know all of my efforts to be completely standard are
wasted. I'd like to start using typeof more often, but am reluctant to
do so. Is there a way to deteremine which extensions are considered
more acceptable (ie more likely to be incorporated into the standard)
than others?

I suppose you could take a look at the standard's comitee stuff. Bear
in mind
that a fair amount of C99 stuff is still not widely available

I recently revived an old program I wrote for Windows. The only problem

was I'd used Turbo C and just tucked in a few extensions... Microsoft
had also discontinued support for some calls. I did get it running
again
but things could have been smoother.


--
Nick Keighley

Programming should never be boring, because anything mundane and
repetitive should be done by the computer.
~Alan Turing

 

[Andrew Poelstra]

Hi

Thanks for your algorithm. I was thinking of the copy to new list and
destroy old list as well - but when I copied the data it was a shallow
copy (i.e the data in the structure was not copied). Is it possible to
use memcpy or something to copy - if so could you please give a small
example of copying an element such that the data is also copied ?

Many thanks,
Anand.

Please remember to quote the post above you; Usenet is not a message board.

Let's assume that you have a struct with 3 variables:
struct data {
int a;
int b;
int c;
}

And within your list you have a pointer to such a struct:
struct data *node;

To memcpy one of these nodes, you must:
1) Allocate the space:
struct data *cp_node = malloc (sizeof (struct data))
if (cp_node == NULL)
{
/* In case you can't get enough memory, do something here */
}

2) Copy it over:
memcpy (cp_node, node, sizeof(struct node);

 

[Laurijssen]

*I* find it amusing that GNU of all "organisations" would be
encouraging
the usage of non-standard extensions. We criticise Microsoft et al for
"extending" standards and hence locking customers in. The same applies
to GNU extensions (and I'm not entirely convinced the motives are any
purer)

many extensions in gcc indeed, i guess gcc being non commercial makes it not
evil

 

[jacob navia]

Nick Keighley a écrit :

Bill Pursell wrote:

I'm at the "extensions are Evil, they rot your teeth, they make your
hair
fall out" end of the spectrum.

Yes but, as you say in the next line:

To be more realistic extensions of some
sort
are always necessary in real world programs.

There you are. Extensions ARE needed, and all languages and improvements
of software were born as extensions of some other stuff.

The C language?

Was an "extension" of BCPL,

C++?

Extension of C

Etc etc.

[snip]

One I had an argument about was a "flattened" union

So

union A
{
union B
{
int c;
}
};

(apologies if I got the syntax wrong I don't use unions...). With this
extension you could access c with both A.B.c and A.c.

This is a very useful extension, one that I have included also in the
lcc-win32 compiler. As you can see useful extensions are that: USEFUL
and they tend to be copied by other compiler, and eventually they make
it into the standard, if the commitee agrees on "existing practice"...


The other party

argued "well it's there and it's useful so why not use it?" to my "If
you
can avoid an extension then do so". I work on systems that can outlive
their hardware so I consider this a wise course.

It is a stupid course because:

If you change the layout of the structures you have to modify ALL THOSE
LINES in your code that access that particular field!!!!!

Instead of all that work, your code A.c still works NO MATTER WHERE in
the structure you change the layout!

You understand now?

Extensions are NOT just evil stuff that compiler writers find out to
"lock their users in" but are USEFUL for certain situations!

jacob

 

[Keith Thompson]

Nick Keighley' signature contains:


I would love to see some discussions about this. I'm constantly
changing my mind about whether or not to use extensions. I most
recently decided to start using extensions, marking them with
__extension__, and stop worrying about it. But I keep worrying about
it. At the moment, the only extensions I'm using are trivial-- enums
with trailing commas, unnamed unions within structures (Am I correct in
calling that trivial?), and very rarely the typeof keyword.

[snip]

C99 allows a trailing comma on an enumerator list.

 

[CBFalconer]

many extensions in gcc indeed, i guess gcc being non commercial
makes it not evil

Notwithstanding the fact that some over enthusiastic writers
recommend using those extensions, the fact is that GNU makes it
easy to avoid them and use standards conformant coding practices.
Microsoft makes it hard. I recall that on VC6 one couldn't turn up
the warning level without having the system headers fill the error
messages.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>

 

[CBFalconer]

Nick Keighley a écrit :
.... snip ...

This is a very useful extension, one that I have included also
in the lcc-win32 compiler. As you can see useful extensions are
that: USEFUL and they tend to be copied by other compiler, and
eventually they make it into the standard, if the commitee
agrees on "existing practice"...

No, this is a purposeless extension, only useful to convert
portable code into non-portable code. It doesn't allow you to do
anything you couldn't do without it. As has been said, it "will
make your hair fall out, and will rot your teeth".

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>

 

[jacob navia]

Keith Thompson a écrit :

C99 allows a trailing comma on an enumerator list.

What was before an extension is now in the standard.

Why?

Because people used the extension, and didn't have the conservative
attitude is promoted here, where any innovation is treated as an heresy,
even in the most trivial cases.

jacob

 

[Richard Heathfield]

jacob navia said:

Keith Thompson a écrit :


What was before an extension is now in the standard.

Why?

No idea. It's a completely pointless extension. The only reason I can think
of for it is consistency with the equally pointless trailing comma on an
initialiser list.

Because people used the extension, and didn't have the conservative
attitude is promoted here, where any innovation is treated as an heresy,
even in the most trivial cases.

No, innovation's great, and it gives you extra choice. But not everybody
innovates in the same way. The conservative attitude promoted here is based
on the fact that using extensions brings with it a portability cost. If you
decide you want to go ahead and use the extensions anyway and let the cost
be hanged, well, that's up to you - and there are newsgroups dealing with
questions about the extensions of particular implementations. Lots of them.
Please let us keep /one/ newsgroup where such extensions are /not/ topical
- pretty please? With sugar on?

 

[Arthur J. O'Dwyer]

Nick Keighley' signature contains:

I would love to see some discussions about this. I'm constantly
changing my mind about whether or not to use extensions. I most
recently decided to start using extensions, marking them with
__extension__,

As someone else said, "eek!" But I'm not sure what you mean;
do you mean using the comment string /*__extension__*/ as standard
documentation, the way some people use /*FALLTHROUGH*/ and I
personally use /* Todo fixme bug hack */? Or do you mean naming
your functions things like

fft(x) /* the standard, slow version */
fft__extension__(x) /* the speedy version */

Either of those seems reasonable, although the latter IMHO is a
bad idea.

and stop worrying about it. But I keep worrying about
it. At the moment, the only extensions I'm using are trivial-- enums
with trailing commas, unnamed unions within structures (Am I correct in
calling that trivial?),

If you mean

enum foo { x, y, z, } bar;

struct baz {
union /* unnamed */ {
int i;
double j;
} a;
int b;
};

those are both standard features of C, not extensions. If you mean

struct {
union {
int i; /* henceforth "quux.i" */
double j; /* henceforth "quux.j" */
} /* unnamed */;
int b;
} quux;

that's just wrong and evil, and I didn't even know any implementors
had stooped that low. (For one thing, it means that modifying 'quux.i'
will invalidate 'quux.j', even though they're both syntactically
fields in a struct --- which violates the C "object model" and
generally screws with the maintainer's brain.)

and very rarely the typeof keyword.

'typeof' seems nice, but other than writing SUPER ULTRA FAST!!1!
macros to swap two values of arbitrary type, I've never seen a
real-world use for it.

I work
exclusively with gcc, and although I'm trying to remain within
standards, the only enforcement mechanism I really have is -pedantic,
so for all I know all of my efforts to be completely standard are
wasted. I'd like to start using typeof more often, but am reluctant to
do so. Is there a way to deteremine which extensions are considered
more acceptable (ie more likely to be incorporated into the standard)
than others?

Given that the C99 standard still isn't being taught in school, widely
used, or added to GCC, after 7 years, I'm guessing that we may have
reached the point where "likely to be incorporated into the standard"
and "acceptable" are totally different things. As far as I'm concerned,
"acceptable" means either "works in Visual Studio" or "works in ISO C90",
depending on your job description. C99 has nothing to do with it --- let
alone future standards!

my $.02,
-Arthur

 

[Mark McIntyre]

What was before an extension is now in the standard.

Yup.

Why?
Because people used the extension, and didn't have the conservative
attitude is promoted here, where any innovation is treated as an heresy,
even in the most trivial cases.

Or possibly even, because people didn't have MASSIVE chips on their
shoulders about being repeatedly asked not to go on about wildly
offtopic stuff in a group dedicated to a particular topic.

Perhaps you ought to stop making such a complete fool of yourself.
Mark McIntyre

 

[Keith Thompson]

Keith Thompson a écrit :


What was before an extension is now in the standard.

Why?

Because people used the extension, and didn't have the conservative
attitude is promoted here, where any innovation is treated as an
heresy, even in the most trivial cases.

Jacob, you should know better than this by now.

Extensions are not treated as "heresy". I don't remember anyone other
than you using that word or anything resembling it. I hesitate to
call anyone a liar, but your statement is grossly misleading.

Extensions are treated as exactly what they are -- non-standard
extensions. This newsgroup, as you should know perfectly well,
discusses the C programming language, which is defined by the C90 and
C99 standards. There are a plethora of C implementations, most of
which provide non-standard extensions (as the standard explicitly
allows). We simply lack the expertise and the inclination to keep
track of all of them.

When we see code posted there that uses extensions that are necessary
to the functionality of the code (for example, code that uses
directories or threads), we advise the poster to post to a newsgroup
where those extensions are topical. When we see code that
*unnecessarily* uses extensions (for example, code that gratuitously
clears the screen or calls getch()), we point out that the code is
non-portable, and could easily be made portable.

There are plenty of system-specific newsgroups where these extensions
can be discussed among people who actually know and care about them.

If you want to advocate changes to the standard, comp.std.c is the
place to do so. Actually getting a change through the process is a
lot of work; you can either do that work yourself, or persuade someone
else to do it, or give up. Of course, there's no guarantee that
you'll succeed. If you don't like C as it is, and can't persuade the
committee to change it to your liking, you can always publish your own
language standard, as long as you don't claim that it's C.

If you merely want to discuss or advocate the use of
implementation-specific extensions that you think are useful, please
do so in a newsgroup that's appropriate to the implementation in
question.

You have comp.compilers.lcc, and if you post a brief message here
pointing people to it, I for one will not object. But your repeated
attempts to characterize this newsgroup as some kind of
standard-conforming religious cult are extremely annoying.

Once again, extensions are not evil, and nobody here has claimed that
they are. They're just not what we discuss in this newsgroup.

Do you understand?

 

[Mark McIntyre]

jacob navia said:


No idea. It's a completely pointless extension. The only reason I can think
of for it is consistency with the equally pointless trailing comma on an
initialiser list.

Well, I don't know. I've found a use for it oft-betimes, for example
if you're generating lists via a script, or if you're adding or
recordering elements time to time.
Mark McIntyre

 

[Keith Thompson]

Jacob, you should know better than this by now.

Extensions are not treated as "heresy". I don't remember anyone other
than you using that word or anything resembling it. I hesitate to
call anyone a liar, but your statement is grossly misleading.

[snip]

The preceding rant was intended for comp.lang.c. I didn't notice that
this thread is cross-posted to comp.programming, where discussions of
non-standard C language extensions might be perfectly topical for all
I know.