Implement a doubly linked list in C

Question

I want to insert a node at the beginning of linked list, whenever insertAtBeginning method is called. My code builds well, but i don't get the desired output.

I get the following output:

0------>NULL

The desired output is:

9------>8------>7------>6------>5------>4------>3------>2------>1------>0------>NULL

Following is my code:

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

struct dll{
    int data;
    struct dll* previous;
    struct dll* next;
};


struct dll* insertAtBeginning(int a, struct dll* head){

    if(head == NULL){
        head->data = a;
        head->previous = NULL;
        head->next = NULL;
        return head;
    }
    else{
        struct dll *first;
        first = (struct dll*) malloc( sizeof(struct dll));
        first->data = a;
        first->next = head;
        head->previous = first;
        first->previous = NULL;
        head = first;
        free(first);
        return head;
    }
}


void display_from_first(struct dll* head){
    struct dll *temp;
    temp = head;

    printf("\nThe linked list contains: ");
    while(temp != NULL) {
        printf("%d------>",temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
    free(temp);
    }


int main(){
    int i = 0;
    struct dll *head1, *tail1;
    head1 = (struct dll*) malloc( sizeof(struct dll));
    head1->next = NULL;
    head1->previous = NULL;

    for(i=0; i<10; i++){
        insertAtBeginning(i, head1);
    }

    display_from_first(head1);

    return 0;
}

Why on earth is your insert code doing head = first; free(first); — your code will crash. What output do you get? — Jonathan Leffler
– Jonathan Leffler, Commented Mar 14, 2015 at 4:16

user3386109 · Accepted Answer · 2015-03-14 04:53:43Z

The code for a doubly linked list is much cleaner if you start with an empty list of two nodes as shown below.

enter image description here

That way you don't have to deal with special cases like if(head==NULL). There's always a node before and after the node that is being inserted (or deleted), so you just hook things up and you're done.

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

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

Node *insertAtBeginning( Node *head, int value )
{
    // allocate memory for the new node
    Node *node = malloc( sizeof(Node) );
    if ( node == NULL )
        return NULL;

    // insert the node at the beginning of the list
    Node *temp = head->next;
    head->next = node;
    temp->prev = node;

    // fill in the fields of the node
    node->prev = head;
    node->next = temp;
    node->data = value;

    return node;
}

void showList( Node *head )
{
    Node *node;

    printf( "The list contains: " );
    for ( node = head->next; node->next != NULL; node = node->next )
        printf( "%d--->", node->data );
    printf( "NULL\n" );
}

int main( void )
{
    // create an empty list with two nodes
    Node head = { NULL , NULL, 0 };
    Node tail = { &head, NULL, 0 };
    head.next = &tail;

    // insert more nodes
    for ( int i = 0; i < 10; i++ )
        insertAtBeginning( &head, i );

    // display the list
    showList( &head );
}

Ayushi Jha · Accepted Answer · 2015-03-14 04:45:54Z

2

There are mainly two problems here :

free(first) : This is not required as you wish to save the memory you just allocated, not delete it.
Your insertAtBeginning() function returns a pointer to head, so in main(), where you are calling this function change it to head1=insertAtBeginning(i, head1); This way your head is also saved.

Here's the code with the two edits :

http://ideone.com/nXwc8z

answered Mar 14, 2015 at 4:45

Ayushi Jha

4,0233 gold badges28 silver badges44 bronze badges

6 Comments

Jainam Jhaveri Over a year ago

After updating the pointer and removing the free statement, I get the stackdump error!! It worked good till i freed first pointer.

Jainam Jhaveri Over a year ago

I ran the same code over codeBlocks... but got Stackdump error

Ayushi Jha Over a year ago

Let me check on codeblocks then, because it works well on ideone.

Jainam Jhaveri Over a year ago

Yeah, it worked...!! I had removed head1 = (struct dll*) malloc( sizeof(struct dll)); head1->next = NULL; head1->previous = NULL; statements before running it..

Ayushi Jha Over a year ago

Glad it helped! I was about to suggest one more thing : when displaying, you need to to change the condition while(temp!=NULL) to `(while(temp->next!=NULL), as it printed erroneous data at last output.

|

justanothercoder · Accepted Answer · 2015-03-14 04:19:49Z

2

You have several mistakes here.

1) Your function insertAtBeginning returns pointer to changed list, but you do not update pointer to head of list in the main function.

2) You are freeing just allocated pointer to new node in the insertion function. You think that you are freeing pointer, but actually you say that this place in memory is not needed more and so your node can't be there.

answered Mar 14, 2015 at 4:19

justanothercoder

1,9391 gold badge17 silver badges27 bronze badges

1 Comment

Jainam Jhaveri Over a year ago

After updating the pointer and removing the free statement, I get the stackdump error!! It worked good till i freed first pointer.

Karthikeyan.R.S · Accepted Answer · 2015-03-14 04:42:09Z

2

You can't free(first); in insertAtBeginning().

code here.

And btw when you have empty list your display_from_first() prints The linked list contains: 0------>NULL because of

head1 = (struct dll*) malloc( sizeof(struct dll));
head1->next = NULL;
head1->previous = NULL;

in main(). Remove it from main to have correct output

edited Mar 14, 2015 at 4:42

Karthikeyan.R.S

4,0512 gold badges21 silver badges31 bronze badges

answered Mar 14, 2015 at 4:17

stryku

7505 silver badges12 bronze badges

Collectives™ on Stack Overflow

Implement a doubly linked list in C

4 Answers 4

Comments

6 Comments

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

6 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related