Segmentation Fault error - Implementing Stack using Linked lists

Question

I am currently in a University program studying Data Structures in C and I am having a lot of trouble right now. I want to make clear that what I am asking help for is not for marks, just practice challenge problems.

The goal is to implement a stack using Linked Lists. By looking through the lecture notes I think I have most of the functions down. I need to demonstrate Push() and Pop() will an append and a pretend. Using Cygwin, I compiled with no errors. but when I try to run it, I get a "Segmentation Fault". What does this mean and how do I fix it? if I remove "stack = initLListStack();", the error disappears. Here is my code:

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

typedef struct Link{
int *value;
struct Link *next;
}Link;

typedef struct LList1{
int *size;
Link *head;
}LList1;

typedef struct LListStack{
LList1 *llist;
}LListStack ;


LListStack *initLListStack(void)
{
LListStack *stack = (LListStack *) malloc(sizeof(LListStack)) ;
stack->llist->size = 0;
stack->llist->head = NULL;
return(stack);
}


void removefront(LList1 *llist)
{
if(llist->head != NULL){
    llist->head = llist->head->next;
    llist->size--;
}
}

Link *FindLastLink(LList1 *llist, Link *link)
{
if(link = NULL){
    return(NULL);
}
else if(link->next == NULL){
    return(link);
}
else{
    return(FindLastLink(llist, link->next));
}
}

Link *FindSecondLastLink(LList1 *llist, Link *link)
{
if(link = NULL){
    return(NULL);
}
else if(link->next->next == NULL){
    return(link);
}
else{
    return(FindSecondLastLink(llist, link->next));
}
}

void removelast(LList1 *llist)
{
Link *secondlastlink = (Link *) malloc(sizeof(Link));
secondlastlink = FindSecondLastLink(llist, llist->head);
secondlastlink->next = NULL;
llist->size--;

}



void prepend(int *newValue, LList1 *templist)
{
Link *node = (Link *) malloc(sizeof(Link)); 
node->value = newValue; 
node->next = templist->head;
templist->head = node;
templist->size++;
}

void append(int *newValue, LList1 *templist)
{
Link *node = (Link *) malloc(sizeof(Link));
Link *lastlink = (Link *) malloc(sizeof(Link));
lastlink = FindLastLink(templist, templist->head);
node->value = newValue;
lastlink->next = node;
node->next = NULL;
templist->size++;
}

void prepush(int *value, LListStack *stack)
{
 prepend(value, stack->llist);
}

void apppush(int *value, LListStack *stack)
{
append(value, stack->llist);
}

int prepop(LListStack *stack, int *value)
{ 
int result ;

if ((!isEmpty(stack)))
{
    removefront(stack->llist);
    result = 1 ;

}
else {
    result = 0 ;
}
return(result) ;
}

int isEmpty(LListStack *stack) 
{ 
int empty;

if (stack->llist->head == NULL) 
    return( 1 ) ;
else
    return( 0 ) ;
}

int apppop(LListStack *stack, int *value)
{ 
int result ;

if ((!isEmpty(stack)))
{
    removelast(stack->llist);
    result = 1 ;
}
else 
    result = 0 ;

return(result) ;
}

//*******MAIN**********//

int main()
{
LListStack *stack = (LListStack *) malloc (sizeof(LListStack));

stack = initLListStack(); //if I take this away, I can run the program


return(0);
}

I don't have that much in Main() yet because I'm just trying to get it to run first. Initializing the Stack seems to be the problem.

Thanks for your help guys!

score 1 · Accepted Answer · answered Sep 30 '13 at 01:58

The problem is in your initLListStack() function:

LListStack *stack = (LListStack *) malloc(sizeof(LListStack)) ;
stack->llist->size = 0;
stack->llist->head = NULL;
return(stack);

The result of malloc is an uninitialized block of memory large enough to hold an LListStack struct.

The very first thing you do with that memory is read its llist member. Since this is uninitialized, you invoke undefined behavior which, fortunately, causes a segfault. (The compiler would be within the specification to send embarrassing e-mails to our instructor when this happens.)

You need to initialize llist before you can use that member in stack. Something like:

LListStack *stack = malloc(sizeof(*stack));
stack->llist = malloc(sizeof(*stack->llist));
stack->llist->size = 0;
stack->llist->head = NULL;
return stack;

Note that I've also removed some unnecessary casts and parentheses, and changed the sizeof operator to calculate the memory you need based on the pointer you're storing into.

Thank you so much! That worked. Just a questions 1) I see you took out the "(LListStack *)" before malloc. What is the point of that. My professor has been telling us to include it before malloc, but i'm not sure what it does, since everywhere I've been reading doesn't do it. — dvdmarc12, Sep 30 '13 at 04:08
You're professor apparently lives by C++ or doesn't consider all the things that a *non-required* cast can do if your program isn't properly setup. Standard C does not require casting from `void*` to any other pointer type. [Don't cast the result of malloc in standard C](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc). — WhozCraig, Sep 30 '13 at 06:10

Charlie Burns · Answer 2 · 2013-09-30T01:56:22.770

LListStack *initLListStack(void)
{
  LListStack *stack = (LListStack *) malloc(sizeof(LListStack)) ;
  stack->llist->size = 0; // **this is probably where it crashes**
  stack->llist->head = NULL;
  return(stack);
}

You allocate stack ok, but you do not allocate stack->llist. So stack->llist is uninitialized and then you dereference it in stack->llist->size . Dereferencing an uninitialized variable results in undefined behavior.

To fix this, allocate stack->list like this:

LListStack *initLListStack(void)
{
  LListStack *stack = (LListStack *) malloc(sizeof(LListStack)) ;
  stack->llist = (LListStack *) malloc(sizeof(LList1)) ; // ADD THIS LINE
  stack->llist->size = 0; 
  stack->llist->head = NULL;
  return(stack);
}

score 0 · Answer 3 · answered Sep 30 '13 at 01:52

A segmentation fault error is usually caused by trying to dereference an uninitialized pointer. In your case, you have allocated memory for stack in your initLListStack method but you haven't initialized it -- in particular the llist field is not initialized to any particular value. You need to allocate an LList1 and set the llist field to the newly-allocated memory.

Segmentation Fault error - Implementing Stack using Linked lists

3 Answers3

Linked