Here's one way to do it. Picture the list like this:
Code:
head
address
2
---------->address
41
-------------->address
173
------------>NULL
where each address is the address of a node in the list, the integer is the data member of the node, and an arrow is the pointer to the address of the next node in the list. then say you want to insert the value 53 into the list.
First you create a new node to hold 53.
Then use a node pointer called current and use it to search the list for a value which is greater than 53, in this case it is 173.
Code:
head
address
2
---------->address
41 current
-------------->address
173
------------>NULL
Then you search for the node just before that one using a pointer called previous, in this case it is the node 41.
Code:
address
2 previous
---------->address
41 current
-------------->address
173
------------>NULL
Then assign the address of new node to the pointer in previous and assign the address of current to pointer in new node.
Code:
head
address
2 previous
---------->address
41 newNode
--------------->address
53 current
------------->address
173
------------>NULL
Now put it into pseudo-code, taking into account special cases of no nodes in list, one node in list, and that value passed in to a general case will be the smallest value in the list:
Code:
struct node
{
int data
node * next
}
node * head = NULL
void insertVal(node * head, int val)
{
declare newNode using dynamic memory
assign val to newNode data
assign NULL to newNode next
declare two node pointers called current and previous
assign head to both current and previous
//no node in list
if current is NULL
{
assign newNode to head
}
//one node in list
else if current not NULL but current next is NULL
{
if newNode data less than current data
assign current to newNode next
assign newNode to head
else
assign newNode to current next
}
//general case
else if current not NULL and current next not NULL
{
while current next not NULL and current data < newNode data
{
assign current next to current
}
while current != head and previous->next->data not equal current data
{
assign previous next to previous
}
if current is same as head
assign current to newNode next
assign newNode to head
else
assign newNode to previous next
assign current to newNode next
}
}