CODEWITHSUNDEEP
csortingdata-structuresdoubly-linked-listinsertion
Pomegranate Society
Pomegranate Society

Reputation: 127

Insert a node into a doubly linked list in a sorted manner?

I am working on a problem in which I have a method that is supposed to insert a node into a doubly linked list in a sorted manner. Here is my node and list structure:

typedef struct NodeStruct Node;

//struct for each office item
struct NodeStruct {
    int id;
    struct NodeStruct *next;
    struct NodeStruct *prev; //Create doubly linked list node
};


/** Structure for the whole list, including head and tail pointers. */
typedef struct {
  /** Pointer to the first node on the list (or NULL ). */
  Node *head;
  Node *last;
} List;

When I attempt to print the list of items, the item what I am trying to insert does not appear. For instance, if I try to insert 15 into this list

1 -> 2 -> 3 -> 5 -> 7,

15 does not appear at the end. Here is my insert method: 

void insert(int idInsert, List *list)
{
  //Initialize data for node
  int idInsert;

  //Insert the record based on the ID if no duplicates exist
  //Special case: insert at front if idInsert is less than the ID of the current head
  if (idInsert < list->head->id) {
    //Make the node with idInsert the first node
    Node *new = (Node *)malloc(sizeof(Node)); //Allocate memory for the new node

    //Add in data
    new->id = idInsert;

    new->next = list->head;

    list->head = new;
  } else { //Locate the node before the point of insertion
    //Allocate memory for the node
    Node *new = (Node *)malloc(sizeof(Node));

    //Add in data
    new->id = idInsert;

    Node *current = list->head;
    while (current->next != NULL && current->next->id < new->id) {
      current = current->next;
    }
    new->next = current->next;
    if (current->next != NULL) {
      new->next->prev = new;
    }
    current->prev->next = new;
    new->prev = current;
  }

  //Print this message if successful
  printf("RECORD INSERTED: %d\n", idInsert);
  }

I am also going to include some minimal reproducible code below:

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


typedef struct NodeStruct Node;

//struct for each office item
struct NodeStruct {
    int id;
    struct NodeStruct *next;
    struct NodeStruct *prev; //Create doubly linked list node
};


/** Structure for the whole list, including head and tail pointers. */
typedef struct {
  /** Pointer to the first node on the list (or NULL ). */
  Node *head;
  Node *last;
} List;

List *list;

List *makeList();
void insert(int idInsert, List *list);
static void *addRecord(List *list, int newID);
static void printReverse(List *list);

int main(int argc, char **argv) {

  //Create an empty list for you to start.
  list = (List *)makeList();

  addRecord(list, 1);
  addRecord(list, 2);
  addRecord(list, 3);
  addRecord(list, 4);
  addRecord(list, 7);
  insert(15, list);
  printReverse(list);

}

List *makeList()
{
  List *list = (List *) malloc( sizeof( List ) );
  list->head = NULL;
  list->last = NULL;
  return list;
}

void insert(int idInsert, List *list)
{
  //Insert the record based on the ID if no duplicates exist
  //Special case: insert at front if idInsert is less than the ID of the current head
  if (idInsert < list->head->id) {
    //Make the node with idInsert the first node
    Node *new = (Node *)malloc(sizeof(Node)); //Allocate memory for the new node

    //Add in data
    new->id = idInsert;

    new->next = list->head;

    list->head = new;
  } else { //Locate the node before the point of insertion
    //Allocate memory for the node
    Node *new = (Node *)malloc(sizeof(Node));

    //Add in data
    new->id = idInsert;

    Node *current = list->head;
    while (current->next != NULL && current->next->id < new->id) {
      current = current->next;
    }
    new->next = current->next;
    if (current->next != NULL) {
      new->next->prev = new;
    }
    current->prev->next = new;
    new->prev = current;
  }

  //Print this message if successful
  printf("RECORD INSERTED: %d\n", idInsert);
}

