5

I saw a SO question yesterday about implementing a classic linked list in Java. It was clearly an assignment from an undergraduate data structures class. It's easy to find questions and implementations for lists, trees, etc. in all languages.

I've been learning about Java lambdas and trying to use them at every opportunity to get the idiom under my fingers. This question made me wonder: How would I write a custom list or tree so I could use it in all the Java 8 lambda machinery?

All the examples I see use the built in collections. Those work for me. I'm more curious about how a professor teaching data structures ought to rethink their techniques to reflect lambdas and functional programming.

I started with an Iterator,but it doesn't appear to be fully featured.

Does anyone have any advice?

duffymo
  • 305,152
  • 44
  • 369
  • 561
  • 3
    As long as your custom Collection implements the Collection interface, you will have the `stream()` method, and will be able to process your custom class with a stream pipeline. – Eran Apr 24 '16 at 13:28
  • Thank you Eran, I'll give that a go with my linked list implementation and see if that sorts me out. – duffymo Apr 24 '16 at 13:29

2 Answers2

10

Exposing a stream view of arbitrary data structures is pretty easy. The key interface you have to implement is Spliterator, which, as the name suggests, combines two things -- sequential element access (iteration) and decomposition (splitting).

Once you have a Spliterator, you can turn that into a stream easily with StreamSupport.stream(). In fact, here's the stream() method from AbstractCollection (which most collections just inherit):

default Stream<E> stream() {
    return StreamSupport.stream(spliterator(), false);
}

All the real work is in the spliterator() method -- and there's a broad range of spliterator quality (the absolute minimum you need to implement is tryAdvance, but if that's all you implement, it will work sequentially, but will lose out on most of the stream optimizations.) Look in the JDK sources Arrays.stream(), IntStream.range()) for examples of how to do better.)

Brian Goetz
  • 90,105
  • 23
  • 150
  • 161
4

I'd look at http://www.javaslang.io for inspiration, a library that does exactly what you want to do: Implement custom lists, trees, etc. in a Java 8 manner.

It specifically doesn't closely couple with the JDK collections outside of importing/exporting methods, but re-implements all the immutable collection semantics that a Scala (or other FP language) developer would expect.

Lukas Eder
  • 211,314
  • 129
  • 689
  • 1,509
  • Thank you Lukas, I was completely ignorant of that library. I'll give it a look. – duffymo Apr 24 '16 at 13:45
  • 1
    I just pulled down the GitHub source. It's far more extensive than I would have guessed. That data structures professor will have to toss out those old notes. – duffymo Apr 24 '16 at 14:00
  • 1
    @duffymo: Indeed, there's a world beyond Java collections :) (and javaslang is just scratching the surface) – Lukas Eder Apr 24 '16 at 14:31
  • Jaysus, I can't write code anymore. This will make an undergrad's head explode. – duffymo Apr 24 '16 at 14:33
  • My concern is that the difficulty has become so great that writing your own data structure will be out of the reach of the average (or below average) developer. I thought the exercise might be worthwhile for somebody like me to rediscover how to do it using Java 8. – duffymo Apr 24 '16 at 15:30
  • 1
    I just suggested the library for *inspiration* :) – Lukas Eder Apr 24 '16 at 21:44