There were a few issues and the code is actually much simpler.
You were doing malloc twice instead of only once, so you were leaking memory on each call.
Don't cast malloc:. See: Do I cast the result of malloc?
SinglyLinkedListNode is a bit long. When used in a lot of places, this doesn't scale well. How about something shorter like Node or SlNode
Here's a refactored version:
#include <stdio.h>
#include <stdlib.h>
typedef struct node Node;
struct node {
int data;
Node *next;
};
Node *
insertNodeAtPosition(Node *head, int data, int position)
{
int i = 0;
Node *prev;
Node *pcurr;
Node *pnew;
pnew = malloc(sizeof(Node));
pnew->data = data;
// find the correct place to insert
prev = NULL;
for (pcurr = head; pcurr != NULL; pcurr = pcurr->next, i += 1) {
if (i >= position)
break;
prev = pcurr;
}
// link up the element that will follow the new node
pnew->next = pcurr;
// insert into middle or end of list
if (prev != NULL)
prev->next = pnew;
// insert into empty list or _before_ the first node
else
head = pnew;
return head;
}
void
printlist(Node *head)
{
Node *pcurr;
printf("List:");
for (pcurr = head; pcurr != NULL; pcurr = pcurr->next)
printf(" %d",pcurr->data);
printf("\n");
}
int
main(void)
{
FILE *fi;
Node *head = NULL;
int count;
int newval;
int pos;
fi = fopen("input.txt","r");
if (fi == NULL) {
perror("input.txt");
exit(1);
}
fscanf(fi," %d",&count);
for (int i = 0; i < count; ++i) {
fscanf(fi," %d",&newval);
printf("new: %d\n",newval);
head = insertNodeAtPosition(head,newval,count + 10);
}
printlist(head);
while (1) {
if (fscanf(fi," %d %d",&newval,&pos) != 2)
break;
printf("insert: %d at %d\n",newval,pos);
head = insertNodeAtPosition(head,newval,pos);
}
printlist(head);
fclose(fi);
return 0;
}
Here's the test file: input.txt:
3
16 13 7
1 2
9 0
8 0
Here is the program output:
new: 16
new: 13
new: 7
List: 16 13 7
insert: 1 at 2
insert: 9 at 0
insert: 8 at 0
List: 8 9 16 13 1 7
UPDATE:
can you also tell me why we have to use a pointer *prev? why only pcurr and pnew are not sufficient? It would help me in learning this new concept being a beginner.
Sure. If we're inserting at the head of the list because the list is empty or we want to insert at the head (i.e. we want a new head even if we have other nodes in the list), we adjust head.
But, if we're inserting in the middle of the list or appending to the end of the list, we need to know what the previous node is.
Consider that we're trying to append to the end of the list. We need to know the existing/prior tail [last element] of the list. If we have:
head | node1 | node2 | node3
Then, node3 is the tail of the list. node3->next will be NULL. To append, we create the new node (pnew) and we have to set node3->next = pnew, so we get:
head | node1 | node2 | node3 | pnew
prev
Here, prev will end up having the value of node3, so setting prev->next = pnew is just like setting node3->next = pnew. Note that when appending to the end, pcurr will be NULL.
We call it prev because it (the previous node) can also be any node that we wish to insert after, even if prev is in the middle of the list (e.g. node2). That would look like (before the insertion):
head | node1 | node2 | node3
prev pcurr
After the insertion, we want:
head | node1 | node2 | pnew | node3
prev pcurr
In this case, pcurr will be node3 (i.e. prev->next).
So, prev points to the node just prior to where we want to insert pnew and pcurr points to the node just after where we want to insert pnew.
In other words, after insertion, prev is the node just to the left of pnew (i.e. the node that precedes it). pcurr is the node just to the right of pnew (i.e. the node that follows it). If pcurr is null, there is no following node, but setting pnew->next = pcurr works in all cases, regardless of the values of head or prev being null or not.
If prev ends up being NULL, this means that the list is either empty or we wish to insert pnew at the head/front of the list. In that case, we can't try to dereference [a null] prev, so we just set head to pnew. Then, we're returning an updated head pointer.
There are several possible list states and insertion operations:
- list is empty (adjust the head)
- we want to insert the new node before the head of the [non-empty] list (adjust the head)
- we want to insert the new node somewhere in the middle of the list
- we want to append the new node at the end of the list (adjust tail or head if tail is null)
I think it would be helpful for you to diagram each of these separate cases using pencil and paper. Then, verify, by hand, that the code handles each of these cases, even if the list has prior elements or is empty.
The important thing to note about the above code is that it uses variables that work for several different cases, using the same code path, minimizing the number of if/else clauses to handle the various edge cases in a uniform way.
The type of simplification I did occurs again and again when coding. Thoroughly understanding what was done and why will help you immeasurably in the future.
Any one function that one writes, by itself, may not seem like much. But, magnify this across hundreds or thousands of functions, and it will pay dividends far beyond the initial extra work.
A maxim: As simple as it needs to be--and no simpler
The simpler (i.e. the cleaner) the code, the more likely it is to be correct, complete, and the easier it is to check for correctness. Contrary to popular belief, I've also found that the simpler code also tends to be faster.
