Problem with a linked list

[Xarky]

Hi,

I am writing a linked list in the following way.

struct list
{
struct list *next;
char *mybuff;
};

struct list *myList = NULL;
struct list *endList = NULL;

void getline(char s[], int lim)
{
int c, i;

for(i=0; ((i<lim-1) && ((c=getchar()) != '\n')); i++)
s = c;

s ='\0';
} // end method getline

void add_item(char *data)
{
if (!endList)
{
endList = (struct list *)malloc(sizeof(struct list));

myList = endList;
endList->mybuff = data;
endList->next = NULL;
} // end if
else
{
endList->next = (struct list *)malloc(sizeof(struct list));
endList = endList>next;
endList->mybuff = data;
endList->next = NULL;
} // end else
}

void printList()
{
struct list *current = myList;

while(current)
{
printf("%s\n", current->mybuff);
current = current->next;
}
}

int main()
{
char buff[50];

// called for a n times
getline(buff, 50);
add_item(buff);

printList();
}

Now in the printList method, the nothing is being printed, but just a
simple blank line for each item.

Can someone help me solve this problem out.
Thanks in Advance

 

[=?iso-8859-1?q?Dag-Erling_Sm=F8rgrav?=]

int main()
{
char buff[50];

// called for a n times
getline(buff, 50);
add_item(buff);

printList();
}

Now in the printList method, the nothing is being printed, but just a
simple blank line for each item.

Of course. What you have is not a list of strings, but a list of
pointers to buff, so printList() just prints N copies of whatever it
was you typed on line N.

DES

 

[Mukul]

Are you sure this program compiled, and that you are not looking
at some other binary? There is a syntax error at the line:
endList = endList>next; (should be endList->next)

Besides this, have you realized that you are 'assigning' data
without allocating any memory to the structure element mybuff?
This way you might end up corrupting many other things, however,
sometimes, you would find the same string (mybuff) in all the
nodes.

Overall, a poorly written code.

 

[maadhuu]

voke, what i think is u have not allocated memory fo the char * mybuff
member of the structure and what it will point is completely
implementation dependent......if the same char * is replaced with int or
plain char it will definitely work, provided u have the right syntax and
logic.

 

[marty]

int main()
{
char buff[50];

// called for a n times
getline(buff, 50);
add_item(buff);

printList();
}

Now in the printList method, the nothing is being printed, but just a
simple blank line for each item.

Of course. What you have is not a list of strings, but a list of
pointers to buff, so printList() just prints N copies of whatever it
was you typed on line N.

DES

Use a library for your linked lists if possible. glib from www.gtk.org was
pointed out to me on this ng and is what I'll be using in any future C
programming projects.


Martin

 

[CBFalconer]

I am writing a linked list in the following way.
.... snip ...

Now in the printList method, the nothing is being printed, but
just a simple blank line for each item.

Can someone help me solve this problem out.

C doesn't have methods, but it does have functions. Try the
following and understand why it is written as it is.

/* A simplified demo of creating a linked list */
/* EOF or a non-numeric entry ends entry phase */

#include <stdio.h>
#include <stdlib.h>

typedef int datatype;

struct node {
struct node *next;
datatype datum;
};

/* ----------------- */

/* add value to head of list */
struct node *addtolist(struct node *root, datatype value)
{
struct node *newnode;

if ((newnode = malloc(sizeof *newnode))) {
newnode->next = root;
newnode->datum = value;
}
return newnode;
} /* addtolist */

/* ----------------- */

void showlist(struct node *root)
{
while (root) {
printf("%d\n", root->datum);
root = root->next;
}
} /* showlist */

/* ----------------- */

/* believed necessary and sufficient for NULL terminations */
/* Reverse a singly linked list. Reentrant (pure) code */
struct node *revlist(struct node *root)
{
struct node *curr, *nxt;

if (root) { /* non-empty list */
curr = root->next;
root->next = NULL; /* terminate new list */
while (curr) {
nxt = curr->next; /* save for walk */
curr->next = root; /* relink */
root = curr; /* save for next relink */
curr = nxt; /* walk onward */
}
}
/* else empty list is its own reverse; */
return root;
} /* revlist */

/* ----------------- */

/* return all the storage for a list */
struct node *killlist(struct node *root)
{
struct node *tmp;

while ((tmp = root)) {
root = root->next;
free(tmp);
}
return root;
} /* killlist */

/* ----------------- */

int main(void)
{
struct node *root, *tmp;
datatype num;

root = NULL;
puts("Entry until non numeric value:");
while (1 == scanf("%d", &num)) {
if ((tmp = addtolist(root, num))) root = tmp;
else break;
}
puts("Entries, 1 per line, from last:");
showlist(root);
root = revlist(root);
puts("Same list, reversed:");
showlist(root);
root = killlist(root);
return 0;
} /* main linklist.c */

