Thread: 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

Originally Posted by G4143

I'm confused here:

Why are you passing struct node *head here?

new node points to previous node

Originally Posted by G4143

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 ?

Originally Posted by Dadu@

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.