Sorted Insertion in linked list with pointers, C program crashes

Question

I'm "translating" this program from a pseudo Pascal language. Recently I learned C structs and pointers features, and from the start I noticed that pointers are very annoying. So this is a recursive version of the Sorted Insertion in a Linked List algorithm, and it still gives me problems, like crashing.

typedef struct node Node;

struct node
{
  int info;
  struct node *link;
};

void ordered_insert_rec(Node *head, Node *new_node)
{
  if(!head)
  {
    new_node->link = head;
    head = new_node;
  }

  if(new_node->info < head->info)
  {
    new_node->link = head;
    head = new_node;
  }
  else
  {
    ordered_insert_rec(head->link, new_node);
  }

This is the main:

int main()
{
  Node head;
  Node node;
  Node node2;
  Node inserting_node;

  head.info = 1;
  head.link = &node;

  node.info = 3;
  node.link = &node2;

  node2.info = 7;

  inserting_node.info = 5;

  ordered_insert_rec(&head, &inserting_node);

  Node *front = &head;
  while(front)
  {
    printf("%d ", front->info);
    front = front->link;
    if(!front)
    {
      exit(1);
    }
  }
}

Maybe I'm doing something wrong with the list printing at the end of the algorithm, is it? In the prompt the output is "1 3 7" but the program crashes after a while. It must be "1 3 5 7", by this way I noticed up that the procedure "ordered_insert_rec" doesn't work correctly.

Thanks for the help. :)

an important problem is that you need to add node2.link=0; to your code too. you crash because you are accessing invalid address. — Afshin
– Afshin, Commented May 24, 2018 at 11:40
order_insert_rec logic should be if()...else if()....else. Just check what happens now! — Paul Ogilvie
– Paul Ogilvie, Commented May 24, 2018 at 11:42
node2.linkand inserting_node.link are not initialized: undefined behavior. — Paul Ogilvie
– Paul Ogilvie, Commented May 24, 2018 at 11:45

Afshin · Accepted Answer · 2018-05-24 12:12:18Z

1

Here is corrected code:

#include <stdio.h>

typedef struct node Node;

struct node
{
  int info;
  struct node *link;
};

void ordered_insert_rec(Node **head, Node *new_node)
{
  // You are inserting at head. So you need to update head pointer.
  // If you don't use double pointers, you only change it locally.
  if(!(*head))
  {
    new_node->link = *head;
    *head = new_node;
    return;
  }

  if(new_node->info < (*head)->info)
  {
    new_node->link = *head;
    *head = new_node;
  }
  else
  {
    ordered_insert_rec(&((*head)->link), new_node);
  }
}

int main()
{
  Node head;
  Node node;
  Node node2;
  Node inserting_node;

  head.info = 1;
  head.link = &node;

  node.info = 3;
  node.link = &node2;

  node2.info = 7;
  node2.link = 0;

  inserting_node.info = 5;
  inserting_node.link = 0;

  Node * start = &head;

  ordered_insert_rec(&start, &inserting_node);

  Node *front = &head;
  while(front)
  {
    printf("%d ", front->info);
    front = front->link;
  }

  return 0;
}

I didn't improve your code, just changed it for a working code as pointer tutorial. you can write this code better.

Problems:

Uninitialized links (head and insertion_node).
Your code updates head in function which is a pointer. So you need to use double pointers or you will just change it in function and results will not send back to main.
That break inside while loop for printing list is useless. Condition of while will not met on next iteration and it will stop.
You missed a return for when you are inserting in an empty list.
In general, people don't use stack variables as list members. Normally you need to allocate them. But in this specific case, you can use it.

edited May 24, 2018 at 12:12

answered May 24, 2018 at 11:50

Afshin

9,2401 gold badge28 silver badges59 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

RalphTheCreator Over a year ago

I put that break inside the while to check if the problem was the while condition. However thanks for the help, your answer saved my day! The double-pointer feature, that's news to me! :D

Afshin Over a year ago

@RalphTheCreator double pointer is for changing pointer from inside function. As I told, I changed your code. In real you don't need double pointer. As homework, try to write it without any double pointers. :D

RalphTheCreator Over a year ago

Ok, I'm going to write a non-recursive version of the algorithm, I will try there. Improvising an answer: I should create another pointer (as stack variable) that points to the address of the list element pointer (in my case *head). Next time I will make difference between stack variable and list elements. Thank you :D

Collectives™ on Stack Overflow

Sorted Insertion in linked list with pointers, C program crashes

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related