Creating a linked list in C, getting segmentation fault

Question

I need to create a linked list of nodes such that the main function is able to work; I cannot change anything in the main function. I am new to C, so I am probably making a simple mistake or two, and I am getting a segmentation fault when I try to run my code. Am I missing something obvious?

The segmentation fault happens on marked line

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

typedef struct Node{
    char *value;
    struct Node *next;
}Node;
typedef struct Node** List;

Node *new_node(char *input);
void delete_node(Node *input);
void push(List list, char *value);
List new_list();

Node *new_node(char *input) {
  Node *new;
  new = malloc(sizeof(Node));
  new->value = input;
  return new;
}

void delete_node(Node *input) {
  free(input);
}

void push(List head, char *input) {
  if (*head == NULL) {  
    *head = new_node(input);
  }
  else {
    Node *new = new_node(input);
    while ((*head)->next != NULL) {
      *head = (*head)->next;
    }
    (*head)->next = new;    
  } 
}

List new_list() {
  List list = malloc(sizeof(List));
  *list = NULL;
  return list;
}

int main( void ) {
  List list = new_list();
  push(list, "First!\n");
  push(list, "Second!\n");
  push(list, "Third!\n");
  push(list, "Fourth!");

  printf("%s", (*list)->value);
  printf("%s", (*list)->next->value);
  printf("%s", (*list)->next->next->value);       //Segmentation fault
  printf("%s", (*list)->next->next->next->value);

  return 0;
}

When I ran it with gdb I got the message:

Third!                                                                                                               

Program received signal SIGSEGV, Segmentation fault.                                                                 
0x0000000000400752 in main () at main.c:54                                                                           
54        printf("%s", (*list)->next->next->value);

Ouch! typedef struct Node** List; You will want to review: Is it a good idea to typedef pointers?. I can't believe you can't change that. It makes it so much harder to actually learn what is going on when you are hiding pointers behind a typedef. — David C. Rankin
– David C. Rankin, Commented Nov 7, 2019 at 21:38

1201ProgramAlarm · Accepted Answer · 2019-11-07 19:41:08Z

3

When you create a new node, you never set the next member of the newly created node. This leaves it uninitialized, resulting in Undefined Behavior when you dereference the pointer.

The fix is simple. Add

new->next = NULL;

into your new_node function after you assign the value.

answered Nov 7, 2019 at 19:41

1201ProgramAlarm

32.8k7 gold badges47 silver badges60 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

AskerOfQuestions Over a year ago

Thanks for the help, but the problem seems to be persisting. I am getting the same error message, except its at a different address.

1201ProgramAlarm Over a year ago

@AskerOfQuestions That's a different issue. Hint: When you push things, what are you doing with 'head'? Use your debugger to see what's really going on in there.

AskerOfQuestions Over a year ago

I've had a look with the debugger, but can't tell how to fix the problem. The values seem to set only the first and second values, and they then get overwritten by the third and fourth, because the value of *head is changing to *head->next. Is there a good way to get around this, as I cant seem to fix it?

1201ProgramAlarm Over a year ago

@AskerOfQuestions Don't change *head in push, unless it is to assign the first node. Use a local variable instead.

ChuckCottrill · Accepted Answer · 2019-11-07 23:07:22Z

Linked lists can have a single or double pointers. Single linked lists have a pointer to the next element, double linked lists have pointers to next element and previous element. You have chosen a single linked list.

Your function to add to the end of the list must traverse the entire list on every append to list operation. That means adding to the list is an O(n) complexity operation. The major benefit to a linked list is the O(1) add and remove operations, when implemented to provide that ability.

Declare the list as pointers to head (of list) and tail (of list),

typedef struct {
    Node* head;
    Node* tail;
} List;

Rather than declaring list as a pointer to pointer to node,

typedef struct Node** List;

Now, the complexity of adding to the list, and dropping from the list are O(1) (constant) time operations...

//enqueue to tail of list (not push)
void enqueue(List* list, char *input) {
  if( !list ) return; //no list
  Node* new = new_node(input); //new node
  if( NULL == list->head ) { //list empty
    list->head = new; //add at tail, tail equals head
  }
  else {
    list->tail->next = new; //list not empty, add at tail
  }
  list->tail = new;
}

//dequeue from head of list
Node* dequeue(List* list) {
    if( !list ) return NULL; //no list
    if( NULL == list->head ) return NULL; //list empty
    Node* node = list->head; //node at head of list
    list->head = list->head->next; //remove from list
    if( NULL == list->head ) list->tail = NULL; //empty now
    //oh, should also: node->next = NULL;
    return node;
}

And, as others have said, you should initialize all pointers in your 'constructor',

Node *new_node(char *input) {
  Node *new;
  if( ! (new = malloc(sizeof(Node))) ) return NULL;
  //new = calloc(sizeof(Node)); //calloc fills allocated memory with zero bytes
  //initialize all values in Node structure
  new->value = input;
  new->next = NULL; //either use calloc or init the individual elements
  return new;
}

Collectives™ on Stack Overflow

Creating a linked list in C, getting segmentation fault

2 Answers 2

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related