linked list - add in order - Need Help

[brandon93s]

I am writing a program in C to build linked lists from scratch. However, I am getting hung-up on trying to build a link list that will automatically sort itself. By this, I mean that the nodes will automatically be placed in the correct location. My current code is putting only the first value into the list (and then exiting successfully), it isn't executing properly when trying to determine if it is greater than or less than its surrounding nodes. Please see my code below.

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

typedef struct IntNode {
    int data;
    struct IntNode *next;
} IntNode;


typedef struct List {
    IntNode *head;
} List;


IntNode *New_Node(int n);
void Print_List(List *theList);
void Free_List(List *theList);
void Add_in_Order(List *list, List *newnode);

int main()
{
int i=0;
List myList = {NULL};

for(i=1; i<=10; i++) {
    IntNode *n=New_Node(rand()%20);
    Add_in_Order(&myList, n);
}

Print_List(&myList);
Free_List(&myList); 
    return 0;
}

IntNode *New_Node(int n){
    IntNode *temp;
    temp = malloc(sizeof(IntNode));
    temp->data = n;
    return temp;
}

void Add_in_Order(List *list, List *newnode)
{
    IntNode *x, *temp;
    if(!list->head)
    {
     list->head = newnode;
     return;
    }
     IntNode *hd;
     hd = list->head;
     IntNode *hd2;
     hd2 = newnode->head;
     for (hd = list->head; hd->next; hd = hd->next)
     {
         if((hd2->data) < (hd->data) && (hd2->data) >= (hd->next->data))
         {
           temp = hd->next;
           hd->next = newnode;
           newnode->head->next = temp;
           return;
         }
    }
     hd->next = newnode;
     list->head->next = NULL;
}

I have not included Free_List or Print_List as they are working just fine. As you can see I am trying to place 10 random numbers into nodes into the list, sorted. But on print it is only printing the first generated number (13) which i have confirmed is (13) by simply printing it. Basically, there is something wrong with my for loop in Add_in_Order and I'm not sure what. Thank you!

[hwoarang69]

you dont need two struct for sorted linked list. Also try not to use for loop when working with linked list. Point of linked list is that you dont know how many value there are. so while loop make more scene.

I didnt test my code for bugs for the Idea is more important here. Also you can use the same idea for your free function.

you only need one struct which all you data. Also a pointer which will point at 1st node of your linked list.

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

struct node
{
  int age;
  struct node *next;
};
struct node *head;

/* Prototypes for the functions */

void insert(int);
void print_list();

In my main user will 1st enter one of 3 commands:
1- end = ends the program
2- ins = insert a number in sorted linked list
3- print= print the linked list

you can change main to do what you want but the main idea is same.

    int main(void)
    {
      int age = 0;
      char cmd[4];


      printf("Command? "); fflush(stdout);      
      scanf("%s",cmd);                         //user choose a command 

      while(strcmp(cmd,"end") != 0)             //stop program if user enter "end"
        {
          if(strcmp(cmd, "ins") == 0)           //if user enter ins than call insert fuction
        {
          scanf("%d", &age);                    //get a number from user
          insert(age);                           //put the number in insert function
        }
          if(strcmp(cmd, "print") == 0)        //if user enter print  than 
        {
          print_list();                         //call print function
        }

          printf("Command: "); fflush(stdout);
          scanf("%s",cmd);                          //get next number and do the whole thing again
        }

      return 0;
    }






    void insert(int ag)
    {
      struct node *cur_node = head;
      struct node *new_node;
      int in_list = 0;

        //if linked list is empty creat 1st node
      if(cur_node == NULL)
        {
          head = (struct node *) malloc(sizeof(struct node));  //create memory for head pointer
          if(head == NULL)
        {
          printf("Node allocation failed.\n"); fflush(stdout);
          exit(1);
        }
          head->age = ag;               
          head->next = NULL;
        }
      else
        {
          /* insert at begining */
          if(head->age > ag)
        {
          new_node = (struct node *) malloc(sizeof(struct node));
          if(new_node == NULL)
            {
              printf("Node allocation failed.\n"); fflush(stdout);
            }
          new_node->age = ag;
          new_node->next = head;
          head = new_node;
          in_list = 1;
        }



         /* insert number in middle of linked list*/
         cur_node = head;
          while(cur_node != NULL && cur_node->next != NULL)
        {
          if(cur_node->age < ag && cur_node->next->age > ag)
            {
              new_node = (struct node *) malloc(sizeof(struct node));
              if(new_node == NULL)
            {
              printf("Node allocation failed.\n"); fflush(stdout);
            }
              new_node->age = ag;
              new_node->next = cur_node->next;
              cur_node->next = new_node;
              in_list = 1;
            }
          cur_node = cur_node->next;
        }


          /* insert number at end of a linked list */
          if(in_list == 0)
        {
          cur_node = head;

          while(cur_node->next != NULL)
            {
              cur_node = cur_node->next;
            }
          new_node = (struct node *) malloc(sizeof(struct node));
          if(new_node == NULL)
            {
              printf("Node allocation failed.\n"); fflush(stdout);
              exit(1);
            }
          new_node->age = ag;
          new_node->next = NULL;
          cur_node->next = new_node;
        }
        }//end of main else
    }//end of indert method

