Thread: Dont understand something in linked list

  1. #1
    Registered User
    Join Date
    Apr 2009
    Posts
    187

    Dont understand something in linked list

    oke i don't understand something in code where i was reading abt linked list i dont understand something in the code
    Code:
    /* films2.c -- using a linked list of structures */
    
    #include <stdio.h>
    
    #include <stdlib.h>      /* has the malloc prototype      */
    
    #include <string.h>      /* has the strcpy prototype      */
    
    #define TSIZE    45      /* size of array to hold title   */
    
    
    
    struct film {
    
        char title[TSIZE];
    
        int rating;
    
        struct film * next;  /* points to next struct in list */
    
    };
    
    
    
    int main(void)
    
    {
    
        struct film * head = NULL;
    
        struct film * prev, * current;
    
        char input[TSIZE];
    
    
    
    /* Gather  and store information          */
    
        puts("Enter first movie title:");
    
        while (gets(input) != NULL && input[0] != '\0')
    
        {
    
            current = (struct film *) malloc(sizeof(struct film));
    
            if (head == NULL)       /* first structure       */
    
                head = current;
    
            else                    /* subsequent structures */
    
                prev->next = current;
    
            current->next = NULL;
    
            strcpy(current->title, input);
    
            puts("Enter your rating <0-10>:");
    
            scanf("%d", &current->rating);
    
            while(getchar() != '\n')
    
                continue;
    
            puts("Enter next movie title (empty line to stop):");
    
            prev = current;
    
        }
    
    
    
    /* Show list of movies                    */
    
        if (head == NULL)
    
            printf("No data entered. ");
    
        else
    
            printf ("Here is the movie list:\n");
    
        current = head;
    
        while (current != NULL)
    
        {
    
            printf("Movie: %s  Rating: %d\n",
    
                   current->title, current->rating);
    
            current = current->next;
    
        }
    
    
    
    /* Program done, so free allocated memory */
    
        current = head;
    
        while (current != NULL)
    
        {
    
            free(current);
    
            current = current->next;
    
        }
    
        printf("Bye!\n");
    
    
    
        return 0;
    
    }
    here else /* subsequent structures */

    prev->next = current;

    wouldnt that set every time prev to current ? why did he add it in the end then ? ?

  2. #2
    Registered User
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,267
    It doesn't set prev to current, it sets prev->next to current. Basically, this just adds current to the end of the list (which is how the list is built).
    bit∙hub [bit-huhb] n. A source and destination for information.

  3. #3
    {Jaxom,Imriel,Liam}'s Dad Kennedy's Avatar
    Join Date
    Aug 2006
    Location
    Alabama
    Posts
    1,065
    Quote Originally Posted by elwad
    Code:
    /* Program done, so free allocated memory */
    
        current = head;
    
        while (current != NULL)
    
        {
    
            free(current);
    
            current = current->next;
    
        }
    
        printf("Bye!\n");
    
    
    
        return 0;
    
    }
    Don't use this part though, this is bad -- as in "all of the particles in your body instantly accelerated to the speed of light."

  4. #4
    Registered User
    Join Date
    Apr 2009
    Posts
    187
    k i somehow got it but why if i free them once can cause problems ? like it needs some delay in the loop ? for example use Sleep func of windows api ?

  5. #5
    {Jaxom,Imriel,Liam}'s Dad Kennedy's Avatar
    Join Date
    Aug 2006
    Location
    Alabama
    Posts
    1,065
    Once you free() something, it isn't yours anymore. Though this _might_ work, it ____SHOULD_____ cause a seg fault. If the OS doesn't see that as a seg fault, switch OS's.

  6. #6
    Registered User
    Join Date
    Apr 2009
    Posts
    187
    there something also i m puzzled abt in this each structure itself we dont increment address so how does it point to the next structure like for example
    int arr[]={1,2,3};
    int *ptr=*arr+1; will point to 2
    but here in this linked structure we didnt increment the address of anything so how does it point to next etc?

  7. #7
    Registered User
    Join Date
    Apr 2009
    Posts
    187
    i think i got since each time i m allocating memory each next points to the structure which comes after right ?

  8. #8
    Registered User
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,267
    If the OS doesn't see that as a seg fault, switch OS's.
    This is not an OS issue since malloc() is not an OS system call. malloc() will usually keep its own internal memory heap that is separate from the heap allocated to the application by the OS. It is perfectly plausible that a malloc() implementation will simply mark the memory block as being available for reuse without actually modifying the memory content. If you really want to blame someone, blame the standard library implementation (ie glibc), not the OS. In my opinion, this is normal behavior though.

    That being said, obviously the code is bad and no memory pointer should be used after passing it to free().
    bit∙hub [bit-huhb] n. A source and destination for information.

  9. #9
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    Quote Originally Posted by bithub View Post
    This is not an OS issue since malloc() is not an OS system call. malloc() will usually keep its own internal memory heap that is separate from the heap allocated to the application by the OS. It is perfectly plausible that a malloc() implementation will simply mark the memory block as being available for reuse without actually modifying the memory content. If you really want to blame someone, blame the standard library implementation (ie glibc), not the OS. In my opinion, this is normal behavior though.

    That being said, obviously the code is bad and no memory pointer should be used after passing it to free().
    malloc() doesn't have its own heap; it fetches storage from the pool of available memory and maps it into the address space of the process ie the heap section.

  10. #10
    Registered User
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,267
    Quote Originally Posted by itCbitC View Post
    malloc() doesn't have its own heap; it fetches storage from the pool of available memory and maps it into the address space of the process ie the heap section.
    That memory that is mapped into the address space of the process is the heap. This heap is maintained by the malloc() (and friends) implementation. Every call to malloc() does not result in an allocation call to the OS.
    bit∙hub [bit-huhb] n. A source and destination for information.

  11. #11
    {Jaxom,Imriel,Liam}'s Dad Kennedy's Avatar
    Join Date
    Aug 2006
    Location
    Alabama
    Posts
    1,065
    Quote Originally Posted by http://www.gnu.org/software/libc/manual/html_node/Freeing-after-Malloc.html#Freeing-after-Malloc
    Occasionally, free can actually return memory to the operating system and make the process smaller. Usually, all it can do is allow a later call to malloc to reuse the space. In the meantime, the space remains in your program as part of a free-list used internally by malloc.

    There is no point in freeing blocks at the end of a program, because all of the program's space is given back to the system when the process terminates.
    Birthtub is actually right this time

  12. #12
    Registered User
    Join Date
    Apr 2009
    Posts
    187
    but how prev set to current why not do it on current directly ?

  13. #13
    Registered User
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,267
    Quote Originally Posted by Kennedy View Post
    Birthtub is actually right this time
    bah, we need a new nickname for you.

    Quote Originally Posted by elwad
    but how prev set to current why not do it on current directly ?
    I'm not sure I understand the question.
    bit∙hub [bit-huhb] n. A source and destination for information.

  14. #14
    Registered User
    Join Date
    Apr 2009
    Posts
    187
    like for example here
    else /* subsequent structures */

    prev->next = current;//wont that be same next ???

    current->next = NULL;//wont that be same next??
    wont that be same next field of the structure?

  15. #15
    Registered User
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,267
    No, they are different.

    current->next = NULL would be the same as prev->next->next = NULL.
    bit∙hub [bit-huhb] n. A source and destination for information.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 10:03 AM
  2. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  3. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 09:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM