Sorted Linked List

download source
The key to understanding sorted insertion is to have 2 pointers.

One is current, the other is trailer.


While the current is not NULL, and the incoming data to be inserted is larger than the current’s data, then we move forward

We move forward by having the trailer and current move forward. Trailer take on current. Current take on current’s next.

When we do find a node data, where the incoming node’s data is not larger, we stop. We have the trailer’s next point to the new node. The new node’s next take on current.

If the list empty, we simply use the first to point.