//just print linked list but using the same idea from insert function
void print()
{
//...
}

hope it helps. and good luck

[brandon93s]

Unfortunately, this didn't work.

[hwoarang69]

i just tested this in unix and it seem to be working fine.

when you run it whats it out put or errors?

[histrungalot]

Let's add more debug. Not making it into the for loop.

Code

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

typedef struct IntNode {
    int data;
    struct IntNode *next;
} IntNode;


typedef struct List {
    IntNode *head;
} List;


IntNode *New_Node(int n);
void Print_List(List *theList);
void Free_List(List *theList);
void Add_in_Order(List *list, IntNode *newnode);

IntNode *New_Node(int n){
    IntNode *temp;
    temp = malloc(sizeof(IntNode));
    temp->data = n;
    return temp;
}
int main()
{
int i=0;
List myList = {NULL};

for(i=1; i<=10; i++) {
    IntNode *n=New_Node(rand()%20);
    Add_in_Order(&myList, n);
}
}

void Add_in_Order(List *list, IntNode *newnode)
{
    printf("Trying to Add: %d\n",newnode->data);
    IntNode *x, *temp;
    if(!list->head)
    {
     printf("Setting head\n");
     list->head = newnode;
     return;
    }
     IntNode *hd;
     hd = list->head;
     IntNode *hd2;
     hd2 = newnode;
     printf("Before for loop: list->head(%p) hd->next(%p)\n",list->head,list->head->next);
     for (hd = list->head; hd->next; hd = hd->next)
     {
         printf("Testing: %d < %d && %d >= %d\n",hd2->data,hd->data,hd2->data,hd->next->data);
         if((hd2->data) < (hd->data) && (hd2->data) >= (hd->next->data))
         {
           printf("Adding node\n");
           temp = hd->next;
           hd->next = newnode;
           newnode->next = temp;
           return;
         }
    }
    printf("Setting hd->next = %p\n",newnode);
     hd->next = newnode;
    printf("Setting list->head->next = NULL\n");
     list->head->next = NULL;
}

Output

$ ./a.out
Trying to Add: 7
Setting head
Trying to Add: 9
Before for loop: list->head(0x100100080) hd->next(0x0)
Setting hd->next = 0x100100090
Setting list->head->next = NULL
Trying to Add: 13
Before for loop: list->head(0x100100080) hd->next(0x0)
Setting hd->next = 0x1001000a0
Setting list->head->next = NULL
Trying to Add: 18
Before for loop: list->head(0x100100080) hd->next(0x0)
Setting hd->next = 0x1001000b0
Setting list->head->next = NULL
Trying to Add: 10
Before for loop: list->head(0x100100080) hd->next(0x0)
Setting hd->next = 0x1001000c0
Setting list->head->next = NULL
Trying to Add: 12
Before for loop: list->head(0x100100080) hd->next(0x0)
Setting hd->next = 0x1001000d0
Setting list->head->next = NULL
Trying to Add: 4
Before for loop: list->head(0x100100080) hd->next(0x0)
Setting hd->next = 0x1001000e0
Setting list->head->next = NULL
Trying to Add: 18
Before for loop: list->head(0x100100080) hd->next(0x0)
Setting hd->next = 0x1001000f0
Setting list->head->next = NULL
Trying to Add: 3
Before for loop: list->head(0x100100080) hd->next(0x0)
Setting hd->next = 0x100100100
Setting list->head->next = NULL
Trying to Add: 9
Before for loop: list->head(0x100100080) hd->next(0x0)
Setting hd->next = 0x100100110
Setting list->head->next = NULL
$