C Linked List -

[ritchie]

Hi,

I am writing to ask for some info with a program I am trying out. I
am teaching myself
linked lists in C.

I have a linked list (see code below), and I accept user input which
is the inputted into
the list via an 'insert function'. The users value is passed as a
paramater to 'insert'.
All is ok with this, but what I was wondering is, if I have a node
with say 10 variables instead of one, is it still ok/efficent to pass
these values to 'insert' as paramaters?
Is there another way??

Also, I know that you can delete nodes, but is there any other actions
that can be performed on linked lists that would help me learn more?

Thanks a million,
Ritchie


~~~~~~~~~~~~~~~~~~CODE START ~~~~~~~~~~~~~~~~~~~
struct node {
int iOrderDate;
struct node *nextPtr;
};
typedef struct node Node;
typedef Node *NodePtr;

/********************** fns *****************************/

void insert ( NodePtr *, int );

/********************************************************/
....

void insert (NodePtr *sPtr, int lDate)
{
NodePtr newPtr, prevPtr, currPtr;

newPtr = malloc( sizeof(Node) );

if( newPtr != NULL )
{
newPtr->iOrderDate = lDate;
newPtr->nextPtr = NULL;

prevPtr = NULL;
currPtr = *sPtr;

while( currPtr != NULL && lDate > currPtr->iOrderDate )
{
prevPtr = currPtr;
currPtr = currPtr->nextPtr;
}

if( prevPtr == NULL )
{
newPtr->nextPtr = *sPtr;
*sPtr = newPtr;
}
else
{
prevPtr->nextPtr = newPtr;
newPtr->nextPtr = currPtr;
}
}
else
printf("unable to allocate memory!");
}

~~~~~~~~~~~~~~CODE END ~~~~~~~~~~~~~~~~~

 

[AirPete]

Hi,

I am writing to ask for some info with a program I am trying out. I
am teaching myself
linked lists in C.

I have a linked list (see code below), and I accept user input which
is the inputted into
the list via an 'insert function'. The users value is passed as a
paramater to 'insert'.
All is ok with this, but what I was wondering is, if I have a node
with say 10 variables instead of one, is it still ok/efficent to pass
these values to 'insert' as paramaters?
Is there another way??

If I understand you, there should be no difference how many members Node
has, because you're passing it as a pointer.

Also, I know that you can delete nodes, but is there any other actions
that can be performed on linked lists that would help me learn more?

Not that I can think of, although a function to walk the list, accepting a
function pointer as an argument, and calling the pointed-to function for
each node (passing the node) could be handy.
[snip]

 

[Default User]

Hi,

I am writing to ask for some info with a program I am trying out. I
am teaching myself
linked lists in C.

Please fix your line lengths, go with something less than 80 character
so that weird wrapping like the above does not occur.

All is ok with this, but what I was wondering is, if I have a node
with say 10 variables instead of one, is it still ok/efficent to pass
these values to 'insert' as paramaters?

That's starting to push it from a readability standpoint. I doubt it
makes a significant difference in performance.

Is there another way??

Sure, create the new node and pass a pointer to the insert function.

Also, I know that you can delete nodes, but is there any other actions
that can be performed on linked lists that would help me learn more?

One of the obvious important ones is to find a specific node based on
search criteria. My linked list stuff also has a replace_node() function
to swap out a node. I also have print_node() that outputs the node data,
and a dump_list() which prints out the data from the entire list in one
fell swoop.

A lot of the functionality you add will depend on what you use the list
for.



Brian Rodenborn

 

[Thomas Matthews]

Hi,

I am writing to ask for some info with a program I am trying out. I
am teaching myself
linked lists in C.

I have a linked list (see code below), and I accept user input which
is the inputted into
the list via an 'insert function'. The users value is passed as a
paramater to 'insert'.
All is ok with this, but what I was wondering is, if I have a node
with say 10 variables instead of one, is it still ok/efficent to pass
these values to 'insert' as paramaters?
Is there another way??

Also, I know that you can delete nodes, but is there any other actions
that can be performed on linked lists that would help me learn more?

Thanks a million,
Ritchie


~~~~~~~~~~~~~~~~~~CODE START ~~~~~~~~~~~~~~~~~~~
struct node {
int iOrderDate;
struct node *nextPtr;
};
typedef struct node Node;
typedef Node *NodePtr;

[snip]

I would isolate the data from the links. Try to make the
link list container independent of the data in the container.

For example:
struct node
{
void * p_data;
struct node * next;
};

typedef int (*P_Compare_Func)(void * p_A, void * p_B);

Also, to make the list more generic, provide these functions:
insert_front (a.k.a. push_front) -- add to front of list.
insert_back (a.k.a. push_back) -- append to list.
insert_sort(struct node * p_list,
void * data,
P_Compare_Func compare_func);
The insert_sort function would use the function pointer
to find out where to insert the new node.

By using a pointer to the data, the number of parameters
for the insert functions is the same regardless of how
many variables are "in the node".

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book

 

[Malcolm]

All is ok with this, but what I was wondering is, if I have a node
with say 10 variables instead of one, is it still ok/efficent to pass
these values to 'insert' as paramaters?
Is there another way??

