i can't seem to understand the logic behind linked lists :|

Ok i've made my code really simplistic to tackle the problem i'm having currently of understanding how linked lists work. I only know what happens until a new node is added (i.e. 1) but i can't seem to understand what happens AFTER that i.e if there are more than 1 nodes. So i've highlighted the bits where i exactly can't understand. Hopefully someone can explain it step by step.

Code:

---


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

struct charNode
{
  char petName[12];

  struct charNode *next;
};

typedef struct charNode charNode;

void addElement(charNode **start, char *petName);
void printList(charNode *start);
charNode* newNode(char *petName);
void getString(charNode *start);

int main()
{
  charNode *start = NULL;

  getString(start);
 
  return 0;
}


void getString(charNode *start)
{

    addElement(&start, "(1)Cat");
    addElement(&start, "(2)Dog");
    addElement(&start, "(3)Horse");
 
    printList(start);
}

void addElement(charNode **start, char *petName)
{

  charNode *temp,*prev, *loc;
  int i;

  temp = newNode(petName);


  if (*start == NULL)
  {
      *start = temp;
  }

  else
  {
      loc = *start;
      prev = NULL;

      for (i=0; loc != NULL; i++)
      {
                      printf("%d", i);
                      printf(" %s ", loc->petName);
                  prev = loc;
                        loc = loc->next;
        }
                printf("\n");
                printf("\n");

      temp->next = loc;
          prev->next = temp;
  }

}


charNode* newNode(char *petName)
{

  charNode *temp;

  temp = (charNode *) malloc(sizeof(charNode));
  if (temp == NULL)
  {
      printf("WARNING - Memory allocation error\n");
      exit(EXIT_FAILURE);
  }


  strcpy(temp->petName, petName);


  temp->next = NULL;

  return temp;
}


void printList(charNode *start)
{

  while (start != NULL)
  {

      printf("%s\n", start->petName);
      start = start->next;
  }
}

---

Hi,

first of all, on the typdef line, do something actually useful :D
hint :

Code:

---

typedef char* String

---

here's the stepwise evaluation for

Code:

---

void getString(charNode *start)
{

    addElement(&start, "(1)Cat");
    addElement(&start, "(2)Dog");
    addElement(&start, "(3)Horse");
 
    printList(start);
}

---

on the first call of add Element, *start is NULL (look at main() )

so according to your function, addElement returns start (by reference) by calling newNode

Code:

---

  if (*start == NULL)
  {
      *start = temp;
  }

---

** tips : instead of using strcpy, use strncpy ... strcpy doesn't have any check for buffer overflow.... to use strncpy :

Code:

---

strncpy(char *destination, char *source, bufferLength)
in your case :
strncpy(temp->petName, petName, 12);

---

so far, *start has a string "(1)Cat" according to

Code:

---

addElement(&start, "(1)Cat");

---

on the second call: (the part u actually asked :D)

Code:

---

addElement(&start, "(2)Dog");

---

before:

Code:

---

temp = newNode(petName); // making temp an element with new string in it
prev = NULL; // nowhere
loc = *start
/* loc has the same address as *start (ie harshly the same as saying
 * int *i, a = 10;
 * i = &a;
 */
"(1)Cat" -> NULL
  ^
 loc

---

1st iteration :

Code:

---

prev = loc;
"(1)Cat" -> NULL
  ^
(prev & loc)
loc = loc->next // loc becomes NULL
"(1)Cat" -> NULL
  ^        ^
 prev      loc     

the nullity of loc terminates the for loop and notice here how prev is actually used to store the last item in the list

then
temp->next = loc; // assigning the next of the temp to be NULL, since loc is null...
** tips : I don't personally think this is neccessary, since newNode has done this for you (Tested)

prev->next = temp; // simply appending the new element to the end of the old list
}

---

Hope dat helps :)

You don't understand the code, or the concept?

If it's the latter, you might enjoy [url=http://www.cprogramming.com/tutorial/lesson15.html]this[/rul] and/or this.

Quote:

---

Originally Posted by yxunomei

Hi,

Code:

---

prev = loc;
"Panda" -> NULL
  ^

---

---

ok this confuses me. loc is pointing to start
hence: loc = *start; and not null is this an error?

Quote:

---

Originally Posted by jafet

You don't understand the code, or the concept?

If it's the latter, you might enjoy [url=http://www.cprogramming.com/tutorial/lesson15.html]this[/rul] and/or this.

---

[/QUOTE]

