Uniform Linked Lists Contraction

Yijie Han

We present a parallel algorithm (EREW PRAM algorithm) for linked lists contraction. We show that when we contract a linked list from size $n$ to size $n/c$ for a suitable constant…