Doubly Linked list Insertion

Question

I made a program to insert a element in doubly linked list given below(ignore create and display functions Which was working perfectly right till it found the index to be inserted is 5 ,where it fails .Although i made another program to encounter this and now it isn't displaying anything. I used chat gpt but just got wrong answers .Pls help me and also any guidance for when i think a program and its algo it works perfectly but when i actually compile it .It doesn't work, even if i have traced my program like 10 times Another program:

     #include<stdio.h>
#include<stdlib.h>
typedef struct Node {
  struct Node *prev;
  int data;
  struct Node *next;
}new;
new *insert (new *head,int index,int num);
void display(new *head);
void create(new *head,int A[],int n);
void create(new *head,int A[],int n)
{
  head->data=A[0];
  head->next=head->prev=NULL;
  new *last=head;
  for(int i=1;i<n;i++)
  {
      new *t=(new *)malloc(sizeof(new));
      t->data=A[i];
      t->prev=last;
      t->next=NULL;
      last->next=t;
      last=t;
  }
}
void display(new *head)
{
  new * temp=NULL;
  int flag=0;
  printf("Next:");
  while(head)
  {
      printf("%d ",head->data);
      if(!head->next||flag==0){
          temp=head;
          flag=1;
      }
      head=head->next;
  }
  printf("\nPREV:");
  while(temp)
  {
      printf("%d ",temp->data);
      temp=temp->prev;
  }
  printf("\n");
}
new *insert (new *head,int index,int num)
{
  new*q=NULL,*temp=NULL;
  int flag=0;
  if(index==0)
  {
      return insert(head,0,9);
  }
  int i=0;
  while(i!=index)
  {
      if(!q->next&&flag==1)temp=q; 
      flag=1;
      q=head;
      head=head->next;
      i++;
  }
  new*t=(new*)malloc(sizeof(new));
  t->next=head;
  int y=0;
  t->data=num;
  if(!(head&&q))
  {
      temp->next=t;
      t->prev=temp;
      y=1;
  }
  if(y==0)
  {
  q->next=t;
  t->prev=q;
  head->prev=t;
  }
}
int main()
{
  new * head=(new *)malloc(sizeof(new));
  int A[5]={1,2,3,6,7};
  create(head,A,5);
  display(head);
  int i=3;
  insert(head,i,87);
  display(head);
}
  ```

If you want help to debug your program, please provide a minimal reproducible example (one, not two) so that we can actually compile your code. — Ted Lyngmo
– Ted Lyngmo, Commented Jan 13, 2024 at 11:30
Sir, example as ,in a set of numbers with a index to be inserted ?if yes then i may add the create function and the display function as well ,and the array of numbers being the one in the code — Harshal Malani
– Harshal Malani, Commented Jan 13, 2024 at 11:34
Yes, please add the missing functions and the expected output. Please also remove one of the snippets and concentrate on finding the bug in one of them. — Ted Lyngmo
– Ted Lyngmo, Commented Jan 13, 2024 at 11:34
Sir ,I have edited my answer and now it contains my full program, but please ignore the insert0() function it has no use — Harshal Malani
– Harshal Malani, Commented Jan 13, 2024 at 11:43

Vlad from Moscow · Accepted Answer · 2024-01-14 11:34:42Z

For starters the typedef name new is not good. It will be much better for example to use typedef name Node

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

you should decide what to do if the specified index is greater than the current number of nodes in the list: whether to append a new node or to report an error.

As for your code then it can not run fine.

For example if the specified index is equal to 0 then this code snippet

if(index==0)
{
    return insert(head,0,9);
}

invokes an infinite recursive call of the function itself. Also it is unclear why the third argument is the integer constant 9.

Also the function returns nothing if the specified index is not equal to 0.

And this statement in main

new * head=(new *)malloc(sizeof(new));

does not make sense. For example if the user will not call the function create then calls of the function insert will invoke undefined behavior.

Initially a list should be empty. That is in main you should write

new *head = NULL;

I would declare and define the function insert the following way.

int insert( Node **head, size_t index, int data )
{
    int success = 0;

    if (index == 0)
    {
        Node *node = ( Node * )malloc( sizeof( *node ) );
        success = node != NULL;

        if (success)
        {
            node->data = data;
            node->prev = NULL;
            node->next = *head;

            if (*head != NULL) ( *head )->prev = node;

            *head = node;
        }
    }
    else
    {
        Node *current = *head;

        while ( current != NULL && --index != 0 )
        {
            current = current->next;
        }

        success = index == 0;

        if (success)
        {
            Node *node = ( Node * )malloc( sizeof( *node ) );
            success = node != NULL;

            if (success)
            {
                node->data = data;
                node->prev = current;
                node->next = current->next;
                current->next = node;

                if (node->next != NULL) node->next->prev = node;
            }
        }
    }

    return success;
}

The function returns 1 if a node in the given position was inserted in the list or 0 if the specified index is out of the acceptable range [0, number of existent nodes] or a memory for a new node was not allocated.

Instead of the return type int you could introduce an enumeration that will classify possible errors or success.

Here is a demonstration program.

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

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

int insert( Node **head, size_t index, int data )
{
    int success = 0;

    if (index == 0)
    {
        Node *node = ( Node * )malloc( sizeof( *node ) );
        success = node != NULL;

        if (success)
        {
            node->data = data;
            node->prev = NULL;
            node->next = *head;

            if (*head != NULL) ( *head )->prev = node;

            *head = node;
        }
    }
    else
    {
        Node *current = *head;

        while ( current != NULL && --index != 0 )
        {
            current = current->next;
        }

        success = index == 0;

        if (success)
        {
            Node *node = ( Node * )malloc( sizeof( *node ) );
            success = node != NULL;

            if (success)
            {
                node->data = data;
                node->prev = current;
                node->next = current->next;
                current->next = node;

                if (node->next != NULL) node->next->prev = node;
            }
        }
    }

    return success;
}

FILE *display( const Node *head, FILE *fp )
{
    for (; head != NULL; head = head->next)
    {
        fprintf( fp, "%d -> ", head->data );
    }

    fputs( "null", fp );

    return fp;
}

void clear( Node **head )
{
    while (*head)
    {
        Node *tmp = *head;
        *head = ( *head )->next;
        free( tmp );
    }
}

int main( void )
{
    Node *head = NULL;

    int a[] = { 1, 2, 3, 6, 7 };
    const size_t N = sizeof( a ) / sizeof( *a );

    int success = 1;
    for (size_t i = 0; success && i < N; i++)
    {
        success = insert( &head, i, a[i] );
    }

    fputc( '\n', display( head, stdout ) );

    clear( &head );

    fputc( '\n', display( head, stdout ) );
}

The program output is

1 -> 2 -> 3 -> 6 -> 7 -> null
null

Try to write the function create yourself. It should be declared like

size_t create( Node **head, const int a[], size_t n );

The function returns the actual number of added elements of an array to the list.

Pay attention to that it would be reasonsable to introduce one more structure like for example

struct DoubleLinkedList
{
    struct Node *head;
    struct Node *tail;
    size_t size;
};

And define functions that will deal with an object of this structure type.

@Harshal Malani I am sorry. The initial provided by me function insert was incorrect. I have updated it now.

Collectives™ on Stack Overflow

Doubly Linked list Insertion

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related