Click here to Skip to main content
15,881,898 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
I was given an simple assignment that deals with doubly linked lists, dynamic data allocation, and recursion. I created an array of just 10 integers and I am trying to put these integers into a sorted doubly linked list using recursion. I am having some trouble with inserting nodes into the linked list; my output is "2 7 9 100" and is missing the other 6 integers for some reason. What am I doing wrong? Thank you for any help! (The language used is C)


C++
#include <stdio.h>

#include <stdlib.h>

#define N 10

typedef struct node_ {
  int value;
  struct node_ *next;
  struct node_ *prev;
} node;

void insert(node **head, node *cur, node *p);
void print_list(node *cur);


void print_list(node *cur)
{
  if (!cur) {
    printf("\n");
    return;
  } else {
    printf("%d ", cur->value);
    print_list(cur->next);
  }
}

int main(int argc, char *argv[])
{
  int i;
  int data[N] = {2, 7, 3, 9, 4, 4, 0, 8, 7, 100};
  node *p, *head;
  head = NULL;
  for (i = 0; i < N; i++) {
    p = (node *)malloc(sizeof(node));
    p->value = data[i];
    insert(&head, head, p);
  }

  print_list(head);
}

void insert(node **head, node *cur, node *p)
{
  if(*head == NULL) 
  {
     p->next = p->prev = NULL;
    *head = p;
    return; 
  }
  if(p->value < cur->value)
  {
    p->prev = cur->prev;
    p->next = cur;
    cur->prev = p;
    if(cur->prev != NULL) 
      cur->prev->next = p;
    else
      *head = p; 
    return; 
  }
  if(cur->next == NULL) 
  {
    cur->next = p;
    p->next = NULL;
    p->prev = cur;
  }
  else 
    insert(head, cur->next, p);
}
Posted
Updated 22-Nov-15 9:13am
v3

Obviously, your own code is like a blackbox to you. It don't do what you expect.
What follow is not directly a solution to your problem, but a key that will help you to understand by yourself what is wrong.
The debugger is your friend. It will show you what your code is really doing.
Follow the execution, inspect variables and you will see that there is a point where it stop doing what you expect.
Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]
Details may change depending on your compiler, the idea stay the same.
 
Share this answer
 
cur->prev = p;
if(cur->prev != NULL)

it is strongly recommended to use human readable names - so you can see 'cur' is 'p' now.
if(p->prev != NULL)
  p->prev->next = p;

regards.
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900