static void *addRecord(List *list, int newID) {
    //Allocate memory for the node
    Node *new = (Node *)malloc(sizeof(Node)); 

    //Add in data
    new->id = newID; 
    new->prev = NULL;

    //New node has no next, yet
    new->next = NULL;

    Node **next_p = &list->head;
    while (*next_p) {
        next_p = &(*next_p)->next;
    }
    *next_p = new;
    list->last = new;
    new->prev = *next_p;

    return EXIT_SUCCESS;
}

static void printReverse(List *list) {
    Node **tail = &list->last;
    printf("LIST IN REVERSE ORDER:\n");

    //Traversing until tail end of linked list
    while (*tail) {
        printf("Item ID: %d\n", (*tail)->id);
        tail = &(*tail)->prev;
    }
}

It seems like my addRecord method is working fine (this functions to add values to the end of the linked list), but my insert method is not working properly. When I execute the minimal reproducible code above, I am stuck in an infinite loop. My desired result after calling printReverse would be:

Item ID: 15
Item ID: 7
Item ID: 4
Item ID: 3
Item ID: 2
Item ID: 1

Could someone please point out what is going wrong in my insertion method?

Upvotes: 1

Views: 742

Answers (1)

gsamaras
gsamaras

Reputation: 73366

Insert has three cases:

  1. Insert at the start.
  2. Insert at the middle.
  3. Insert at the end.

Your weapon to sketch out your algorithm is a piece of a paper and a pencil, where you will draw what your code is doing.

Insert at the start

Your case for inserting at the start is not complete, since you need to set the new node's previous pointer to NULL, and the previous pointer of the node that was the old head should now be pointing to the newly created node.

That could be done like this:

Node *new = malloc(sizeof(Node)); //Allocate memory for the new node

list->head->prev = new;
new->prev = NULL;
// rest of your code

Insert at the end

Anyway, to answer your question, in your example, you could simply use the addRecord() method that appends a node in the list, when the node to be inserted goes to the end, like in your example, the node with id 15.

You can do it like this:

Node *current = list->head;
while (current->next != NULL && current->next->id < new->id) {
  current = current->next;
}
// if the new node is the last one
if(current->next == NULL)
{
  // append it to the list
  addRecord(list, idInsert);
  printf("RECORD INSERTED: %d\n", idInsert);
  return;
}

assuming you are using the method addRecord() discussed in your previous question, and not the one you provide here.

But as @SomeProgrammerDude commented, you could simplify that by checking if the new node is greater than the last node, and if yes, you call the addRecord().

Insert at the middle

In the case of having only node with id 1 in the list, and you insert the node with id 15 at the end, this invokes Undefined Behavior:

current->prev->next = new;

since the current node (with id 1) has no previous node, thus it's set to NULL. So you are requesting for the next field in something not a structure or a union.. Same for having 1 and 15 already in the list, and trying to insert 5.

Try changing that to:

current->next = new;

However, with your code, you will request the id of list->head, even if the list is empty, meaning that head (and last) pointer is NULL. That will invoke Undefined Behavior (UB), which is likely to result in a segmentation fault.

For that reason, in the following code I will first check if the list is empty or if the new node shall be inserted at the end, since in both cases it is enough to just call the addRecord() method (which appends a node to the list).

The condition of the if statement is going to be this:

if (list->last == NULL || idInsert > list->last->id)

which, due to short circuiting is going to be evaluated in the following order:

If the last pointer is NULL, then for sure the condition will be evaluated to true since the operator is the logical OR, so a single true operand will suffice to determine what the overall outcome of the condition is going to be. That means, that it won't evaluate the second operand, so the last pointer will not be dereferenced (which would invoke UB, since we would be requesting the id of NULL).

Putting everything together:

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

typedef struct NodeStruct Node;

//struct for each office item
struct NodeStruct {
    int id;
    struct NodeStruct *next;
    struct NodeStruct *prev; //Create doubly linked list node
};

