Passing pointers between functions in an implementation of linked list

Question

The problem was solved. A guy gave it in comments. The problem was that I was using %d to read in a short int. I should have used %hd or I should have used an `int'.

I tried to create a program of singly-linked list using only local variables. I was able to make a working program by using global variables.

The program with local variables compiles but it crashes when I try to traverse the linked list.

I have absolutely no idea what is wrong with the implementation with local variables. What is the problem present in the Implementation with local variables?

ABOUT THE STRUCTURE OF THE PROGRAMS:

I understand that the programs are big so I'll put in something about structure of the program.

The program is structured as a menu driven program. So the initial calls to functions are in main() function
There are 3 options in main() menu - exit, traverse and insertion
Exit returns 0 to exit program while other 2 do function calls
Insertion function itself is arranged as menu-driven program.
It has 3 options - return , insert_begin and insert_end. The last 2 are function calls.
I know there are memory leaks as I haven't freed any memory but I will take care of that after I can understand the problem in the current program.

//WORKING IMPLEMENTATION USING GLOBAL VARIABLE

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

#define MIN 0
#define MAX 2

#define INS_MIN 0
#define INS_MAX 2

typedef struct node
{
    int data;
    struct node *next;
}sll_node;

sll_node *start = NULL;

void intro()
{
    system("cls");
    printf("\n\tThese are the various options:\n");
    printf("\n\t00 Exit");
    printf("\n\t01 Traverse the list");
    printf("\n\t02 Insertion into the list");
}

void insert_begin()
{
    sll_node *node = malloc(sizeof(sll_node));
    if(node == NULL)
    {
        printf("\n\tNot enough menory");
        exit(-1);
    }
    int data;
    printf("\n\tData to be entered: ");
    scanf("%d", &data);

    node->data = data;
    node-> next = start;
    start = node;
}

void insert_end()
{
    sll_node *node = malloc(sizeof(sll_node));
    if(node == NULL)
    {
        printf("\n\tNot enough menory");
        exit(-2);
    }

    if(start == NULL)
        insert_begin();
    else
    {
        printf("\n\tData to be entered: ");
        scanf("%d", &(node->data));
        node-> next = NULL;

        sll_node *node2;
        for(node2 = start; node2->next != NULL; node2 = node2->next)
            ;
        node2->next = node;
    }
}

void insert_intro()
{
    system("cls");
    printf("\n\tThese are the various options:\n");
    printf("\n\t00 Insertion Done");
    printf("\n\t01 Insert at beginning");
    printf("\n\t02 Insert at end");
}

void insertion()
{
    short choice;
    while(1)
    {
        choice = -1;
        while(choice < INS_MIN || choice > INS_MAX)
        {
            insert_intro();
            printf("\n\n\tEnter your chocie: ");
            scanf("%d", &choice);
        }

        switch(choice)
        {
        case 0:
            return;
        case 1:
            insert_begin();
            break;
        case 2:
            insert_end();
            break;
        }
    }
}

void traverse()
{
    if(start == NULL)
        printf("\n\n\tLinked list is empty");
    else
    {
        printf("\n\n\t");
        for(sll_node *node = start; node != NULL; node = node->next)
            printf("%d ", node->data);
    }
    getch();
}

int main()
{
    short choice;
    while(1)
    {
        choice = -1;
        while(choice < MIN || choice > MAX)
        {
            intro();
            printf("\n\n\tEnter your choice: ");
            scanf("%d", &choice);
        }

        switch(choice)
        {
        case 0:
            return 0;
        case 1:
            traverse();
            break;
        case 2:
            insertion();
            break;
        }
    }
    return 0;
}

//COMPILES BUT CRASHES - Same program but with local variable start and variable passing between functions

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

#define MIN 0
#define MAX 2

#define INS_MIN 0
#define INS_MAX 2

typedef struct node
{
    int data;
    struct node *next;
}sll_node;

void intro()
{
    system("cls");
    printf("\n\tThese are the various options:\n");
    printf("\n\t00 Exit");
    printf("\n\t01 Traverse the list");
    printf("\n\t02 Insertion into the list");
}

sll_node* insert_begin(sll_node *start)
{
    sll_node *node = malloc(sizeof(sll_node));
    if(node == NULL)
    {
        printf("\n\tNot enough menory");
        exit(-1);
    }
    int data;
    printf("\n\tData to be entered: ");
    scanf("%d", &data);

    node->data = data;
    node-> next = start;
    return node;
}

sll_node* insert_end(sll_node *start)
{
    sll_node *node = malloc(sizeof(sll_node));
    if(node == NULL)
    {
        printf("\n\tNot enough menory");
        exit(-2);
    }

    if(start == NULL)
        start = insert_begin(start);
    else
    {
        printf("\n\tData to be entered: ");
        scanf("%d", &(node->data));
        node-> next = NULL;

        sll_node *node2;
        for(node2 = start; node2->next != NULL; node2 = node2->next)
            ;
        node2->next = node;
    }
    return start;
}

void insert_intro()
{
    system("cls");
    printf("\n\tThese are the various options:\n");
    printf("\n\t00 Insertion Done");
    printf("\n\t01 Insert at beginning");
    printf("\n\t02 Insert at end");
}

sll_node* insertion(sll_node *start)
{
    short choice;
    while(1)
    {
        choice = -1;
        while(choice < INS_MIN || choice > INS_MAX)
        {
            insert_intro();
            printf("\n\n\tEnter your chocie: ");
            scanf("%d", &choice);
        }

        switch(choice)
        {
        case 0:
            return start;
        case 1:
            start = insert_begin(start);
            break;
        case 2:
            start = insert_end(start);
            break;
        }
    }
}

void traverse(sll_node *start)
{
    if(start == NULL)
        printf("\n\n\tLinked list is empty");
    else
    {
        printf("\n\n\t");
        for(sll_node *node = start; node != NULL; node = node->next)
            printf("%d ", node->data);
    }
    getch();
}

int main()
{
    sll_node *start = NULL;
    short choice;
    while(1)
    {
        choice = -1;
        while(choice < MIN || choice > MAX)
        {
            intro();
            printf("\n\n\tEnter your choice: ");
            scanf("%d", &choice);
        }

        switch(choice)
        {
        case 0:
            return 0;
        case 1:
            traverse(start);
            break;
        case 2:
            start = insertion(start);
            break;
        }
    }
    return 0;
}

Would be helpful if you also show how insert_begin is called and how start is used! — Atmaram Shetye
– Atmaram Shetye, Commented Jun 23, 2013 at 7:13
@zaphod These are complete programs that compile. You'll have to scroll a little. The call to insert_begin and insert_end is present in function insertion(). — Aseem Bansal
– Aseem Bansal, Commented Jun 23, 2013 at 7:14
@TaylorFlores How does this can have any effect on the traversal? Correct functions are being called even when I am using short instead of int. — Aseem Bansal
– Aseem Bansal, Commented Jun 23, 2013 at 7:28

Rohan · Accepted Answer · 2013-06-23 07:18:53Z

3

You are not returning anything from insertion() function when item is added to a list. So linked list may not get constructed properly.

Probably, you should return start only when its added at the beginning, otherwise start in main() will not point to head of the list.

sll_node* insertion(sll_node *start)
{
        ...
        switch(choice)
        {
        case 0:
            return start;
        case 1:
            start = insert_begin(start);
            return start;  //<----- return node
            break;
        case 2:
            start = insert_end(start);
            break;
        }
    ...

}

answered Jun 23, 2013 at 7:18

Rohan

53.5k12 gold badges95 silver badges89 bronze badges

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

6 Comments

Aseem Bansal Over a year ago

I'll have to return in the case when I insert at end. What about the case when the list is empty and the function is called for insertion at end? The end is beginning and hence I'll have to return some value. The function insert at end actually returns the start so there should be no problem if I return start.

Aseem Bansal Over a year ago

I tried both your suggestions before and after your edit. Program still crashes during traversal.

Rohan Over a year ago

@Zel, yes, you would handle case appropriately when first node is added at the end.

Aseem Bansal Over a year ago

@Rohan Didn't get your last comment. Can you rephrase that?

Rohan Over a year ago

@Zel, It will be helpful if you write steps (how did you insert nodes, choices that used) etc, when you get crash. Update that in question.

|

Aseem Bansal · Accepted Answer · 2013-06-23 08:10:28Z

2

Change short choice to int choice.

Why does this make a difference?

Short answer is that printf("%d") expects an integer.

The long answer is "%d" describes the data type you are passing to printf as an integer (which is commonly 4 to 8 bytes), and you're giving it a datatype of short - which is commonly 2 bytes long. When your program reads the input and stores it at the pointer, &choice, it writes 4 bytes starting at that address (but only 2 were reserved). This causes a segmentation fault and will crash your program.

Here's a list to some printf documentation. You'll notice that to pass a short to printf you would write %hd instead of %d

edited Jun 23, 2013 at 8:10

Aseem Bansal

7,02014 gold badges51 silver badges86 bronze badges

answered Jun 23, 2013 at 8:04

tay10r

4,3662 gold badges27 silver badges46 bronze badges

Comments

user2513066 · Accepted Answer · 2013-06-23 07:42:46Z

1

When i compile your code on my computer, it works, but i changed "short choice" to "int choice", because scanf("%d", &choice) takes 4 bytes to write on, and when choice is short it crashes, because short has only 2 bytes, therefore stack corruption will occur, my be on your computer this corruption damage the "start" pointer.

answered Jun 23, 2013 at 7:42

user2513066

3 Comments

tay10r Over a year ago

I beat you to this in a comment ;)

cup Over a year ago

Depends on compiler: some will take scanf("%hd", &shortvariable)

Aseem Bansal Over a year ago

Your suggestion works but @TaylorFlores told it first. Your explanatin helped. Thanks.

Boiko Angelov · Accepted Answer · 2013-06-23 07:47:22Z

0

About the crash. Change the argument start in both functions insert_begin and insert_end to sll_node ** start, and when assigning new value, use the expression *start = your-new-value. It is because you have to pass a pointer to the local variable start which is also pointer. You do not need to change function traverse.

About memory leaks, let me to point-out that when you call insert_begin from inside insert_end, the node created from insert_end is left unused. before exit() and the return in main() you should free the list.

answered Jun 23, 2013 at 7:47

Boiko Angelov

214 bronze badges

1 Comment

Aseem Bansal Over a year ago

I had actually tried that also. It doesn't work either. I found the solution. TaylorFlores gave it in a comment.

Boiko Angelov · Accepted Answer · 2013-06-23 10:20:12Z

Yes, sorry. There was another bug hard to see. It was at 2 lines where you read (choice).

    short choice;
    ...
    // It is ERROR to use "%d" with (short choice), because the stack will
    // be overwritten with unsuspected results. The format specifier "%hd"
    // say to compiler that (&choice) point to a short 16-bit integer,
    // not 32-bit
    scanf("%hd", &choice);

This is slightly different version, tested, without memory leaks.

//

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

    #define MIN 0
    #define MAX 2
    #define INS_MIN 0
    #define INS_MAX 2

    typedef struct node
    {
        int data;
        struct node *next;
    } sll_node;

    void clear_list(sll_node** start)
    {
        assert(start != NULL);
        sll_node* node = *start;
        while (node != NULL)
        {
            sll_node* element = node;
            node = element->next;
            free(element);
        }
        *start = NULL;
    }

    void intro()
    {
        system("cls");
        printf("\n\tThese are the various options:\n");
        printf("\n\t00 Exit");
        printf("\n\t01 Traverse the list");
        printf("\n\t02 Insertion into the list");
    }

    void insert_begin(sll_node** pstart)
    {
        sll_node* node = (sll_node*)malloc(sizeof(sll_node));
        if (node == NULL)
        {
            printf("\n\tNot enough menory");
            clear_list(pstart);
            exit(-1);
        }
        int data;
        printf("\n\tData to be entered: ");
        scanf_s("%d", &data);//scanf
        node->data = data;
        node->next = *pstart;
        // update the local variable start passed from main to point just inserted node
        *pstart = node;
    }

    void insert_end(sll_node** start)
    {
        assert(start != NULL);
        if (*start == NULL)
        {
            insert_begin(start);
        }
        else
        {
            sll_node* node = (sll_node*)malloc(sizeof(sll_node));
            if (node == NULL)
            {
                printf("\n\tNot enough menory");
                clear_list(start);
                exit(-2);
            }
            printf("\n\tData to be entered: ");
            scanf("%d", &(node->data));
            node->next = NULL;
            sll_node* node2;
            for(node2 = *start; node2->next != NULL; node2 = node2->next)
                ;
            node2->next = node;
        }
    }

    void insert_intro()
    {
        system("cls");
        printf("\n\tThese are the various options:\n");
        printf("\n\t00 Insertion Done");
        printf("\n\t01 Insert at beginning");
        printf("\n\t02 Insert at end");
    }

    void insertion(sll_node** start)
    {
        short choice;
        while(1)
        {
            choice = -1;
            while(choice < INS_MIN || choice > INS_MAX)
            {
                insert_intro();
                printf("\n\n\tEnter your chocie: ");
                scanf("%hd", &choice);
            }
            switch(choice)
            {
            case 0:
                return;
            case 1:
                insert_begin(start);
                break;
            case 2:
                insert_end(start);
                break;
            }
        }
    }

    void traverse(sll_node *start)
    {
        if (start == NULL)
            printf("\n\n\tLinked list is empty");
        else
        {
            printf("\n\n\t");
            for(sll_node *node = start; node != NULL; node = node->next)
                printf("%d ", node->data);
        }
        getch();
    }

    int main()
    {
        sll_node *start = NULL;
        short choice;
        while(1)
        {
            choice = -1;
            while(choice < MIN || choice > MAX)
            {
                intro();
                printf("\n\n\tEnter your choice: ");
                scanf("%hd", &choice);
            }
            switch(choice)
            {
            case 0:
                clear_list(&start);
                return 0;
            case 1:
                traverse(start);
                break;
            case 2:
                insertion(&start);
                break;
            }
        }
        return 0;
    }

P.S. Very hard to edit! I'm new here and do not have enough experience. Wasted a lot of time to edit!

Best way to edit code is to go to an IDE -> edit -> then replace the original code. Editing on SO is a hassle

Collectives™ on Stack Overflow

Passing pointers between functions in an implementation of linked list

5 Answers 5

6 Comments

Comments

3 Comments

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

6 Comments

Comments

3 Comments

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related