Thread: Segmentation Fault in Doubly Linked List Program.. Can not figure out why

  1. #1
    Registered User
    Join Date
    Nov 2020
    Posts
    6

    Segmentation Fault in Doubly Linked List Program.. Can not figure out why

    I'm new to C and have spent the past two days pulling my hair out over this issue. Everything in my code seems to line up with what I've researched, but I still keep getting a Segmentation Fault error. I have tried so hard to fix this but I can not spot what I'm doing wrong.

    Here is my struct:
    Code:
    struct MovieType {
        unsigned int id;
        char movie_title[NAME_LENGTH];
        int year; 
    };
    
    typedef struct Node {
        struct MovieType *data; //contains node item
        struct Node *next;
        struct Node *prev;
        } NodeType;
    
    struct ListType {
        struct Node *head;
        struct Node *tail;
        int nextid;
    };
    And here is the function which gives me the error - it works up until the contents of if (currNode->next == NULL).
    Code:
     
    void addMovieToList(enum SortType s, struct ListType *list, struct MovieType *m) {
    
        NodeType *newNode;
        NodeType *currNode;
        NodeType *prevNode;
        currNode=list->head;
        prevNode=NULL;
    
        newNode=(NodeType *) malloc(sizeof(NodeType));
        if (newNode == NULL) {
            printf("mem allocation error");
            exit(0);
        }
        newNode->data=m;
        newNode->data->id=list->nextid;
    
        if (currNode == NULL)
        {
            newNode->next = NULL;
            newNode->prev = NULL;
            list->head = newNode;
            list->tail = newNode;
            return;
            }
        if (currNode->next == NULL) {
            list->head = newNode;
            newNode->next = currNode;
            newNode->prev = NULL;
            currNode->prev = newNode;
            return;
            }
        while (currNode->next != NULL)
        {
            list->head = newNode;
            newNode->next = currNode;
            newNode->prev = NULL;
            currNode->prev = newNode;
            return;
            currNode = currNode->next;
        }
        currNode->next = newNode;
        newNode->prev = currNode;
        list->tail = newNode;
    }
    In my main function, I allocate memory for the lists, initialize the movie and then call this addMovieToList function. I can add the code for that here but the program seems to lie in the above function, as when I remove it everything works smoothly.
    Any help would be appreciated.. Thank you.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,304
    I think you're doing way too much work.

    If your aim is to prepend the new node, then:
    Code:
    new node's prev node = null
    if list is empty
        new node's next node = null
        tail = new node
    else
        new node's next node = head
        head's prev node = new node
    head = new node
    If your aim is to append the new node, then:
    Code:
    new node's next node = null
    if list is empty
        new node's prev node = null
        head = new node
    else
        new node's prev node = tail
        tail's next node = new node
    tail = new node
    Either way, you definitely don't need a loop because you're keeping track of both the head and the tail. You would only need a loop if say, you were trying to insert in the middle so as to maintain ordering by movie title or something like that.

    I would also be concerned about this line:
    Code:
    newNode->data=m;
    This assumes that the caller is correctly managing the memory for the struct MovieType object. If that is not done correctly, you could get a segmentation fault.

    EDIT:
    Oh, I didn't notice that you need to set the previous node pointer too, so I've updated my pseudocode.
    Last edited by laserlight; 11-12-2020 at 09:44 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Nov 2020
    Posts
    6
    Laserlight, thank you for the advice. I'm going to condense it right now.
    The memory for MovieType is initialized like so:
    Code:
      *m = (struct MovieType *) malloc(sizeof(struct MovieType));
        if (m == NULL) {
            printf("Memory allocation error\n");
            exit(0);
        }
    Would I need to free m every time after I add each movie to the list? Do you think that's the only place the segmentation error could be coming from?
    Thank you!

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,304
    Quote Originally Posted by Elenasnow
    Would I need to free m every time after I add each movie to the list? Do you think that's the only place the segmentation error could be coming from?
    No, you don't want to do that at all. You want the memory to remain allocated until you are done with it, which is probably when you have no more use for that node or for the entire linked list. It is a premature deallocation of the memory for the struct MovieType object that can result in a segmentation fault.

    Note that if this is literally what you wrote, then it is probably wrong and should result in at least a compile warning:
    Code:
    *m = (struct MovieType *) malloc(sizeof(struct MovieType));
    You probably wanted to write:
    Code:
    m = (struct MovieType *) malloc(sizeof(struct MovieType));
    But I would recommend:
    Code:
    m = malloc(sizeof(*m));
    EDIT:
    I think it would be helpful to explain how do you intend to insert the new node. Are you prepending, appending, or inserting in another manner (e.g., you do have an enum SortType s parameter)? It looks like you're correctly prepending when the list is either empty or only has one element, but I don't understand what the loop is for. The loop condition makes it sound like you want to append, but that's inconsistent with what you do when the list only has one element, and then the return statement in the loop body means the loop really only runs for at most one iteration.
    Last edited by laserlight; 11-12-2020 at 10:09 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    Nov 2020
    Posts
    6

    Post

    Quote Originally Posted by laserlight View Post
    I think it would be helpful to explain how do you intend to insert the new node. Are you prepending, appending, or inserting in another manner (e.g., you do have an enum SortType s parameter)? It looks like you're correctly prepending when the list is either empty or only has one element, but I don't understand what the loop is for. The loop condition makes it sound like you want to append, but that's inconsistent with what you do when the list only has one element, and then the return statement in the loop body means the loop really only runs for at most one iteration.
    Mostly right now I'm just trying to append the node to the list, eventually I want to sort it based on the list contents but right now I'm just focusing on getting rid of the segmentation error, I made the recommended changes but still can't manage to figure out what I'm doing to cause it..
    Last edited by Elenasnow; 11-12-2020 at 10:39 PM.

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,304
    What is your current code?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Registered User
    Join Date
    Nov 2020
    Posts
    6
    Quote Originally Posted by laserlight View Post
    What is your current code?
    This is what I have at the moment, sorry if it's a little messy:
    Code:
    //define
    #define NAME_LENGTH 20
    #include "stdlib.h"
    #include "stdio.h"
    #include "string.h"
    
    //structures
    struct MovieType {
        unsigned int id;
        char movie_title[NAME_LENGTH];
        int year; 
    };
    
    typedef struct Node {
        struct MovieType *data; //contains node item
        struct Node *next;
        struct Node *prev;
        } NodeType;
    
    struct ListType {
        struct Node *head;
        struct Node *tail;
        int nextid;
    };
    
    struct ArrayType {
      int size;
      struct MovieType **items;
    };
    
    enum SortType {
        BY_TITLE,
        BY_YEAR
    };
    
    void initMovie(char*, int, struct MovieType**);
    
    void initMovie(char *t, int y, struct MovieType **m)
    {
        *m = (struct MovieType *) malloc(sizeof(struct MovieType));
        if (m == NULL) {
            printf("Memory allocation error\n");
            exit(0);
        }
        strcpy((*m)->movie_title, t);
        (*m)->year = y;
       // printf("%s, %d \n", (*m)->movie_title, (*m)->year);
    }
    
    void addMovieToList(enum SortType s, struct ListType *list, struct MovieType *m) {
    
        NodeType *newNode;
        NodeType *currNode;
        NodeType *prevNode;
        currNode=list->head;
        prevNode=NULL;
    
        newNode=(NodeType *) malloc(sizeof(NodeType));
    
        if (newNode == NULL) {
            printf("mem allocation error");
            exit(0);
        }
        newNode->data=m;
        newNode->data->id=list->nextid;
    
        if (currNode == NULL)
        {
            newNode->next = NULL;
            list->tail = newNode;
            return;
            }
    
        else {
            newNode->next = list->head;
            list->head->prev = newNode;
            return;
            }
        list->head=newNode;
    }
    
    void printList(struct ListType *list)
    {
      NodeType *currNode = list->head;
      NodeType *prevNode = NULL;
      printf("Printing forwards \n");  
      while (currNode != NULL) {
        printMovie(currNode->data);
        prevNode = currNode;
        currNode = currNode->next;
      }
       
        printf("Printing backwards \n");
        
        currNode = list->tail;
        prevNode = NULL;
    
        while (currNode != NULL) {
        printMovie(currNode->data);
        prevNode = currNode;
        currNode = currNode->prev;
        }
    }
    
    void printMovie(struct MovieType *m) {
        printf("%s, %d \n", (m)->movie_title, (m)->year);
    }
    
    void list_init(struct ListType *list) {;
        list = (struct ListType*)malloc(100*sizeof(struct ListType *));
        if (list == NULL) {
        printf("mem allocation error");
        exit(0);
        }
        list->head=NULL;
        list->tail=NULL;
        list->nextid=0;
    } 
    
    int main(){
        struct ListType *calvinMovies, *hobbesMovies;
        struct MovieType *m;
        list_init(calvinMovies);
        list_init(hobbesMovies);
        initMovie("Calvin Movies", 1990, &m);
        initMovie("Hobbes Movies", 1990, &m);
        addMovieToList(BY_TITLE, calvinMovies, m);
        addMovieToList(BY_TITLE, hobbesMovies, m);
        printList(calvinMovies);
        printList(hobbesMovies);
        return 0;
    }

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,304
    Here's what I suggest:
    Code:
    void addMovieToList(enum SortType s, struct ListType *list, struct MovieType *m) {
        NodeType *newNode = malloc(sizeof(*newNode));
        if (newNode == NULL) {
            printf("mem allocation error");
            exit(0);
        }
    
        newNode->data = m;
        newNode->data->id = list->nextid++;
    
        // prepend the new node to the linked list:
        newNode->prev = NULL;
        if (list->head == NULL)
        {
            newNode->next = NULL;
            list->tail = newNode;
        }
        else
        {
            newNode->next = list->head;
            list->head->prev = newNode;
        }
        list->head = newNode;
    }
    What I did:
    • Removed all the other variables that you don't need (other than the s parameter, which you indicated that you will need later)
    • Changed the malloc to the version that I recommended earlier, but it is otherwise equivalent.
    • Post-incremented the nextid, otherwise it wouldn't be a nextid the next time
    • Set the new node's previous node pointer to be a null pointer since we're prepending
    • Replaced currNode with list->head
    • Removed the early return statements that you don't need

    Notice that I also added a comment summarising to the reader that the code prepends the new node to the linked list. You wrote that "Mostly right now I'm just trying to append the node to the list", but the code that you wrote (presumably following my pseudocode) prepends instead of appending.

    It doesn't really matter right now, but you might want to return something to indicate the function failed instead of aborting when malloc returns a null pointer. If you really do want to abort, it would be more typical to write to stderr and exit with a non-zero status code, e.g.,
    Code:
    fprintf(stderr, "mem allocation error");
    exit(EXIT_FAILURE);
    This way, someone running your program could pipe stderr to an error log separate from normal output, and a shell script could check the status code to determine if your program "succeeded" or "failed".

    EDIT:
    Also, you made a mistake here:
    Code:
    void initMovie(char *t, int y, struct MovieType **m)
    {
        *m = (struct MovieType *) malloc(sizeof(struct MovieType));
        if (m == NULL) {
            printf("Memory allocation error\n");
            exit(0);
        }
        strcpy((*m)->movie_title, t);
        (*m)->year = y;
       // printf("%s, %d \n", (*m)->movie_title, (*m)->year);
    }
    Basically, your m == NULL check is wrong because you want to check the return value of malloc instead. You should check for *m == NULL. But an easier way is to do something like this:
    Code:
    void initMovie(char *t, int y, struct MovieType **m)
    {
        struct MovieType *p = malloc(sizeof(*p));
        if (p == NULL) {
            printf("Memory allocation error\n");
            exit(0);
        }
        strcpy(p->movie_title, t);
        p->year = y;
        *m = p;
    }
    That is, you introduce a local variable so that you can avoid the hassle of dereferencing the pointer to a pointer again and again.

    As a matter of good style, your parameter names should be more descriptive. A possible exception to this is when your type names already describe the variable very well (e.g., we can easily see that m refers to a movie, though it is probably still no harm to name it movie), if not it is unclear what t and y are for without reading the body of the function. Another improvement that you could make is to change the type of the title parameter to const char*. This indicates that it is safe to pass a string literal as the title because initMovie will not attempt to modify the title, and indeed your implementation of initMovie only copies the given title.
    Last edited by laserlight; 11-12-2020 at 11:22 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Registered User
    Join Date
    Nov 2020
    Posts
    6
    Laserlight, thank you so much for the suggestions, they clear up things a lot
    Are you getting a segmentation error with the code as well? Even with the new fixes I still keep getting it, so frustrated

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,304
    No, I haven't compiled and run your code.

    Looking around, you do have a problem with list_init (which really should be named initList for consistency). Notice that you used a pointer to a pointer for initMovie, but here you only have a pointer to the list itself.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    Registered User
    Join Date
    Nov 2020
    Posts
    6
    Quote Originally Posted by laserlight View Post
    No, I haven't compiled and run your code.

    Looking around, you do have a problem with list_init (which really should be named initList for consistency). Notice that you used a pointer to a pointer for initMovie, but here you only have a pointer to the list itself.
    That was the issue, omg, thank you so so much for your help!!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Segmentation fault on linked list
    By PTM in forum C Programming
    Replies: 1
    Last Post: 05-19-2018, 08:14 PM
  2. Segmentation fault in linked list program
    By smrtshrm in forum C Programming
    Replies: 5
    Last Post: 06-26-2015, 06:00 AM
  3. Segmentation fault in linked list...doubt
    By alphasil in forum C Programming
    Replies: 17
    Last Post: 07-11-2012, 05:23 PM
  4. Doubly linked list-segmentation fault
    By prapanch in forum C Programming
    Replies: 2
    Last Post: 05-10-2012, 11:04 PM
  5. Doubly Linked List Segmentation Fault
    By DaNxTh3xMaNx in forum C Programming
    Replies: 5
    Last Post: 09-09-2011, 09:50 AM

Tags for this Thread