Scala algorithm: Pure-functional double linked list
Published
Algorithm goal
Doubly linked lists are quite the interesting thing, because they are by definition mutable.
Implement one pure-functionally.
Test cases in Scala
Algorithm in Scala
57 lines of Scala (compatible versions 2.13 & 3.0).
Explanation
Interestingly enough, we can use plain Scala Lists, and construct them at O(1) performance for many of the operations, but not all.
The implementation contains many methods that may come useful. We basically represent the doubly linked list as a list of 'currentItem', 'preceding' and 'following' lists. It works similar to a 'Zipper' structure. (this is © from www.scala-algorithms.com)
Scala concepts & Hints
Drop, Take, dropRight, takeRight
Scala's `drop` and `take` methods typically remove or select `n` items from a collection.
Option Type
The 'Option' type is used to describe a computation that either has a result or does not. In Scala, you can 'chain' Option processing, combine with lists and other data structures. For example, you can also turn a pattern-match into a function that return an Option, and vice-versa!
Partial Function
A Partial Function in Scala is similar to function type `A => Option[B]` (Option Type).
Pattern Matching
Pattern matching in Scala lets you quickly identify what you are looking for in a data, and also extract it.