Segmentation fault in C while implementing deque

Question

I am trying to implement a deque in C. I am learning C, so the error might seem very trivial. Here's the entire program

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

typedef struct node{
    int data;
    struct node *prev;
    struct node *next;
}Node;

Node *getNode(int data){
    Node *temp = (Node *)malloc(sizeof(Node));
    temp -> next = temp -> prev = NULL;
    temp -> data = data;
    return temp;
}

void push_right(Node **head, Node **tail, int data){
    Node *newNode = getNode(data);
    Node *temp = (*head);
    if (temp == NULL){
        *head = newNode;
    }   
    else{
        while(temp -> next != NULL){
            temp = temp -> next;
        }
        temp -> next = newNode;
        newNode -> prev = temp;
        *tail = newNode;
    }
}

void push_left(Node **head, Node **tail, int data){
    Node *newNode = getNode(data);
    Node *temp = (*head);
    if (temp == NULL){
        *head = newNode;
    }   
    else{
        newNode -> next = temp;
        newNode -> prev = NULL;
        (*head) = newNode;
    }
}

void remove_right(Node **head, Node **tail, int *val){
    Node *temp = (*tail);
    if (temp == NULL)
    {
        printf("Cannot be removed doesn't point to anything\n");
        return;
    }
    else{
        *val = temp -> data;
        temp = temp -> prev;
        (*tail) = temp;
    }
    free(temp);
}

void remove_left(Node **head, Node **tail, int *val){
    Node *temp = (*head);
    if (temp == NULL)
    {
        printf("Cannot be removed doesn't point to anything\n");
        return;
    }
    else{
        *val = temp -> data;
        temp = temp -> next;
        (*tail) = temp;
    }
    free(temp);
}

void print_all(Node *head){
    Node *temp = head;
    printf("\n");
    while(temp != NULL){
        printf("%d\n",temp->data);
        temp = temp -> next;
    }
}

int main(int argc, char const *argv[])
{
    int *val = NULL;
    Node *head = NULL;
    Node *tail = NULL;
    for (int i = 0; i < 10; ++i){
        push_right(&head, &tail,i);
        push_left(&head, &tail,i);
    }
    remove_left(&head, &tail, val);
    print_all(head);
    return 0;
}

The problem seems to arise when remove_left() is called. I have spend a significant amount of time to understand where the problem is coming from but nothing seems to work. Please help.

This is the output on the Terminal screen.

lib2s-iMac:queue admin$ ./a.out 
Segmentation fault: 11

These articles are very helpful for debugging a program: https://ericlippert.com/2014/03/05/how-to-debug-small-programs/ https://stackoverflow.com/questions/2069367/how-to-debug-using-gdb https://ericlippert.com/2014/03/21/find-a-simpler-problem/ and yes, I consider the third one to be a debugging method, too. — Yunnosch, Jul 13 '18 at 07:21
After the very first call to `push_right`, `tail` is still `NULL`. It should be the same as `head`. Start here. — Jabberwocky, Jul 13 '18 at 07:26
When you've got a doubly-linked list, then all modifying operations must **always** modify both the `prev` **and** `next` links. Your `remove`s do not do so. — Antti Haapala -- Слава Україні, Jul 13 '18 at 07:27
And please use some autoindenting tool before posting code, and when pasting code into the question, you can make it into a code block by selecting it and pressing Ctrl+K, or the `{ }` button from the toolbar. — Antti Haapala -- Слава Україні, Jul 13 '18 at 07:29
You didn't allocate memory for `val` pointer - call `val = malloc(sizeof(int))`. In `remove_left` you should update `head` instead of `tail`. — rafix07, Jul 13 '18 at 07:30

Olivier Cazade · Answer 1 · 2018-07-13T08:46:11.047

1

Problem is here :

*val = temp -> data;

Val is NULL, so trying to dereference it will result in segmentation fault.

If you change val type to an int instead of a pointer to an int. And then call remove_left like this :

int main(int argc, char const *argv[])
{   int val = 0;
    Node *head = NULL;
    Node *tail = NULL;
    for (int i = 0; i < 10; ++i){
        push_right(&head, &tail,i);
        push_left(&head, &tail,i);
    }

    remove_left(&head, &tail, &val);
    print_all(head);
    return 0;
}

This should work.

edited Jul 13 '18 at 08:46

answered Jul 13 '18 at 07:34

Olivier Cazade

777
5
10

Even after this change, the program is still dereferencing a dangling pointer in `print_all`: https://taas.trust-in-soft.com/tsnippet/t/6c9b0c3e – Pascal Cuoq Jul 13 '18 at 08:30
you can't assign NULL to int because you get warning initialization makes integer from pointer without a cast – Nick S Jul 13 '18 at 08:39
@NickS You are right, I missed some change due to needed when val type change. I will edit it. – Olivier Cazade Jul 13 '18 at 08:45
@PascalCuoq Indeed, remove functions have some flaws. – Olivier Cazade Jul 13 '18 at 08:48

score 1 · Answer 2 · answered Jul 13 '18 at 08:58

In your program have 3 main mistakes .

At int *val = NULL; Here it should be int val not int *val.
At function remove_left() . Here You should edit (*head) not (*tail).Also pointer (next,perv) are not managed properly.
Same in the case of remove_right(). Mistakes in managing pointers.

Modified Functions :-

void remove_right(Node **head, Node **tail, int *val)   // modified This function.
{
    Node *temp = (*tail);
    if (temp == NULL)
    {
        printf("Cannot be removed doesn't point to anything\n");
        return;
    }

    else
    {
        *val = temp->data;
        temp->prev->next = NULL;
        (*tail) = temp->prev;
    }
    free(temp);
}

void remove_left(Node **head, Node **tail, int *val)   // modified This function.
{
    Node *temp = (*head);
    if (temp == NULL)
    {
        printf("Cannot be removed doesn't point to anything\n");
        return;
    }

    else
    {
        *val = temp->data;
        temp->next->prev = NULL;
        (*head) = temp->next;
    }
    free(temp);
}

Modified main() :-

int main(int argc, char const *argv[])
{
    int val = -1;                         // Modified here
    Node *head = NULL;
    Node *tail = NULL;
    for (int i = 0; i < 10; ++i)
    {
        push_right(&head, &tail, i);
        push_left(&head, &tail, i);
    }
    remove_left(&head, &tail, &val);
    print_all(head);
    return 0;
}

Complete code Online.

Output :-

Also, suggest OP not to cast `malloc` in `getnode()`, +1 – WedaPashi Jul 13 '18 at 10:19 — WedaPashi, Jul 13 '18 at 10:19

Segmentation fault in C while implementing deque

2 Answers2