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[i] = c;

s[i] ='\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

[Dag-Erling Smørgrav]

be*********@yah oo.com (Xarky) writes:

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
--
Dag-Erling Smørgrav - de*@des.no

[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]

be*********@yah oo.com (Xarky) writes:

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]

Xarky wrote:

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(stru ct 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(struc t 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
*/

--
Chuck F (cb********@yah oo.com) (cb********@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net> USE worldnet address!

[websnarf]

Xarky wrote:

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[i] = c;

s[i] ='\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(s truct 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;
}

---
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

[Keith Thompson]

we******@gmail. com writes:
[...]

"//" is not a portable way of expressing a comment in C.
True.
Not that
portability is an issue in this newsgroup.

What???

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[CBFalconer]

we******@gmail. com wrote:

Xarky wrote:

I am writing a linked list in the following way.

.... 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
failing to #include <stdlib.h>. sizeof(char) is always 1 by
definition, and using it only serves to obfuscate the code.
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(s truct 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(st ruct listheader *thelist, /* data */);

and avoid all that fuzzy thinking.

--
Chuck F (cb********@yah oo.com) (cb********@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net> USE worldnet address!

[websnarf]

CBFalconer wrote:

we******@gmail. com wrote:

Xarky wrote:

I am writing a linked list in the following way.
... 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,

Which basically dont exist. Therefore its not portable. Just how
shallow are your powers of reasoning?
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.

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.

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
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.

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(s truct 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.

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(st ruct listheader *thelist, /* data */);

and avoid all that fuzzy thinking.

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

---
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/