/** Structure for the whole list, including head and tail pointers. */
typedef struct {
  /** Pointer to the first node on the list (or NULL ). */
  Node *head;
  Node *last;
} List;

List *list;

List *makeList();
void insert(int idInsert, List *list);
static void *addRecord(List *list, int newID);
static void printReverse(List *list);

int main(void) {

  //Create an empty list for you to start.
  list = (List *)makeList();

  addRecord(list, 1);
  addRecord(list, 2);
  addRecord(list, 3);
  addRecord(list, 4);
  addRecord(list, 7);
  insert(6, list);
  insert(0, list);
  insert(15, list);
  printReverse(list);

}

List *makeList()
{
  List *list = (List *) malloc( sizeof( List ) );
  list->head = NULL;
  list->last = NULL;
  return list;
}

//Insert the record based on the ID if no duplicates exist
void insert(int idInsert, List *list)
{
  // Insert at end, if list is empty or if id is greater than all existing ids
  // Short circuting protects from derefercing a NULL pointer
  if (list->last == NULL || idInsert > list->last->id) {
    addRecord(list, idInsert);
  } else if (idInsert < list->head->id) {  // Insert at start
    //Make the node with idInsert the first node
    Node *new = malloc(sizeof(Node)); //Allocate memory for the new node

    list->head->prev = new;
    new->prev = NULL;
    //Add in data
    new->id = idInsert;

    new->next = list->head;

    list->head = new;
  } else { // Insert in the middle
    //Locate the node before the point of insertion
    //Allocate memory for the node
    Node *new = malloc(sizeof(Node));

    //Add in data
    new->id = idInsert;

    Node *current = list->head;
    while (current->next != NULL && current->next->id < new->id) {
      current = current->next;
    }
    new->next = current->next;
    if (current->next != NULL) {
      new->next->prev = new;
    }
    current->next = new;
    new->prev = current;
  }

  //Print this message if successful
  printf("RECORD INSERTED: %d\n", idInsert);
}

static void *addRecord(List *list, int newID) 
{
  //Allocate memory for the node
  Node *new = malloc(sizeof(Node)); 

  //Add in data
  new->id = newID; 

  new->prev = list->last;
  new->next = NULL;

  list->last = new;

  // if list is empty
  if(!list->head)
  {
    list->head = new;
    return EXIT_SUCCESS;
  }

  Node **next_p = &list->head;
  while (*next_p) {
    next_p = &(*next_p)->next;
  }
  *next_p = new;

  return EXIT_SUCCESS;
}

static void printReverse(List *list) {
    Node **tail = &list->last;
    printf("LIST IN REVERSE ORDER:\n");

    //Traversing until tail end of linked list
    while (*tail) {
        printf("Item ID: %d\n", (*tail)->id);
        tail = &(*tail)->prev;
    }
}

Output:

RECORD INSERTED: 6
RECORD INSERTED: 0
RECORD INSERTED: 15
LIST IN REVERSE ORDER:
Item ID: 15
Item ID: 7
Item ID: 6
Item ID: 4
Item ID: 3
Item ID: 2
Item ID: 1
Item ID: 0

Appendix

Notice how I approach the special cases of insert at the start and end before tackling the middle case. That is because your list has head and last pointers, these special insertions can get done in constant time, O(1), since you don't have to scan (iterate over) the list.

However, in the middle insertion, you have to scan the list, in order to locate the appropriate index, and then insert the node at that index.

Remember: the operation of traversing a list can take linear time (traversing the whole list), which in asymptotic notation is O(n), where n is the size of the list.

PS: I also checked the next pointer, by using the print (in normal order) method discussed in the linked question.

PPS: When you are done, do not forget to free the list. I have a method for this in List (C), which is the same for a double linked list, except, that you also have to set the head and last pointers to NULL too.

Upvotes: 1

Related Questions