# 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

## How our 100 algorithms look

1. A description/goal of the algorithm.
2. An explanation with both Scala and logical parts.
3. A proof or a derivation, where appropriate.
4. Links to Scala concepts used in this specific algorithm, also unit-tested.
5. An implementation in pure-functional immutable Scala, with efficiency in mind (for most algorithms, this is for paid subscribers only).
6. Unit tests, with a button to run them immediately in our in-browser IDE.

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

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

### Explore the 22 most useful Scala concepts

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

## Subscribe to Scala Algorithms

Maximize your Scala with disciplined and consistently unit-tested solutions to 100+ algorithms.

Use it from improving your day-to-day data structures and Scala; all the way to interviewing.