Let's consider a function insert_after(val, P)
that will insert a
node containing value val
after p
so that sorted
order is maintained. Here's what we need to do
in pictures:
We want to add a node with data after p .
We are using the following struct definition:


Create the new node we want, with the proper data and
next values (drag your mouse to see the code below).
Node *T = new Node; T>data = val; T>next = p>next; 

Splice our new node in after the node p points to
(drag your mouse to see the code below).
p>next = T; 

Done! 
void insert_after(double val, Node* p) { // When you call this function, make sure p is not NULL
Node* T = new Node;
T>data = val;
T>next = p>next;
p>next = T // if p is NULL, p>next will make your program will crash!!!
}
L
is empty
add2front()
.
L
is nonempty
insert_after()
on this last node. add2back
function that works in just this way.


add2front
and
insert_after
, we can easily write a function
insertinorder(val,L)
that will insert a new value
val
into L
so that sorted order is maintained.
There are two cases to consider when we write the function:
val
to the front of the list.
val
after some node in the list.
val
is smaller than any value in the list. Note we
are dealing with an alreadysorted list, so we can easily check this
condition by comparing answer is when val
is smaller than the
value of the first node in the list!
if( L == NULL  val < L>data )
add2front(val, L);
insert_after()
.
p
point to the currentlyvisited node.
p
points to the last node (i.e., p>next
is NULL
).
In this case we need to insert val
after this last node p
.
val
(i.e., 9)
gets smaller than p>next>data
(i.e., 11) for the first
time, you find the right node p
.
for(Node* p = L; p != NULL; p = p>next) {
if( p>next == NULL  val < p>next>data ) {
insert_after(data, p);
break;
}
}
void insertinorder(double val, Node*& L) {
if( L == NULL  val < L>data ) {
add2front(val, L);
}
else {
for(Node* p = L; p != NULL; p = p>next) {
if( p>next == NULL  val < p>next>data ) {
insert_after(val, p);
break;
}
}
}
}
insertinorder
we can sort stuff pretty
easily with linked lists. For example, if you want to read in a
bunch of values and put them in sorted order, you can simply put
them in a list as you read them using insertinorder
,
and when you're done, you'll have a sorted list of values. Not
bad, eh?
Suppose that you already have a list and it's not in sorted
order. You could easily create a sorted copy of the list by
moving through you list a node at a time and calling
insertinorder
for that node's data.
Node* sortedcopy(Node* L) {
Node* S = NULL;
for(Node* p = L; p != NULL; p = p>next)
insertinorder(p>data,S);
return S;
}
This function returns a copy of the original list in sorted order.
insertinorder
function from above so
that duplicate values are not inserted, but rather simply
ignored. Thus, if used on the example code in which words
are entered, only unique words would appear — no
duplicates.
~/$ ./prog hi , bye , yo , ciao , hi , hallo , yo , sianara ; sinara 1 hallo 1 ciao 1 yo 2 bye 1 hi 2