the code :(

did u mean the start of the 2nd call of addElement?

the if statement in addElement fail, because the second time u feed addElement with *start in main, *start isn't NULL anymore, therefore it gets to the else case

Code:

---

void addElement (charNode **start, const char *petName)
{
  charNode *temp = newNode(petName); /* assuming this works. */

  if ( *start == NULL )
      *start = temp;
  else
  {
      temp->next = (*start)->next;
      (*start)->next = temp;
      printf(" %s ", temp->petsName);
  }
  return;
}

---

I think that's all that you need. I don't know why you are passing things the way you are, but I'm not making it my business.

yep i understand that perfectly but

in this line of code:

Code:

---


prev = loc;

---

takes loc's reference and asssigns it to prev.. so they both point to start because at the satrt of the else statement :

Code:

---


loc = *start;

---

but in the for loop, loc moves and stops once it reached the end of the list yes?

Code:

---

for (i=0; loc != NULL; i++)

---

and there's this statement at the end of the for loop (the one u were asking)

Code:

---

prev = loc;

---

it says, hey prev, copy whatever address loc has, and then the next statement

Code:

---

loc = loc->next;

---

loc moves, but prev stays where it was

Code:

---

void insertnode(struct node **head, char *data)
{
    struct node *newnode =  getnode();
    struct node *Tempnode;
   
    strcpy(newnode->data,data);
    newnode->next = NULL;
   
    if(*head == NULL)
        *head = newnode;
    else
    {
        Tempnode = *head;
       
        while(Tempnode->next != NULL)
                Tempnode = Tempnode->next;
       
        Tempnode->next = newnode;
    }
}

---

here is sample code which will help you in understanding the concept. go though it again and again. Find the diff of what u have done and what i have done.

ssharish2005

When you insert a node into a singly linked list, you only need to adjust the next pointers at the two adjoining locations of oldItem and newItem. There shouldn't really be a need to use for loops or anything like that unless addElement is trying to do something that I'm not aware of.

I think the for loop is messing up everything. If I wanted to insert a node in the middle of your list, things would get really interesting.

I think the thread starter wanted to append item to the list already there... therefore, addElement only care about getting into the last thing in the list, and appending the new element....

isnt a loop necessary to traverse the list till you find where you want to insert?

No. Typically, you could just pass a pointer to where you want to insert something instead. And then pass a pointer to whatever "something" is and it can be done.

Continuing with the example that makes nodes, however:

Code:

---

addElement(head->next, "second item");

---

guys,

thanks alot most of the hints helped alot. With ssharish's code its somewhat more easier to follow maybe because it has less variables and more meaningful variable names? and essentially my code does the same thingn... it keeps looping till the end and checks if the nodes next element is not null till we find one thats null so we can insert the new node? am i right?

Quote:

---

Originally Posted by ssharish2005

Code:

---

void insertnode(struct node **head, char *data)
{
    struct node *newnode =  getnode(); // assume that getnode is a function that malloc's a new node and returns a reference.
    struct node *Tempnode;
   
    strcpy(newnode->data,data); // insert some data into the struct
    newnode->next = NULL; // set the new nodes proceeding node to null so we don't run into endless loops..
   
    if(*head == NULL) // this will be used only for the first element.
        *head = newnode;
    else
    {
        Tempnode = *head; // set tempnode to point to head (the start of the list)
       
        while(Tempnode->next != NULL)
                Tempnode = Tempnode->next; // here we just scan through the whole list till we reach the end (NULL)
       
        Tempnode->next = newnode; // we then insert the new node
    }
}

---

---

If you're implying that how you name variables is bad, I don't think so. However, I do notice that ssharish's code is consistant in indentation. That can do wonders for legibility.

and here i've shortended to code even more, i guess it's easier to understand:

Code:

---


          for (prev=NULL; loc != NULL; loc = loc->next)
              {
                        prev = loc;
              }
             
            prev->next = temp;

---

Quote:

---

Originally Posted by Axel

and here i've shortended to code even more, i guess it's easier to understand:

Code:

---


          for (prev=NULL; loc != NULL; loc = loc->next)
              {
                        prev = loc;
              }
             
            prev->next = temp;

---

---

check for loc->next is not equal to null

ssharish2005

wouldn'tt that already be handled when i malloc the new node?

noo. the reason why i said, when u interate through each node u will check for the last node.The way u can find is that the last node next should be null. So when u check for loc->next is equal to null u will come to know that u reached end of the node. and then u can follow with appending a new node.

ssharish2005

Quote:

---

Originally Posted by Axel

and here i've shortended to code even more, i guess it's easier to understand:

Code:

---


          for (prev=NULL; loc != NULL; loc = loc->next)
              {
                        prev = loc;
              }
             
            prev->next = temp;

---

---

this is not quite rite :) ...

say u have

Code:

---

"Panda" -> NULL

---

on the first iteration, loc = *start yes?
and then you assign prev to loc...

Code:

---

prev = loc;

---

and after that, the for loop checks the nullity of loc

Code:

---

for (prev=NULL; loc != NULL; loc = loc->next)

---

.. in this case, no... and then loc goes to the next element which is null...

Code:

---

for(..., loc = loc->next)

---

which is a problem ;) because after that

Code:

---

prev = loc; // prev becomes null (but we don't want it to be)

---

remember in linked list, the last element isn't denoted by NULL... it's denoted by the last item BEFORE NULL
NULL is just like '\0' character in string.

got me? this is exactly what ss was saying

ok i think i've understood my original code now please correct me if i'm wrong.

We have the first element, Cat already added so:

Code:

---

if (*start == NULL)

---

evaluates to false so we go to the else bit.

Code:

---


else
  {
      loc = *start; // MAKE loc point to the start of the list.
      prev = NULL;

      for (i=0; loc != NULL; i++) //here we just loop till we find an empty position to append to
      {
 
                  prev = loc; // keep track of the previous node by copying what the current node equals to
                loc = loc->next; // set loc to the next node
        }

---

Code:

---


once the loop ends it means we have found an empty position i.e.:

[  CAT  ]    [ NULL ] 

prev              loc

 so:

 prev->next = temp;

we just insert the new node AFTER prev->next i.e.:


[  CAT  ]    [ DOG (new node inserted) ]

prev      - >  next

---

i don't see why you need the i in

Code:

---

for (i=0; loc != NULL; i++)

---

just do something like

Code:

---

for(loc = *start; loc != NULL; loc = loc -> next)

---

this, not only you make it easier to understand, but also make your code shorter because then you can take out the

Code:

---

loc = *start

---

at the start of the else bit.

better yet

Code:

---

for(loc = *start; loc->next != NULL; loc = loc->next) {
  // do nothing, it's all done in the loop
}

loc->next = temp;

---