linked list segfault error. c

Question

I have to write this code that makes a linked list. The following code is below. The problem is that I am segfaulting somewhere in the code and I can't figure out where. If anyone could help me find and understand (that's the most important part) where the segfault is coming from, it would be greatly appreciated.

#include "linkedlist.h"
#include <stdio.h>
#include <stdlib.h>


/* Alloc a new node with given data. */
struct ListNode* createNode(int data) {
    struct ListNode *new_node = (struct ListNode *)malloc(sizeof(struct ListNode));
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}

/* Insert data at appropriate place in a sorted list, return new list head. */
struct ListNode* insertSorted(struct ListNode* head, int inputData)
{

    struct ListNode * nextIS = NULL;
    struct ListNode * newNodeIS = NULL;
    struct ListNode * currIS = head;
    struct ListNode * listHeadIS = currIS;
    if (currIS == NULL)
    {
        listHeadIS = createNode(inputData);
        return listHeadIS;
    }
    while (currIS->next != NULL)
    {
        nextIS = currIS->next;

        if (currIS->data < inputData)
        {
            if (nextIS->data >= inputData)
            {

                nextIS->next = createNode(inputData);
                newNodeIS = nextIS->next;
                if (newNodeIS->data > listHeadIS->data)
                {
                    listHeadIS = newNodeIS;
                }
            }
        }
        currIS = currIS->next;
    }

    return listHeadIS;
}
/* Remove data from list pointed to by headRef, changing head if necessary.
 * Make no assumptions as to whether the list is sorted.
 * Memory for removed node should be freed.
 * Return 1 if data was present, 0 if not found. */
int removeItem(struct ListNode** headRef, int data)
{
    while (*headRef && (*headRef)->data != data)
        headRef = &(*headRef)->next;

    if (*headRef)
    {
        struct ListNode *tmp = *headRef;
        free(tmp);
        *headRef = tmp->next;

        return 1;
    }
    return 0;
}

/* Insert data at head of list, return new list head. */
struct ListNode* pushStack(struct ListNode* head, int data)
{
    int dataPush = data;

    struct ListNode * tempPush = (struct  ListNode*)malloc(sizeof(struct ListNode));
    tempPush->data = dataPush;
    tempPush->next = head;
    *head = *tempPush;
    return tempPush;
}

/* Remove and return data from head of non-empty list, changing head.
 * Memory for removed node should be freed. */
int popStack(struct ListNode** headRef)
{
    struct ListNode * tempPop = *headRef;
    int tempData;

    free(tempPop);
    tempData = tempPop->data;
    tempPop = tempPop->next;

    return tempData;
}

/* Return length of the list. */
    int listLength(struct ListNode* head)

 {
   int count = 0;
    struct ListNode* current = head;
    while (current != NULL) {
    count++;
    current=current->next;
  }
   return(count);
}

/* Print list data on single line, separated with spaces and ending
 * with newline. */
void printList(struct ListNode* head)
{

    if (head != NULL)
    {

        while (head->next != NULL)
        {

            printf("%d\n", head->data);
            head = head->next;
        }
    }
}
/* Free memory used by the list. */
void freeList(struct ListNode* head)
{
    struct ListNode* tmp;

    while (head != NULL)
    {
        tmp = head;
        head = head->next;
        free(tmp);
    }
}

/* Reverse order of elements in the list */
void reverseList(struct ListNode** headRef)
{
    struct ListNode * origRL = *headRef;
    struct ListNode * nextRL = NULL;
    struct ListNode * prevRL = NULL;
    while (origRL->next != NULL);
    {
        nextRL = origRL->next;
        prevRL = origRL;
        origRL = nextRL;
        origRL->next = prevRL;
   }

}

The file used to test it (linkedlist.c) is included below this comment.

#include <stdio.h>
#include <stdlib.h>
#include "linkedlist.h"

int main(int argc, char** argv)
{
  int i, n;
  struct ListNode* head = NULL;
  struct ListNode* stack = NULL;

  printf("empty list: ");
  printList(head);

  for(i = 0; i < 23; ++i)
  {
    n = (i*17+11) % 23;
    head = insertSorted(head, n);
    stack = pushStack(stack, n);
  }

  printf("filled list: ");
  printList(head);
  printf("list length = %d\n", listLength(head));

  printf("filled stack: ");
  printList(stack);
  printf("stack size = %d\n", listLength(stack));

  for(i = -4; i < 25; i+=4)
  {
    n = removeItem(&head, i);
    if(!n) printf("remove did not find %d\n", i);  
  }

  printf("list after removes: ");
  printList(head);
  printf("list length = %d\n", listLength(head));

  for(i = 0; i < 5; ++i)
  {
    printf("pop: %d\n", popStack(&stack));
  }

  printf("stack after pops: ");
  printList(stack);
  printf("stack size = %d\n", listLength(stack));

  reverseList(&head);
  printf("list after reverse: ");
  printList(head);

  freeList(head);
  head = NULL;

  freeList(stack);
  stack = NULL;

  return 0;
}

the expected output is

empty list: 
filled list: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 
list length = 23
filled stack: 17 0 6 12 18 1 7 13 19 2 8 14 20 3 9 15 21 4 10 16 22 5 11 
stack size = 23
remove did not find -4
remove did not find 24
list after removes: 1 2 3 5 6 7 9 10 11 13 14 15 17 18 19 21 22 
list length = 17
pop: 17
pop: 0
pop: 6
pop: 12
pop: 18
stack after pops: 1 7 13 19 2 8 14 20 3 9 15 21 4 10 16 22 5 11 
stack size = 18
list after reverse: 22 21 19 18 17 15 14 13 11 10 9 7 6 5 3 2 1 

Answer 1

Your segfault is happening in the pushStack() function. The line *head = *tempPush makes no sense here. When you pass in a NULL pointer for head, this attempts to dereference it, leading to the segfault. You can remove this line, and remove the unnecessary variable dataPush. Also, there is no reason to cast the result of malloc(), and it is better to use the pointer that you are assigning to as the argument for sizeof(). If the type is later changed, avoiding using an explicit type in sizeof() means fewer thing to remember to update. That means that the new pushStack() function is:

struct ListNode * pushStack(struct ListNode *head, int data)
{
    struct ListNode *tempPush = malloc(sizeof(*tempPush));
    tempPush->data = data;
    tempPush->next = head;

    return tempPush;
}

Your insertSorted() function contains an error. I am not exactly sure where this is; your function is more complicated that it needs to be, so I just wrote a new one for you. Similarly, your printList() function can be streamlined. I also modified the printList() function to match the expected output example that you provided:

struct ListNode * insertSorted(struct ListNode *head, int inputData)
{
    struct ListNode *prev = NULL;
    struct ListNode *curr = head;
    struct ListNode *new_node = createNode(inputData);

    while (curr) {
        if (inputData < curr->data) {
            new_node->next = curr;
            if (prev)
                prev->next = new_node;
            return (prev ? head : new_node);
        }
        prev = curr;
        curr = curr->next;
    }
    if (head) {
        new_node->next = NULL;
        prev->next = new_node;
    } else {
        head = new_node;
    }

    return head;
}

void printList(struct ListNode *head)
{
    struct ListNode *curr = head;

    while (curr) {
        printf("%d ", curr->data);
        curr = curr->next;
    }
    putchar('\n');
}

With these changes, the output is starting to match your expectations. There is a problem in your listLength() function, and there is a problem in your popStack() function. There may be further problems as well. I will let you wrestle with these issues; my suggestions should get you started. If you continue to have problems, send me a comment and I will try to help further.