3

Coming from functional background, I am looking for equivalent of immutable singly linked list in Java.

Immutable singly linked lists give me freedom to define many lists with common tail. For example, if I have list = [1,2,3] and then I am creating two new lists:

first = [10 | list]
second = [15 | list]

I am not copying the list. Internally it looks more like this:

first -> 10 -> 1 -> 2 -> 3 -> null
second -> 15  /|\

I looked at Guava Lists, but I couldn't find information on implementation details. As far as I understand, it is a doubly linked list, so efficient prepend operation is impossible (please correct me, if I am wrong about that).

tkowal
  • 9,129
  • 1
  • 27
  • 51
  • Besides of CAD systems I can not imagine who needs that? – AlexWien Sep 29 '15 at 15:17
  • 2
    roll one yourself? probably not a lot of work, by subclassing `AbstractSequentialList` (you don't need to support the "previous" methods) – ZhongYu Sep 29 '15 at 15:22
  • 2
    @AlexWien: Anyone who regularly works with threads. You don't have to use monitors on immutable data structures, which can give reasonable speed up. – tkowal Sep 29 '15 at 15:23
  • @LucasRoss: Yes, this implementation doesn't have prepending. – tkowal Sep 29 '15 at 15:25
  • If lists are imuatble, then replace them with arrays, that would really speed up and save a lot of memory. Such fast things you only can do yourself. – AlexWien Sep 29 '15 at 15:43
  • 1
    @AlexWien: I have an algorithm with high branching factor (similar to enumerating all subsets of a set). This means, I have common parts (tails), but always different heads. With common tail, all 128 cores can use the same tail and only couple of different values in front (less copying). We are using arrays now and we want to compare, if this speeds things up or make everything slower, because of worse use of cache. – tkowal Sep 29 '15 at 16:35

2 Answers2

3

Did you try Functional Java? Also there's similar question, you could use that algorithm and make singly list from double.

Lii
  • 11,553
  • 8
  • 64
  • 88
Timofey
  • 823
  • 1
  • 8
  • 26
  • Functional java looks good: `fj.data.List` is immutable. I don't see in the docs, how it works internally, but I'll check it. Thank you! – tkowal Sep 29 '15 at 15:31
  • I doubt that this is an option. If you came from functional either use an functional language, or use plain java. If you have to use java, (e.g comercially) then nobody would like that you introduce fucntional java in that project. (I cannot imgaine that you will get a speed up (see comment about multithreading of the OP) using functional java) – AlexWien Sep 29 '15 at 15:48
  • @AlexWien: It is more academic project. We want to try different options and check, which one is faster, so introducing dependencies is not an issue. – tkowal Sep 29 '15 at 16:37
1

Try Vavr it's open source so you can see the internal implementation.

Navneet kumar
  • 1,696
  • 1
  • 17
  • 26