Talk:List ranking

The problem is unclear to me

"Although it is straightforward to solve this problem efficiently on a sequential computer, by traversing the list in order, it is more complicated to solve in parallel". Assuming a singly-linked list, you have no choice but to step through it linearly. If it was doubly linked I suppose you can work from both ends.

Am I allowed to assume there are multiple entry points into the list at various places (like a sort of skiplist) or what?

thanks 85.211.200.201 (talk) 20:08, 9 October 2018 (UTC)[reply]

Your claim "Assuming a singly-linked list, you have no choice but to step through it linearly" is false. The parallel algorithms described in this article do assume a singly-linked list, but solve this problem without stepping through it linearly. The list is stored in memory, for instance in an array of records with next-record pointers, in such a way that any list element can be directly accessed but you don't know at the start of the computation what their order as a list is. —David Eppstein (talk) 20:28, 9 October 2018 (UTC)[reply]

OK, not a linked list quite as a progammer would typically consider it, as it effectively exposes its implementation, but yes, that's a nice clear answer. Thank you, and BTW that's certainly not the first comp-sci/maths question you've answered me! 92.0.29.191 (talk) 10:52, 10 October 2018 (UTC)[reply]