473,890 Members | 1,359 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

pruning a linear singly linked list


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.

Apr 23 '06 #1
59 4272
Anando wrote:

this is an algorithm (programming technique) question rather
than a strictly C question. Therefore it would be better asked
on comp.programmin g
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)

Apr 23 '06 #2
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.

Apr 23 '06 #3

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?

Apr 23 '06 #4
On 2006-04-23, Bill Pursell <bi**********@g mail.com> wrote:

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,


You can use -ansi with gcc, and also -std=c99 or -std=c89
Apr 23 '06 #5
Ben C wrote:
On 2006-04-23, Bill Pursell <bi**********@g mail.com> wrote:
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,


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.
--
Flash Gordon, living in interesting times.
Web site - http://home.flash-gordon.me.uk/
comp.lang.c posting guidelines and intro:
http://clc-wiki.net/wiki/Intro_to_clc
Apr 23 '06 #6
Bill Pursell wrote:
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.


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

*I* find it amusing that GNU of all "organisati ons" 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

Apr 23 '06 #7
Anando wrote:
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);
Apr 23 '06 #8

"Nick Keighley" <ni************ ******@hotmail. com> wrote in message
news:11******** **************@ j33g2000cwa.goo glegroups.com.. .
*I* find it amusing that GNU of all "organisati ons" 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 :)
Apr 23 '06 #9
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
Apr 23 '06 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

4
4713
by: HS-MOON | last post by:
I'm asking you to help me. I'm a beginner of studying c++. I'm trying to make the Singly Linked List(Ordered). Anyway, I've been debugging all day. I can't sort it out!! As you see, I don't know what this is wrong.. When I run this pgm, It can't find the Current Variable. //
19
13583
by: RAJASEKHAR KONDABALA | last post by:
Hi, Does anybody know what the fastest way is to "search for a value in a singly-linked list from its tail" as oposed to its head? I am talking about a non-circular singly-linked list, i.e., head and tail are not connected. Of course, recursive function aproach to traverse the list is one way. But, depending upon the list size, it could overrun the stack pretty fast.
7
1979
by: Shwetabh | last post by:
Hi, can some one tell me: -> how to remove a loop from a singly linked list with a loop. -> how to count the number of nodes in a looped singly link list. Thanks
3
7858
by: malik | last post by:
// Linked Lists in classes(excluding structures) without using tail pointer # include<iostream.h> # include<stdlib.h> void Swap(int num1, int num2) { int a = num1; num2 = num1; num2 = a;
6
2534
by: Alien | last post by:
Hi, I am having problem with ordering a singly linked list. Since a singly linked list goes only one way, is it possible to order them? If my structs look like the one below. struct block { struct block *next;
3
3426
by: jou00jou | last post by:
Hello, I am trying to sort a singly linked list for the following typedef typedef struct message { int messageId; char * messageText; struct message * next; } message; I have successfully implemented add, delete, print, and search functions for the linked list but I am not sure why I am stuck with this one.
23
4382
by: Himanshu Chauhan | last post by:
Hi! I was wondering, In the first parse of a singly linked list of unknown length, is it possible to know when we are at middle of the linked list? Regards --Himanshu
4
4315
by: saki | last post by:
How do we reverse a singly linked list without using extra memory.Extra pointers can however be used
7
5748
by: davidson1 | last post by:
Hello friends, I want ur help regarding singly linked list in C,I tried in net,But it is confusing and difficult.I want singly linked list in a simple way of Understanding.Please Help Me I want single list to create,delete,Display Can u give me Program and Explanation,to create,display,Delete in a Simple and Easy Way.Really it will be Helpful for Me. I have given some partial code,I want Program to create,display,Delete a Singly...
0
9980
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
9826
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
11236
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
10830
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
0
9641
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
0
5855
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
0
6061
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
2
4276
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
3283
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.