/* A run of the above code:
Entry until non numeric value:
1 2 40 3 5
8 9 x
Entries, 1 per line, from last:
9
8
5
3
40
2
1
Same list, reversed:
1
2
40
3
5
8
9
*/

 

[websnarf]

I am writing a linked list in the following way.

struct list
{
struct list *next;
char *mybuff;
};

struct list *myList = NULL;
struct list *endList = NULL;

void getline(char s[], int lim)
{
int c, i;

for(i=0; ((i<lim-1) && ((c=getchar()) != '\n')); i++)
s = c;

s ='\0';
} // end method getline

"//" is not a portable way of expressing a comment in C. Not that
portability is an issue in this newsgroup. (You can also use fgets()
as an alternative to the function you've written.)

Ok, to the issue of linked lists.

1. First of all, you have to remember to allocate individual storage
for each string that you input. If you reuse the same buffer for
input, then your older input will simply be overwritten by it each
time.

2. Ok, there is also a common obfuscation that people do when they make
linked lists of distinguishing the "empty list" case from the other
cases. Actually both cases are the same if you think of the "current
tail pointer" as a reference to the link point, rather than the upper
container of the link point. I.e., tail should be &("last"->next)
rather than just "last". In this way the "current tail pointer" for
empty list is just the address of the top-of-list pointer, and is just
the address of the last "->next" record in the list.

I've demonstrated this in the code below:

static char * copystr (const char * data) {
int l = strlen(data) + 1;
char * s = (char *) malloc (sizeof (char) * l);
if (s) memcpy (s, data, l);
return s;
}

struct list ** add_item (struct list ** tail, char * data) {
if (NULL == tail ||
NULL != *tail ||
(NULL == (*tail = (struct list *) malloc(sizeof(struct list))))
)
return NULL;
(*tail)->mybuff = copystr (data);
(*tail)->next = NULL;
return &((*tail)->next);
}

void printlist (struct list * head) {
while (head) {
printf ("%s\n", head->mybuff);
head = head->next;
}
}

void destroylist (struct list ** tail) {
if (NULL == tail) return;
while (*tail) {
struct list ** next = &((*tail)->next);
(*tail)->next = NULL;
free ((*tail)->mybuff);
free (*tail);
tail = next;
}
}

int main () {
int i;
char buff[51];
struct list * top = NULL, * cur, ** tailptr;

for (tailptr = &top, i=0; i < 10; i++) {
getline (buff, 50);
tailptr = add_item (tailptr, buff);
}

printlist (top);
destroylist (&top);
return 0;
}

 

[Keith Thompson]

"//" is not a portable way of expressing a comment in C.
True.

Not that
portability is an issue in this newsgroup.

What???

 

[CBFalconer]

.... snip ...

"//" is not a portable way of expressing a comment in C. Not that
portability is an issue in this newsgroup. (You can also use
fgets() as an alternative to the function you've written.)

On the contrary, it is extremely important. The point about // is
that it is only portably usable on C99 compliant systems, and that
it is extremely vulnerable to linewrap problems in usenet postings.

.... snip ...

2. Ok, there is also a common obfuscation that people do when they
make linked lists of distinguishing the "empty list" case from the
other cases. Actually both cases are the same if you think of the
"current tail pointer" as a reference to the link point, rather
than the upper container of the link point. I.e., tail should be
&("last"->next) rather than just "last". In this way the "current
tail pointer" for empty list is just the address of the top-of-list
pointer, and is just the address of the last "->next" record in the
list.

As I demonstrated in an earlier posting in this thread, there is no
need for the complication of maintaining a tail pointer.

I've demonstrated this in the code below:

static char * copystr (const char * data) {
int l = strlen(data) + 1;
char * s = (char *) malloc (sizeof (char) * l);

The cast is superfluous, and only serves to hide the error of

if (s) memcpy (s, data, l);
return s;
}

struct list ** add_item (struct list ** tail, char * data) {
if (NULL == tail ||
NULL != *tail ||
(NULL == (*tail = (struct list *) malloc(sizeof(struct list))))
)
return NULL;
(*tail)->mybuff = copystr (data);
(*tail)->next = NULL;
return &((*tail)->next);
}

All this unnecessary complication to use a tail pointer. The code
is also obfuscated by more foolish and unnecessary casts.

Of course you have neglected to ever define struct list. The code
will not even compile.

void printlist (struct list * head) {
while (head) {
printf ("%s\n", head->mybuff);
head = head->next;
}
}

Having neglected to #include <stdio.h> there is no prototype for
printf in scope. The code thus invokes undefined behavior, and is
not suitable for this newsgroup.

void destroylist (struct list ** tail) {
if (NULL == tail) return;
while (*tail) {
struct list ** next = &((*tail)->next);
(*tail)->next = NULL;
free ((*tail)->mybuff);
free (*tail);
tail = next;
}
}

If tail is expected to point to the last item in a list, tail->next
would normally be NULL. Once more the code is obfuscated and
unnecessarily verbose.

int main () {
int i;
char buff[51];
struct list * top = NULL, * cur, ** tailptr;

for (tailptr = &top, i=0; i < 10; i++) {
getline (buff, 50);
tailptr = add_item (tailptr, buff);
}

printlist (top);
destroylist (&top);
return 0;
}

All in all, I do not recommend studying the above.

Should the OP really want a list formed in the so called normal
order (rather than reversed, as I demonstrated earlier) he can do
so with perfectly portable code. However he would be well advised
to make a few block diagrams showing the actual form of the list
when empty, when holding one item, and when holding more than one
item, and how to make the transitions between them. He might well
consider defining a listheader type which can hold both head and
tail pointers, something like:

struct listheader {
struct node *head, *tail;
}

and he can then declare instances as:

struct listheader mylist = {NULL, NULL};

for the initial condition. Now the functions can operate on:

errinfo_t somefunction(struct listheader *thelist, /* data */);

and avoid all that fuzzy thinking.

 

[websnarf]

On the contrary, it is extremely important. The point about // is
that it is only portably usable on C99 compliant systems,

Which basically dont exist. Therefore its not portable. Just how
shallow are your powers of reasoning?

As I demonstrated in an earlier posting in this thread, there is no
need for the complication of maintaining a tail pointer.

Your implementation adds entries to the "top" of the list. The OP
clearly was trying to implement a semantic which adds entries to the
tail. There is a difference.

The cast is superfluous, and only serves to hide the error of
failing to #include <stdlib.h>. sizeof(char) is always 1 by
definition, and using it only serves to obfuscate the code.

Illustrating my point about not caring about portability perfectly.
The cast has to be there for this to correctly compile with C++
compilers. A lot of C development done today is actually on C++
compilers.

All this unnecessary complication to use a tail pointer. The code
is also obfuscated by more foolish and unnecessary casts.

There is one cast above and I've explained why this is necessary. I'm
sorry if this code is too complicated for you, but it solves the
problem in a way that is as close to what the OP was trying to do as
possible. If you have a specific question, I can explain whichever
part of this code you don't understand.

Of course you have neglected to ever define struct list. The code
will not even compile.

I don't think the OP will have any trouble with it considering he has
defined it. I never claimed it was a complete program. The OP still
has to put it together.

All in all, I do not recommend studying the above.

But you do recommend changing the algorithm and basically mixing up the
semantics of a queue versus a stack?

The OP can't learn anything from your code -- it does the wrong thing.
Besides being correct, my code demonstrates an important idea in
simplifying linked list management. I.e., that the empty, singleton
and other cases are not actually different in any way, and don't need
to be dealt with in seperate cases.

[...] However he would be well advised
to make a few block diagrams showing the actual form of the list
when empty, when holding one item, and when holding more than one
item, and how to make the transitions between them. He might well
consider defining a listheader type which can hold both head and
tail pointers, something like:

struct listheader {
struct node *head, *tail;
}

You of course miss the whole point of unsing an additional indirection.
"tail" should not be declared like that. It just causes you to have
extra cases that get pushed upwards into the usage semantics. I.e.,
the code doubles in size for no good reason.

Furthermore, anyone who has dealt with linked lists knows that having a
pointer to the end is not necessarily an intrinsic part of a linked
list -- for example if you wish to implement an "insert" function
instead of an "append" function, then the tail is not of any relevance.
I.e., including a definition of a tail into a "listheader" (which may
be redundant and unnecessary) is not always desirable.

Now the functions can operate on:

errinfo_t somefunction(struct listheader *thelist, /* data */);

and avoid all that fuzzy thinking.

Yeah, you seem to be big on avoiding thinking of any kind.

 

[Al Bowers]

As I demonstrated in an earlier posting in this thread, there is no
need for the complication of maintaining a tail pointer.

It really is unclear on the requirements of the OP. Should the
op need to maintain a data model that requires sequentually
adding data to the end of the link then your demonstration
would not be the preferred method, as the demonstration adds
data to the root(head) of the list. IMO, there is not
much complication in maintaining a tail pointer. A model
as you have described below would be a fine approach.


.....................SNIP....................

Should the OP really want a list formed in the so called normal
order (rather than reversed, as I demonstrated earlier) he can do
so with perfectly portable code. However he would be well advised
to make a few block diagrams showing the actual form of the list
when empty, when holding one item, and when holding more than one
item, and how to make the transitions between them. He might well
consider defining a listheader type which can hold both head and
tail pointers, something like:

struct listheader {
struct node *head, *tail;
}

and he can then declare instances as:

struct listheader mylist = {NULL, NULL};

for the initial condition. Now the functions can operate on:

errinfo_t somefunction(struct listheader *thelist, /* data */);

and avoid all that fuzzy thinking.

Yes!
Here is a hastily written and possibly deficient example
that I hope is not fuzzy.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_DATA 50

struct node
{
struct node *next;
char data[MAX_DATA];
};

typedef struct QUEUE
{
struct node *head;
struct node *tail;
} QUEUE;

/* Prototyes */
struct node *pushQUEUE(QUEUE *p, char *data);
char *popQUEUE(QUEUE *p);
void freeQUEUE(QUEUE *p);

int main(main)
{
char *data;
QUEUE fifo = {NULL};
int i;

pushQUEUE(&fifo,"1111111111");
pushQUEUE(&fifo,"2222222222");
pushQUEUE(&fifo,"3333333333");
for(i = 0 ; i < 2 &&(data = popQUEUE(&fifo)) ;i++ )
printf("POP \"%s\"\n",data);
pushQUEUE(&fifo,"4444444444");
putchar('\n');
for( ; (data = popQUEUE(&fifo));i++ )
printf("POP \"%s\"\n",data);
freeQUEUE(&fifo);
return 0;
}

struct node *pushQUEUE(QUEUE *p, char *data)
{
struct node *tmp;

if((tmp = calloc(1,sizeof *tmp)) != NULL)
{
strncat(tmp->data,data,MAX_DATA);
tmp->next = NULL;
if(!p->tail) p->head = tmp;
else p->tail->next = tmp;
p->tail = tmp;
}
return tmp;
}

char *popQUEUE(QUEUE *p)
{
static char s[MAX_DATA];
struct node *tmp;

if(!p->head) return NULL;
strcpy(s,p->head->data);
tmp = p->head->next;
free(p->head);
if((p->head = tmp) == NULL) p->tail = NULL;
return s;
}

void freeQUEUE(QUEUE *p)
{
struct node *tmp;

for( ; (p->head); p->head = tmp)
{
tmp = p->head->next;
free(p->head);
}
p->tail = NULL;
return;
}

 

[Al Bowers]

CBFalconer wrote:


There is one cast above and I've explained why this is necessary. I'm
sorry if this code is too complicated for you, but it solves the
problem in a way that is as close to what the OP was trying to do as
possible. If you have a specific question, I can explain whichever
part of this code you don't understand.

It seems that the OP wants a pointer to the tail of the
list for some reason unknown. It seems strange that you
would define a function add_item that will would adultrate
that precious tail pointer should function malloc return NULL.
Perhaps you have a reason with would be explicable but on the
surface it looks to ba a clumsy way to define the function.

 

[Keith Thompson]

Which basically dont exist. Therefore its not portable.

[personal insult snipped]

Nobody was disputing your statement that "//" comments aren't
portable. CBFalconer's "On the contrary" was in response to your
claim that portability is not an issue in this newsgroup. In fact,
portability is an always has been an extremely important issue in this
newsgroup.

[...]

Illustrating my point about not caring about portability perfectly.
The cast has to be there for this to correctly compile with C++
compilers. A lot of C development done today is actually on C++
compilers.

There is rarely any need for C code to compile correctly with C++
compilers. That's what C compilers are for. Code compiled with C++
compilers is called C++; there are several newsgroups dedicated to it.

As you know, C and C++ are closely related but distinct languages.

Casting the result of malloc() is unnecessary in C, and can (depending
on the compiler) mask the error of failing to #include <stdlib.h>.

 

[CBFalconer]

.... snip ...


Illustrating my point about not caring about portability
perfectly. The cast has to be there for this to correctly
compile with C++ compilers. A lot of C development done today
is actually on C++ compilers.

Marvellous. You write poor obfuscated error-prone C code in order
to avoid using a C compiler, and claim the result is portable C. I
am blinded by your keen intellect. I assume your code compiles on
a Fortran compiler? Pascal? Ada? MIX assembler? Should I let
the cat walk over the keyboard to select the compiler?

 

[websnarf]

[...] It seems that the OP wants a pointer to the tail of the
list for some reason unknown.

Unknown?!?! Look closely. It causes the algorithm to stop attempting
to add nodes. It is essentially a simple feedback that lets you know
that you are out of memory (or more generally that an add_item has
failed).

[...] It seems strange that you
would define a function add_item that will would adultrate
that precious tail pointer should function malloc return NULL.

Strange how?

Perhaps you have a reason with would be explicable but on the
surface it looks to ba a clumsy way to define the function.

I don't understand your confusion. The tail is overwritten with NULL
when malloc has failed on you, so you can test it easily afterwards ...
what would you suggest as an alternative behavior?

 

[websnarf]

Nobody was disputing your statement that "//" comments aren't
portable.

Nobody else brought it up either. This doesn't tell you something?

[...] CBFalconer's "On the contrary" was in response to your
claim that portability is not an issue in this newsgroup. In fact,
portability is an always has been an extremely important issue in
this newsgroup.

I simply don't think that's the case.

[...]

Illustrating my point about not caring about portability perfectly.
The cast has to be there for this to correctly compile with C++
compilers. A lot of C development done today is actually on C++
compilers.

There is rarely any need for C code to compile correctly with C++
compilers.

That's not true. Many people who write C++ code, also really write a
lot of C code. And therefore also consume C code written by others.
Its not rare at all. C++ people don't use entirely different concepts
to implement linked lists.

[...] That's what C compilers are for. Code compiled with C++
compilers is called C++; there are several newsgroups dedicated to
it.

Just because you decide to live in a small little cubby hole doesn't
mean that other people have chosen to do the same. The WATCOM C++
compiler, often produces substantially faster code than their C
compiler, BTW.

As you know, C and C++ are closely related but distinct languages.

Casting the result of malloc() is unnecessary in C, and can
(depending on the compiler) mask the error of failing to #include
<stdlib.h>.

Not casting malloc() masks the error of not being able to compile with
a C++ compiler. Of the two points of view, which do you think is more
aligned to the issue of portability?

 

[Keith Thompson]

Nobody else brought it up either. This doesn't tell you something?

No, it doesn't. I've seen the non-portability of "//" comments
mentioned here numerous times.

[...] CBFalconer's "On the contrary" was in response to your
claim that portability is not an issue in this newsgroup. In fact,
portability is an always has been an extremely important issue in
this newsgroup.

I simply don't think that's the case.

Then I humbly submit that you should consider paying closer attention.

[...]

That's not true.

[snip]

Yes, it is. This has been discussed at length here many times.

[snip]

Not casting malloc() masks the error of not being able to compile with
a C++ compiler. Of the two points of view, which do you think is more
aligned to the issue of portability?

Not being able to compile with a C++ compiler is not an error.

 

[Richard Bos]

[...] It seems that the OP wants a pointer to the tail of the
list for some reason unknown.

Unknown?!?! Look closely. It causes the algorithm to stop attempting
to add nodes. It is essentially a simple feedback that lets you know
that you are out of memory (or more generally that an add_item has
failed).

Which is a wrong way to handle such situations. If add_item() fails, it
should return a failure status, not fiddle with a pointer.

Besides, the OP's code never even checks what happens to that pointer.
If malloc() returns a null pointer, it merrily writes through it as if
nothing untoward has happened.

I don't understand your confusion. The tail is overwritten with NULL
when malloc has failed on you, so you can test it easily afterwards ...
what would you suggest as an alternative behavior?

Make add_item() an int function rather than void, return a success
value, and for heavens' sake, _check_ that malloc() succeeded!
Alternatively, make add_item() return a struct list *, to the added
member if succesful, null if not. And ditto on malloc().

Richard

 

[Richard Bos]

Nobody was disputing your statement that "//" comments aren't
portable.

Nobody else brought it up either. This doesn't tell you something?

[...] CBFalconer's "On the contrary" was in response to your
claim that portability is not an issue in this newsgroup. In fact,
portability is an always has been an extremely important issue in
this newsgroup.

I simply don't think that's the case.

That's because you don't know what "portable" means.

That's not true. Many people who write C++ code, also really write a
lot of C code. And therefore also consume C code written by others.

And if so, they'd better learn the difference. Broken C++ users are no
excuse for us to subject our C code to uglification as well.

Not casting malloc() masks the error of not being able to compile with
a C++ compiler.

That is not an error, it is a highly useful feature.

I'd tell you to get a clue, but I don't think you're able to.

Richard

 

[Chris Torek]

Not casting malloc() masks the error of not being able to compile with
a C++ compiler.

I see. Do you avoid classes, "new", exceptions, and all other C++
features so that your C++ code can be compiled with a C compiler?