Hi Sven I'm collecting alternative Collection implementations in the project Container I do not remember if I have linkedList but we can add it there. You may wonder why I'm doing that? - I want to be able to have strong collections that are independent from the kernel - Ideally the kernel of Pharo should be mininmal so it means that I would like to have as few as possible as collections inside the bootstrapped kernel and that other collections are nicely packaged in Container. Now I can understand that others do not like what I'm doing but I will just continue. I have Grid, LinkedList, DoubleLinkedList, I have on my disc two implementation of Trees I should harvest BTrees and SkipList. If people want to help they are welcome, else I will just do it alone. Stef
Hi,
There exists a very elegant algorithm to detect cycles in linked lists.
https://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare
I know that our LinkedList was written with the assumption that there are no cycles. However, it seems to me that it would be nice to have a test to check for cycles. This could be useful while printing or inspecting a LinkedList (and prevent things from blowing up when there is a cycle).
Here is the implementation:
LinkedList>>#containsCycle | slow fast | slow := fast := firstLink. [ slow notNil and: [ fast notNil and: [ fast nextLink notNil ] ] ] whileTrue: [ slow := slow nextLink. fast := fast nextLink nextLink. slow == fast ifTrue: [ ^ true ] ]. ^ false
And one of the tests:
LinkedListTests>>#testCycles 1 to: 42 do: [ :each | list := LinkedList withAll: (1 to: each). "Warning: the following statement creates a cylce, inspecting/viewing list will probably fail" list lastLink nextLink: list firstLink. self assert: list containsCycle ]
Opinions ?
Sven
-- Using Opera's mail client: http://www.opera.com/mail/