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(
  NonEmptyDoubleLinkedList.of(1, 2, 3).currentItem == 1,
  "After creation, the focus item is the first item"
)
assert(
  NonEmptyDoubleLinkedList.of(1, 2, 3).previous.isEmpty,
  "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(
  NonEmptyDoubleLinkedList.of(1, 2, 3).last.currentItem == 3,
  "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(
  NonEmptyDoubleLinkedList.of(1, 2, 3).last.insertBefore(9).toList ==
    List(1, 2, 9, 3),
  "We can insert before"
)
assert(
  NonEmptyDoubleLinkedList.of(1, 2, 3).last.insertAfter(9).toList ==
    List(1, 2, 3, 9),
  "We can insert after"
)
assert(
  NonEmptyDoubleLinkedList.of(1, 2, 3).last.insertBeforeAndSeek(9).toList ==
    List(1, 2, 9, 3),
  "We can insert before and seek"
)
assert(
  NonEmptyDoubleLinkedList.of(1, 2, 3).last.insertAfterAndSeek(9).toList ==
    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(
  NonEmptyDoubleLinkedList.of(1, 2, 3).last.withoutPrevious.toList ==
    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))
   

   ▶ Run code in the IDE

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)
   

   ▶ Run code in the IDE

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)
   

   ▶ Run code in the IDE

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")
   

   ▶ Run code in the IDE