It is usual to keep a linked list sorted. That means rather than just inserting new nodes at the head or tail of the list you insert them at the right place.
Lets build a list with your example we will add the numbers 3,4,2,6,5,1 like this.
Code:
head of list is a null pointer of type node*
allocate memory for a node using new assigning pointer to head
add 3 to data field
add null to next field (i.e. no next node)
list looks like....
3--NULL
now we need to add a new node to hold the value 4.
compare 4 to head->item
if less add at front. but its not so we compare to next node and there isn't one so call insert at back func.
list now looks like
3--4--NULL
now we compare 2 to head->item and find its less so call add at front func to end up with a new list like....
2--3--4--NULL
now we compare 6 to head->item and find its greater so we traverse the list until we find where to insert.
In this case its a call to insert at back func again
list now looks like
2--3--4--6--NULL
now we add 5 so we compare again to head->item and follow the next pointers through the list until we compare to 6 and find its less so we insert new node just before 6
list now looks like
2--3--4--5--6--NULL
adding the 1 is just a compare then add at front to get
1--2--3--4--5--6--NULL
and your list is sorted as its built.
The inserts are nothing more than a bit of pointer manipulation and dynamic memory allocation.
