Creating an entire doubly linked list in one function

Viewed 57

I'm new to DSA and currently learning linked-list. I was trying to create an entire linked list in one function. The first scanf in createList function doesn't seem to assign the input to the address provided(i.e. &n). I tried printing n right after scanf. It doesn't print n to console at all. As a result, the output is not the way I expected. I can't figure out why.

//ENTIRE CODE HERE

#include<stdio.h>
#include<stdlib.h>
struct node {
    struct node* prev;
    int data;
    struct node* next;
};

void print_nodes(struct node* );
struct node* addToEmpty(struct node*, int);
struct node* addAtEnd(struct node*, int);
struct node* createList(struct node*);

int main() {
    struct node* head = NULL;
    head = createList(head);
    print_nodes(head);
}

void print_nodes(struct node* head) {
    struct node* ptr = head;
    while (ptr != NULL) {
        printf("%d ", ptr->data);
        ptr = ptr->next;
    }
    printf("\n");
}

struct node* addToEmpty(struct node* head, int data) {
    struct node* temp = malloc(sizeof(struct node));
    temp->prev = NULL;
    temp->data = data;
    temp->next = NULL;
    head = temp;
    return head;
}

struct node* addAtEnd(struct node* head, int data) {
    struct node* tp = head;
    struct node* temp = malloc(sizeof(struct node));
    temp->prev = NULL;
    temp->data = data;
    temp->next = NULL;
    while (tp->next != NULL) {
        tp = tp->next;
    }
    tp->next = temp;
    temp->prev = tp;
    return head;
}

struct node* createList(struct node* head) {
    int n, data, i;
    printf("Enter the number of nodes: ");
    scanf("%d ", &n);

    if (n == 0)
        return head;

    printf("Enter the element of node 1: ");
    scanf("%d ", &data);
    head = addToEmpty(head, data);

    for (i = 1; i < n; i++) {
        printf("Enter the element of node %d: ", i + 1);
        scanf("%d", &data);
        head = addAtEnd(head, data);
    }
    return head;
}
3 Answers

your problem is so simple , instead of scanf("%d ", &n); , just write scanf("%d", &n); by which I mean to remove the wite space after %d as it's producing some strange behavior in your case , as if you refer to scanf() manual page , they say that :

A sequence of white-space characters (space, tab, newline, etc.; see isspace(3)). This directive matches any amount of white space, including none, in the input.

which is supposed to ignore any whitespace after the number entered till getting a valid char.

and here is the full code but with this only small modification:

    #include<stdio.h>
#include<stdlib.h>
struct node {
    struct node* prev;
    int data;
    struct node* next;
};

void print_nodes(struct node* );
struct node* addToEmpty(struct node*, int);
struct node* addAtEnd(struct node*, int);
struct node* createList(struct node*);

int main() {
    struct node* head = NULL;
    head = createList(head);
    print_nodes(head);
}

void print_nodes(struct node* head) {
    struct node* ptr = head;
    while (ptr != NULL) {
        printf("%d ", ptr->data);
        ptr = ptr->next;
    }
    printf("\n");
}

struct node* addToEmpty(struct node* head, int data) {
    struct node* temp = malloc(sizeof(struct node));
    temp->prev = NULL;
    temp->data = data;
    temp->next = NULL;
    head = temp;
    return head;
}

struct node* addAtEnd(struct node* head, int data) {
    struct node* tp = head;
    struct node* temp = malloc(sizeof(struct node));
    temp->prev = NULL;
    temp->data = data;
    temp->next = NULL;
    while (tp->next != NULL) {
        tp = tp->next;
    }
    tp->next = temp;
    temp->prev = tp;
    return head;
}

struct node* createList(struct node* head) {
    int n, data, i;
    printf("Enter the number of nodes: ");
    scanf("%d", &n);

    if (n == 0)
        return head;

    printf("Enter the element of node 1: ");
    scanf("%d", &data);
    head = addToEmpty(head, data);

    for (i = 1; i < n; i++) {
        printf("Enter the element of node %d: ", i + 1);
        scanf("%d", &data);
        head = addAtEnd(head, data);
    }
    return head;
}

and this is the output:

 Enter the number of nodes:3
 Enter the element of node 1:1
 Enter the element of node 2:2
 Enter the element of node 3:3
 1 2 3

I tried out your code and found issues with the space in the literal string in the "scanf" statements. I see that someone else found that and offered up the solution to that with the cleanup of the "scanf" statements. I would say that if you are to accept an answer, select the first one. However, I just wanted to also offer up my code snippet with a couple of additional tweaks.

#include<stdio.h>
#include<stdlib.h>
struct node
{
    struct node* prev;
    int data;
    struct node* next;
};

void print_nodes(struct node* );
struct node* addToEmpty(struct node*, int);
void addAtEnd(struct node*, int);           /* No requirement for a node to be returned as the pointers are all set up in the function */
struct node* createList(struct node*);

int main()
{
    struct node* head = NULL;
    head = createList(head);
    print_nodes(head);
}

void print_nodes(struct node* head)
{
    struct node* ptr = head;
    while (ptr != NULL)
    {
        printf("%d ", ptr->data);
        ptr = ptr->next;
    }
    printf("\n");
}