The rule of thumb is that you should pass no more than four parameters to a
function. This is because, internally, most compilers will pass up to four
parameters in registers, whilst additional ones will be passed on the stack,
which is slower. The other reason is that four parameters is about as many
as the human eye can cope with.
However if you really need extra parameters, this rule can be broken.
As many as ten parameters are probaly best wrapped up in a structure.

struct node {
int iOrderDate;
struct node *nextPtr;
};
typedef struct node Node;
typedef Node *NodePtr;

Personally I hate this. Node * tells you that a pointer is being passed.
Typedef the asterisk away, and you rapidly end up with a situation where you
don't know what is going on.

I notice you call malloc() to allocate new nodes. This is acceptable, but to
squeeze extra performance you could consider writing your own fixed-size
allocator / deallocator. Use the link to keep track of your free store.
Initally, all entries are free and the list is set so each points to its
neighbour. To allocate, return the first on the list and advance your free
pointer. To free, set the link in the block to be freed to your free
pointer, and set the free pointer to the block just freed.

 

[ritchie]

Hi,

Thanks for the replies.
However, I have another question about linked lists.

I am getting the values for the nodes by sannf'ing them into variables
in main and then passing those variables into the insert function.
Is this the correct way to do it? As I have seem it done differently
before, scanf'ed directly into the node.
ie: "scanf("%d", nodePtr->nodeMember);".
Does it make a difference?

Also, I am trying to insert a date but i'm not quite sure what is the
best way to do it.

I have included code below which is inserting the values, but i'm not
quite sure that i'm doing it correctly.

If anyone has time could they please let me know if/what i'm doing
wrong?

Thanks again,
Ritchie

****************************code******************************
struct date {
int iDay;
int iMonth;
int iYear;
};
typedef struct date Date;

struct node {
Date iOrderDate;
char cType[20];
struct node *nextPtr;
};
typedef struct node Node;
typedef Node *NodePtr;
….
/*********************** FUNCTIONS******************************/
void insert ( NodePtr *, int , char[] );
/*****************************************************************/
int main(void) {
int iDateIn=0;
char cTypeIn[20];
....
printf("Enter date: "); scanf( "%d", & iDateIn);//GET VALUES TO
INSERT
printf("Enter type: "); scanf( "%s", cTypeIn );

insert( &nStart, iDateIn, cTypeIn ); //INSERT INTO NODE

/************************* insert fn ********************************/
void insert( NodePtr *sPtr, int lOrderDate, char lType[] )
{
NodePtr newPtr, prevPtr, currPtr;
newPtr = malloc( sizeof(Node) );

if( newPtr != NULL )
{
newPtr->iOrderDate.iDay = lOrderDate;
newPtr->nextPtr = NULL;

prevPtr = NULL;
currPtr = *sPtr;

while( currPtr != NULL && lOrderDate > currPtr-iOrderDate.iDay )
{
prevPtr = currPtr;
currPtr = currPtr->nextPtr;
}
if( prevPtr == NULL )
{
newPtr->nextPtr = *sPtr;
*sPtr = newPtr;
}
else
{
prevPtr->nextPtr = newPtr;
newPtr->nextPtr = currPtr;
}
}
else
printf("unable to allocate memory!");
}

 

[pete]

Hi,

Thanks for the replies.
However, I have another question about linked lists.

I am getting the values for the nodes by sannf'ing them into variables
in main and then passing those variables into the insert function.
Is this the correct way to do it? As I have seem it done differently
before, scanf'ed directly into the node.
ie: "scanf("%d", nodePtr->nodeMember);".
Does it make a difference?

Also, I am trying to insert a date but i'm not quite sure what is the
best way to do it.

I have included code below which is inserting the values, but i'm not
quite sure that i'm doing it correctly.

If anyone has time could they please let me know if/what i'm doing
wrong?

Why don't you post a small complete program ?

 

[ritchie]

Hi,

Thanks everyone for the replies. They have all been very helpful.

I have included most of my program.
I am calling these functions from a menu, which is where I suspect
that the trouble may lie?

The problem is that now, when I printf out the values, I keep getting
only the last values entered, and not the rest.
Can anyone see where i'm going wrong?

Also for my insert function, the values are going in, in any order.
What would be the best way to insert or display these values in
ascending/descending order?

Thanks again,
Ritchie


struct date {
int day;
int month;
int year;
};
typedef struct date Date;
struct node {
Date ord_date;
char type[20];
int num;
int num2;
int num3;
struct node *nextPtr;
};

int insert( struct node * indexArr[] )
{
size_t i, j;
struct node *pPtr, *prevPtr;

for (i = 0; i < 5; i++) {
indexArr = prevPtr = NULL;

for (j = 0; j < 5; j++) {
pPtr = malloc(sizeof(struct node));

if (pPtr != NULL)
{
if (j == 0)
indexArr = pPtr;
//? printf("enter type: "); scanf("%s", &(pPtr->type));
printf("enter num: "); scanf("%d", &(pPtr->num));
printf("enter num2: "); scanf("%d", &(pPtr->num2));
printf("enter num3: "); scanf("%d", &(pPtr->num3));
pPtr->nextPtr = NULL;

if (prevPtr)
prevPtr->nextPtr = pPtr;
prevPtr = pPtr;
}
else
{
return 0;
}
}
}
return;
}