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

This is a discussion on i can't seem to understand the logic behind linked lists :| within the C Programming forums, part of the General Programming Boards category; Ok i've made my code really simplistic to tackle the problem i'm having currently of understanding how linked lists work. ...

  1. #1
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335

    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;
       }
    }

  2. #2
    The C eater *munch*
    Join Date
    Oct 2006
    Posts
    101
    Hi,

    first of all, on the typdef line, do something actually useful
    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 )
    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
    Last edited by yxunomei; 10-14-2006 at 02:13 AM.

  3. #3
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    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.
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  4. #4
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    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

  5. #5
    The C eater *munch*
    Join Date
    Oct 2006
    Posts
    101
    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

  6. #6
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,627
    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.

  7. #7
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    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;

  8. #8
    The C eater *munch*
    Join Date
    Oct 2006
    Posts
    101
    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

  9. #9
    Registered User ssharish2005's Avatar
    Join Date
    Sep 2005
    Location
    Cambridge, UK
    Posts
    1,682
    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
    Last edited by ssharish2005; 10-14-2006 at 02:42 AM.

  10. #10
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,627
    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.

  11. #11
    The C eater *munch*
    Join Date
    Oct 2006
    Posts
    101
    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....

  12. #12
    and Nothing Else Matters
    Join Date
    Jul 2006
    Location
    Philippines
    Posts
    117
    isnt a loop necessary to traverse the list till you find where you want to insert?
    It is not who I am inside but what I do that defines me.

  13. #13
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,627
    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");

  14. #14
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    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
        }
    }
    Last edited by Axel; 10-14-2006 at 03:34 AM.

  15. #15
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,627
    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.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  2. Map file formats and linked lists
    By Spitball in forum Game Programming
    Replies: 2
    Last Post: 03-04-2004, 10:32 PM
  3. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 08:57 PM
  4. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 06:25 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21