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?
