Thread: How to create double linked list

  1. #1
    Registered User
    Join Date
    Feb 2022
    Posts
    73

    How to create double linked list

    I am trying to write code for double linked list. My code create single linked list where ecah new node points to previous node. I found, in double linked list each node contains two pointers

    Code:
    #include<stdio.h>
    
    #include<stdlib.h>
    
    
    //declare a Node structure
    struct node 
    {
        int data;
        struct node * next;    
        struct node * prev;    
    };
    
    
    struct node *Add_New_Node (struct node *head, int value)
    {
        struct node * new = malloc(sizeof(*new));
        
        if ( new != NULL)
        {
            new -> data = value;
            new -> prev = head;
        }
        
        return new;
        
    }
    
    
    void display (struct node *head)
    {
        struct node * current = NULL;
        
        for (current = head; current != NULL; current = current-> prev) 
        {
            printf("%d\n", current-> data);
        }
        
    }
    int main ()
    {
        struct node * head = NULL;
        
        head = Add_New_Node ( head, 10);
        head = Add_New_Node ( head, 20);
        head = Add_New_Node ( head, 30);
        head = Add_New_Node ( head, 40);
        head = Add_New_Node ( head, 50);
        
        display (head);
        
        return 0;
        
    }
    50
    40
    30
    20
    10

  2. #2
    Registered User
    Join Date
    Feb 2022
    Location
    Canada, PEI
    Posts
    64
    I'm confused here:
    Code:
    struct node *Add_New_Node(struct node *head, int value)
    {
        struct node *new = malloc(sizeof(*new));
    
        if (new != NULL)
        {
            snip
        }
    
        return new;
    }
    Why are you passing struct node *head here?

    Maybe you should consider having a function that creates an empty node.
    Last edited by G4143; 02-25-2022 at 09:46 PM.

  3. #3
    Registered User
    Join Date
    Feb 2022
    Location
    Canada, PEI
    Posts
    64
    If I had to do this I'd start with something like below and go from that:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    // declare a Node structure
    struct node
    {
        int data;
        struct node *next;
        struct node *prev;
    };
    
    struct node *createHeadNode(int data)
    {
        struct node *n = malloc(sizeof(*n));
        if (!n)
        {
            fputs("Allocation failed!", stderr);
            exit(EXIT_FAILURE);
        }
        n->data = data;
        n->next = NULL;
        n->prev = NULL;
        return n;
    }
    
    struct node *add(struct node *n, int data)
    {
        struct node *new_node = NULL;
        if (n)
        {
            new_node = malloc(sizeof(*new_node));
            if (!new_node)
            {
                fputs("Allocation failed!", stderr);
                exit(EXIT_FAILURE);
            }
            new_node->data = data;
            new_node->next = n;
            new_node->prev = NULL;
            n->prev = new_node;
        }
        return new_node;
    }
    
    void display(struct node *n)
    {
        if (n)
        {
            struct node *it = n;
            while (it)
            {
                fprintf(stdout, "%d\n", it->data);
                it = it->next;
            }
        }
    }
    
    int main()
    {
        struct node *h = createHeadNode(4143);
        display(h);
        h = add(h, 8888);
        h = add(h, 7777);
        h = add(h, 333);
        display(h);
        return 0;
    }
    Note this still needs a lot of thought...
    Last edited by G4143; 02-25-2022 at 10:56 PM.

  4. #4
    Registered User
    Join Date
    Feb 2022
    Posts
    73
    Quote Originally Posted by G4143 View Post
    I'm confused here:

    Why are you passing struct node *head here?
    new node points to previous node

    Quote Originally Posted by G4143 View Post
    If I had to do this I'd start with something like below and go from that:

    Code:
    struct node *add(struct node *n, int data)
    {
        struct node *new_node = NULL;
        if (n)
        {
            new_node = malloc(sizeof(*new_node));
            if (!new_node)
            {
                fputs("Allocation failed!", stderr);
                exit(EXIT_FAILURE);
            }
            new_node->data = data;
            new_node->next = n;
            new_node->prev = NULL;
            n->prev = new_node;
        }
        return new_node;
    }
    Note this still needs a lot of thought...
    What happens in double linked list. Does new node point to the next and previous node in linked list ?

  5. #5
    Registered User
    Join Date
    Feb 2022
    Location
    Canada, PEI
    Posts
    64
    Quote Originally Posted by Dadu@ View Post

    What happens in double linked list. Does new node point to the next and previous node in linked list ?
    Basically a double linked list has a head node which points to the next node and has a previous node of NULL and a end node which has a next node of NULL and a previous node which points to the previous node and intermediate node(s) which have both their next and previous nodes pointing to next and previous nodes.. Clear as mud right?
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    // declare a Node structure
    struct node
    {
        int data;
        struct node *next;
        struct node *prev;
    };
    
    struct node *createHeadNode(int data)
    {
        struct node *n = malloc(sizeof(*n));
        if (!n)
        {
            fputs("Allocation failed!", stderr);
            exit(EXIT_FAILURE);
        }
        n->data = data;
        n->next = NULL;
        n->prev = NULL;
        return n;
    }
    
    struct node *add(struct node *n, int data)
    {
        struct node *new_node = NULL;
        if (n)
        {
            new_node = malloc(sizeof(*new_node));
            if (!new_node)
            {
                fputs("Allocation failed!", stderr);
                exit(EXIT_FAILURE);
            }
            new_node->data = data;
            new_node->next = n;
            new_node->prev = NULL;
            n->prev = new_node;
        }
        return new_node;
    }
    
    void display(struct node *n)
    {
        if (n)
        {
            struct node *up;
            struct node *dw = n;
            fputs("Help! I just fell into a double linked list....\n", stdout);
            while (dw)
            {
                up = dw;
                fprintf(stdout, "Going down...%d\n", dw->data);
                dw = dw->next;
            }
            fputs("Yikes! Here comes the bottom! Bounce...\n", stdout);
            while (up) 
            {
                fprintf(stdout, "Going up...%d\n", up->data);
                up = up->prev;
            }
            fputs("Yah! I found my way out of this double linked list!\n", stdout);
        }
    }
    
    int main()
    {
        struct node *h = createHeadNode(1);
        h = add(h, 2);
        h = add(h, 3);
        h = add(h, 4);
        h = add(h, 5);
        h = add(h, 6);
        h = add(h, 7);
        h = add(h, 8);
        h = add(h, 9);
        h = add(h, 10);
        display(h);
        return 0;
    }
    See if you can follow this humorous version.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 06-12-2014, 07:36 AM
  2. Dynamic List Char Array & Double Linked List
    By Roadrunner2015 in forum C Programming
    Replies: 18
    Last Post: 10-20-2013, 01:31 PM
  3. double linked list
    By TNA$H in forum C Programming
    Replies: 19
    Last Post: 06-13-2008, 07:45 AM
  4. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 08:04 PM
  5. linked list noob - function create new list
    By dukysta in forum C Programming
    Replies: 5
    Last Post: 07-06-2007, 08:16 AM

Tags for this Thread