Uniform Linked Lists Contraction

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\mathrm{/}c$ for a suitable constant $c$ we can pack the linked list into an array of size $n\mathrm{/}d$ for a constant $1<d\le c$ in the time of 3 coloring the list. Thus for a set of linked lists with a total of $n$ elements and the longest list has $l$ elements our algorithm contracts them in $O(n\log i/p+(\log^{(i)}n+\log i )\log \log l+ \log l)$ time, for an arbitrary constructible integer $i$, with $p$ processors on the EREW PRAM, where ${\log }^{(1)}n=\log n$ and ${\log }^{(t)}n=\log {\log }^{(t-1)}n$ and $\log^*n=\min { i|\log^{(i)} n < 10}$\mathrm{.}When$i$isaconstantwegettime$O(n/p+\log^{(i)}n\log \log l+\log l)$\mathrm{.}Thuswhen$l=\Omega (\log^{©}n)$ for any constant $c$ we achieve $O(n\mathrm{/}p+\log l)$ time. The previous best deterministic EREW PRAM algorithm has time $O(n\mathrm{/}p+\log n)$ and best CRCW PRAM algorithm has time $O(n\mathrm{/}p+\log n\mathrm{/}\log \log n+\log l)$. Keywords: Parallel algorithms, linked list, linked list contraction, uniform linked list contraction, EREW PRAM.