Q. Rank the list elements in terms of distance?

Rank the list elements in terms of distance from each to last element in given linear linked list.

A parallel algorithm for this problem is given below. The algorithm presumes there are p number of processors.

Algorithm:

Processor j, 0≤ j

if next[j]=j then 

rank[j]=0

else rank[j] =1

endif

while rank[next[first]]≠0 Processor j, 0≤ j

rank[j]=rank[j]+rank[next[j]]

next[j]=next[next[j]]

endwhile

The working of above algorithm is explained by the diagram below:

Figure: Finding rank of elements