Fog Creek Software
Discussion Board




You guys must love me by now...

So, here I am. I built a linked list, it works (I'm all gleamy eyed because I learned to do it all by myself). But, when I iterate through the list, it prints all I need to see, *plus*, a whole lot of garbage.

If I print printf("%s", struct->my_char_array);

it prints a whole lot of gibberish and finally my string. Any ideas on that?

I'm still open to an easy tutorial on linked lists. If anyone has one, please come forward.

noob
Monday, June 07, 2004

"it prints all I need to see, *plus*, a whole lot of garbage"

Did you remember to stick a null character at the end of your string?  If you don't have a '\0' then printf will keep going ...

Good luck.  Someday, you'll learn C++ and STL and never hand-roll a link list again. :-)

Matt H.
Monday, June 07, 2004


Shoot.  I just read that it's a whole lot of gibberish and then finally your string.  So your string is last, not first.


That sounds like your pointer is off by something.  Too far behind.  I would look at what you are really pointing to in your assignment.

Regards,

Matt H.
Monday, June 07, 2004


noob says, "You guys must love me by now..."

I say, "It all depends on your gender, really." <jk/>

Sathyaish Chakravarthy
Monday, June 07, 2004

Linked List 101:

struct node {
  void* data;
  struct node* next;
}

struct node* node_create() {

  struct node* n;
  n = (struct node*)calloc(1, sizeof(struct node));
  return n;

}

struct node* node_append(struct node* TOP, struct node* a) {
  struct node* cur;

  if (TOP == NULL) return a;

  for(cur = TOP; cur; cur = cur->next)
    if (cur->next == NULL) {
      cur->next = a;
      cur = NULL;
    }

  return TOP;

}

struct node* node_unlink(struct node* TOP, void* target) {

  struct node* cur;
  struct node* prev = NULL;

  if (TOP->data == target)
    return TOP->next;

  for(cur = TOP; cur; cur = cur->next) {
    if (cur->data == target) {
      prev->next = cur->next;
      if (cur->data) free(cur->data);
      free(cur);
      cur = NULL;
    }
    prev = cur;
  }

  return TOP;   

}

void node_list_free(struct node* TOP) {

  struct node* cur;
  struct node* prev;

  for(cur = TOP; cur; cur = cur->next) {
    prev = cur->next;
    if (cur->data) free(cur->data);
    free(cur);
    cur = prev;
  }

}

int main() {

  struct node* top = NULL;
  struct node* input;
  struct node* cur;

  while((input = node_read()))
    top = node_append(top, input);
 
  input = removal_read();
  top = node_unlink(top, input);

  for(cur = top; cur; cur++)
    puts(cur->data);

  node_list_free(top);

  return 0;

}


That's pretty much it in a nutshell.  Complexity can be added if the data elements themselves need special destructor functions, and you'd likely want a lookup function for most applications.  If maintaining the order of the list isn't important you can also gain speed by appending new nodes to the start of the list rather than the end.  This speed difference only really matters if your list is very large, otherwise you won't notice it.

Clay Dowling
Monday, June 07, 2004

dude, please choose another career


Monday, June 07, 2004

Hey, I groked pointers and now I'm onto linked lists. I'm averaging 2 days for each. Although I'm no master I'm getting there.

Did you manage to have a small app working with pointers in 2 days, when you were starting?

Choose another personality.

noob
Monday, June 07, 2004

noob, paste your code here:

rafb.net/paste

and the ask the folks on IRC: EFNet, channel C

They do this all day.

Alex
Tuesday, June 08, 2004

Actually, that was a very good idea.

noob
Tuesday, June 08, 2004

Clay Dowling:
I was doing things the same way you are, but I used malloc instead of calloc. Now with calloc everything's working fine and dandy.

I looked at the difference between malloc and calloc and by what I understood, the biggest difference is that calloc initializes the allocated memory to 0, while malloc doesn't.

Interesting, very interesting.

noob
Tuesday, June 08, 2004

A lesson I learned after beating my head against the wall a lot.  A colleague advised me to make the switch, and I had the same experience you described.  Once I groked that, C became a much easier language for me to work with.

Clay Dowling
Tuesday, June 08, 2004

Switch it back to malloc and understand what went wrong.  You're clearly not setting the end of string null character which the calloc is doing it for you, but you really should know why.

5v3n
Tuesday, June 08, 2004

*  Recent Topics

*  Fog Creek Home