# 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

``````assert(
NonEmptyDoubleLinkedList.of(1, 2, 3).toList == List(1, 2, 3),
"We can turn the DLL into a List"
)
assert(
"After creation, the focus item is the first item"
)
assert(
"After creation, there is no previous item"
)
assert(
NonEmptyDoubleLinkedList.of(1, 2, 3).withoutNext.toList == List(1, 3),
"We can exclude a next item safely"
)
assert(
"Last item is correctly found"
)
assert(
NonEmptyDoubleLinkedList.of(1, 2, 3).last.toList == List(1, 2, 3),
"Last item can reproduce a correct list"
)
assert(
List(1, 2, 9, 3),
"We can insert before"
)
assert(
List(1, 2, 3, 9),
"We can insert after"
)
assert(
List(1, 2, 9, 3),
"We can insert before and seek"
)
assert(
List(1, 2, 3, 9),
"We can insert after and seek"
)
assert(
NonEmptyDoubleLinkedList.of(1, 2, 3).last.first.toList == List(1, 2, 3),
"Going to last, and then first reproduces the order"
)
assert(
List(1, 3),
"We can exclude a previous item safely"
)
``````

## 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

1. ### Drop, Take, dropRight, takeRight

Scala's `drop` and `take` methods typically remove or select `n` items from a collection.

``````assert(List(1, 2, 3).drop(2) == List(3))

assert(List(1, 2, 3).take(2) == List(1, 2))

assert(List(1, 2, 3).dropRight(2) == List(1))

assert(List(1, 2, 3).takeRight(2) == List(2, 3))

assert((1 to 5).take(2) == (1 to 2))
``````
2. ### 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!

``````assert(Option(1).flatMap(x => Option(x + 2)) == Option(3))

assert(Option(1).flatMap(x => None) == None)
``````
3. ### Partial Function

A Partial Function in Scala is similar to function type `A => Option[B]` (Option Type).

``````def getNaming(num: Int): Option[String] =
PartialFunction.condOpt(num) { case 1 => "One" }

assert(getNaming(1) == Some("One"))

assert(getNaming(2) == None)
``````
4. ### Pattern Matching

Pattern matching in Scala lets you quickly identify what you are looking for in a data, and also extract it.

``````assert("Hello World".collect {
case character if Character.isUpperCase(character) => character.toLower
} == "hw")
``````

# Scala Algorithms: The most comprehensive library of algorithms in standard pure-functional Scala

### Study our 89 Scala Algorithms: 6 fully free, 89 published & 0 upcoming

Fully unit-tested, with explanations and relevant concepts; new algorithms published about once a week.

### Explore the 21 most useful Scala concepts

To save you going through various tutorials, we cherry-picked the most useful Scala concepts in a consistent form.

## Register now (free)

Register with GitHub

This gives you access to free test cases & hints for all our 89 published algorithms as well as our installation-free Scala IDE.

You can then choose to subscribe to "Scala Algorithms Unlimited", which gets you access to every current and upcoming algorithm solution. We use Stripe so your data is safe.

We will e-mail you at most once per week with new algorithms and relevant content.
Your data is protected and unsubscribing is straightforward. 