struct node* addToEmpty(struct node* head, int data)
{
    struct node* temp = malloc(sizeof(struct node));
    temp->prev = NULL;
    temp->data = data;
    temp->next = NULL;
    //head = temp;
    return temp;        /* Return the pointer to the new struct - no need for update of head here */
}

void addAtEnd(struct node* head, int data)
{
    struct node* tp = head;
    struct node* temp = malloc(sizeof(struct node));
    temp->prev = NULL;
    temp->data = data;
    temp->next = NULL;
    while (tp->next != NULL)
    {
        tp = tp->next;
    }
    tp->next = temp;
    temp->prev = tp;
    return;
}

struct node* createList(struct node* head)
{
    int n, data, i;
    printf("Enter the number of nodes: ");
    scanf("%d", &n);

    if (n == 0)
        return head;

    printf("Enter the element of node 1: ");
    scanf("%d", &data);
    head = addToEmpty(head, data);

    for (i = 1; i < n; i++)
    {
        printf("Enter the element of node %d: ", i + 1);
        scanf("%d", &data);
        addAtEnd(head, data);
    }
    return head;
}

First off, since there is not a need to return a "struct" pointer in the function "addAtEnd", I revised that to be a "void" function return signature. Second, in the "addToEmpty" function, one can just return the pointer value in "temp" instead of placing the value into the input parameter "head"; however, it works either way. It is just a matter of choice.

As a sample, here is some output data at the terminal.

@Una:~/C_Programs/Console/CompleteList/bin/Release$ ./CompleteList 
Enter the number of nodes: 4
Enter the element of node 1: 65535
Enter the element of node 2: 2458
Enter the element of node 3: -44
Enter the element of node 4: 3258779
65535 2458 -44 3258779 

I would suggest trying out both iterations.

Other answers have pointed at the specific problem you experienced (bad scanf() parameter string).

Going beyond that, however, there are two other "issues(?)".

First is to "create an entire linked list in one function". In your code, main() calls only one function, but that function uses two "helper" functions to get the job done. Every line of code is an opportunity for a bug to lurk unseen. Re-using code is a way to reduce the chances for bugs to appear.

Secondly, the code appears to be correct, but does not prove that the doubly linked list is anything more than a singly linked list.

Both of these matters are addressed below creating (in one function, and later demonstrating) a circular doubly linked list. Comments explain changes from the original code to this version.

Finally, an additional function is used here to prevent memory leaks.

#include <stdio.h>

typedef struct node { // Using 'typedef' saves lots of typing (and reading
    int data;
    struct node *next;
    struct node *prev; // conventional layout of members
} node_t; // Notice '_t' as conventional suffix for user declared datatypes

node_t *print_nodes( node_t *head ) { // return pointer for use by caller
    if( head ) { // insurance against NULL pointer
        node_t *pn = head;

        printf( "Forward: " ); // exercise circular LL in both directions
        do {
            printf( "%d ", pn->data );
            pn = pn->next; // NB: 'next'
        } while( pn != head ); // circular, not linear! One full circuit
        puts( "" );

        printf( "Reverse: " );
        pn = pn->prev; // shift 'back' one node to begin
        do {
            printf( "%d ", pn->data );
            pn = pn->prev; // NB: 'prev'
        } while( pn != head->prev ); // circular, not linear! One full circuit
        puts( "" );
    }
    return head;
}

node_t *createList() { // Create "one ring to rule them all"
    int n = 0; // ALWAYS initialise variables
    do {
        printf( "Number of nodes (min 3): ");
        scanf( "%d", &n ); // 'while' protects against bad input
    } while( n < 3 );

    node_t *head = NULL;
    for( int i = 0; i < n; i++ ) {
        printf( "Enter the element of node %d: ", i + 1 );
        node_t *pn = (node_t *)calloc( 1, sizeof *pn ); // 'calloc()' zeros the block
        /* check 'pn == NULL' omitted for brevity */

        scanf("%d", &pn->data ); // read directly into destination (fewer variables)

        if( head == NULL )
            head = pn->prev = pn->next = pn; // 1st node, circular
        else {
            pn->prev = head->prev; // other nodes spliced-in ahead of 'head'
            pn->next = head;
            head->prev->next = pn;
            head->prev = pn;
        }
    }
    return head;
}

void freemem( node_t *head ) { // VERY important to respect "heap" storage!
    if( head == NULL ) return;

    node_t *pn = head; // traverse releasing nodes along the way
    do {
        node_t *pdel = pn;
        pn = pn->next;
        free( pdel );
    } while( pn != head );
}

int main() {
    // create, print, release, done...
    freemem( print_nodes( createList() ) );

    return 0;
}

Output

Number of nodes (min 3): 5
Enter the element of node 1: 42
Enter the element of node 2: 56
Enter the element of node 3: 10
Enter the element of node 4: -5
Enter the element of node 5: 256
Forward: 42 56 10 -5 256
Reverse: 256 -5 10 56 42

This code implements and proves a circular doubly linked list. The example can be trivially adapted to a linear dbl-LL by severing the connection between head and head->prev after the ring has been formed, and then making necessary adjustments at other locations to account for the change.

Related