Adding and Sorting a Linked List in C
In my assignment, I have to write a function that takes a pointer to the "LNode" structure and an integer argument as arguments. Then I have to not only add that integer to the linked list, but also position it so that the list is in the correct ascending order. I have tried several different attempts and this is my post code.
LNode* AddItem(LNode *headPtr, int newItem)
{
auto LNode *ptr = headPtr;
ptr = malloc(sizeof(LNode));
if (headPtr == NULL)
{
ptr->value = newItem;
ptr->next = headPtr;
return ptr;
}
else
{
while (headPtr->value > newItem || ptr->next != NULL)
{
printf("While\n"); // This is simply to let me know how many times the loop runs
headPtr = headPtr->next;
}
ptr->value = newItem;
ptr->next = headPtr;
return ptr;
}
} // end of "AddItem"
When I run it and try to insert, say, 5 and then 3, 5 comes up, but then the while loop runs once and I get a segmentation error.
Also I cannot change the arguments as part of the skeleton code for this project. Thanks to everyone who can help.
If it helps, it looks like this:
typedef struct LNode
{
int value;
struct LNode *next;
} LNode;
source to share
In your loop
while (headPtr->value > newItem || ptr->next != NULL)
{
printf("While\n"); // This is simply to let me know how many times the loop runs
headPtr = headPtr->next;
you are checking if uninitialised ptr->next
(not) is NULL
. This is unreasonable and can lead to chaos assuming that the bit pattern in that part ptr
does not match the pointer NULL
, because in the condition ||
in the condition, then the loop condition is always true and you run the end of your list.
Either way ||
is wrong, you need &&
both conditions must be met, something is wrong NULL
, and the relationship between these values must be met.
And, since you want the list to be in ascending order, you must traverse the list, and the value in the list is less than the value to be inserted.
But you must stop before the specified value is greater or greater than the new value, because you must change the next
node pointer , after which you will enter the new value.
if (headPtr->value >= newItem) {
ptr->value = newItem;
ptr->next = headPtr;
return ptr;
}
while(headPtr->next != NULL && headPtr->next->value < newItem) {
headPtr = headPtr->next;
}
// Now headPtr is the node behind which the new item is to be inserted
ptr->value = newItem;
ptr->next = headPtr->next;
headPtr->next = ptr;
return ??
But which pointer will you return? If the new item is the first in the list, you return a pointer to the first node. If you also want to do this, if a new item is inserted later, you need to keep (a copy of) the original headPtr
and put it back.
source to share
Wrong condition for your cycle. You never install ptr->next
, but use it to test ptr->next!=NULL
, which means it headPtr=headPtr->next
goes in a loop. Therefore, you must set: ptr->next=NULL
after setting its value.
You can also print these lines and put them at the top:
ptr->value = newItem; ptr->next = headPtr;
Try the following:
LNode* AddItem(LNode *headPtr, int newItem)
{
auto LNode *ptr, *temp, *orghead;
orghead = headPtr;
int fl=0;
ptr = malloc(sizeof(LNode));
ptr->value = newItem;
ptr->next = NULL;
temp = ptr;
if (headPtr == NULL)
return ptr;
else
{
while(headPtr != NULL && headPtr->value < newItem)
{
printf("While\n");
fl =1;
temp = headPtr;
headPtr = headPtr->next;
}
temp->next = ptr;
ptr->next = headPtr;
if(fl) return orghead;
else return temp;
}
} // end of "AddItem"
source to share
Your while loop continues to the end of your linked list, and your last element is null. So, in your state, you are dereferencing a null node (headPtr), thus getting a segmentation fault. I think you need to check if your node is null or not:
while (headPtr != NULL && (headPtr->value > newItem || ptr->next != NULL))
source to share
so true of all of the above
while (headPtr->value > newItem || ptr->next != NULL)
{
printf("While\n"); // This is simply to let me know how many times the loop runs
headPtr = headPtr->next;
}
You are not checking for null Condition for headPtr inside While
at this point
headPtr = headPtr->next;
headPtr-> next may be null, causing your program to crash
bit more
LNode* AddItem(LNode *headPtr, int newItem)
{
auto LNode *ptr = headPtr; ?
ptr = malloc(sizeof(LNode));
if (headPtr == NULL)
{
ptr->value = newItem;
ptr->next = headPtr;
return ptr;
}
consider headPtr not NULL, now ptr points to some heap malloc ptr-> next may or may not be NULL in this case
while (headPtr->value > newItem || ptr->next != NULL)
will be unpredictable
Maybe you need to take a little look at your logic
see below for pseudo logic if you like
LNode* add_time(LNode *headptr , data){
LNode *ptr = headptr, *temp;
temp = malloc(sizeof(LNode));
if(!temp)
return ptr;
temp->next = NULL;
temp->value= data;
if(ptr == NULL){
/** There is no list**/
ptr = temp;
return ptr;
}
/* go to last node*/
while(ptr->next)
ptr = ptr->next;
ptr->next = temp;
return ptr;
}
source to share