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.
|
1 2 3 4 5 6 |
while (current != nullptr && data > current->iData) { //traverse forward trailer = current; current = current->pNext; } |
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.
|
1 2 3 4 5 |
if(trailer==nullptr) first = new Node(data, first); else //your data is smaller than durrent node data trailer->pNext = new Node(data, current); |