🎉 Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io 🎉
Avatar of birchmd

birchmd's solution

to Linked List in the F# Track

Published at Apr 24 2020 · 0 comments
Instructions
Test suite
Solution

Implement a doubly linked list.

Like an array, a linked list is a simple linear data structure. Several common data types can be implemented using linked lists, like queues, stacks, and associative arrays.

A linked list is a collection of data elements called nodes. In a singly linked list each node holds a value and a link to the next node. In a doubly linked list each node also holds a link to the previous node.

You will write an implementation of a doubly linked list. Implement a Node to hold a value and pointers to the next and previous nodes. Then implement a List which holds references to the first and last node and offers an array-like interface for adding and removing items:

  • push (insert value at back);
  • pop (remove value at back);
  • shift (remove value at front).
  • unshift (insert value at front);

To keep your implementation simple, the tests will not cover error conditions. Specifically: pop or shift will never be called on an empty list.

If you want to know more about linked lists, check Wikipedia.

Hints

A doubly linked list is a mutable data structure. As F# is a functional-first language, immutability is generally preferred, but there are language features that allow the use of mutation where it is required.

  • The mutable keyword can be placed before let bindings and record fields, allowing you to assign new values to them.

  • Class properties can be made mutable by specifying a property setter with the set keyword.

Mutable bindings must be re-assigned with <-

let mutable x = "initial value"
x <- "new value"

Running the tests

To run the tests, run the command dotnet test from within the exercise directory.

Autoformatting the code

F# source code can be formatted with the Fantomas tool.

After installing it with dotnet tool restore, run dotnet fantomas . to format code within the current directory.

Further information

For more detailed information about the F# track, including how to get help if you're having trouble, please visit the exercism.io F# language page.

Source

Classic computer science topic

LinkedListTests.fs

// This file was created manually and its version is 1.0.0.

module LinkedListTest

open Xunit
open FsUnit.Xunit
open LinkedList

[<Fact>]
let ``Push and pop are first in last out order`` () =
    let linkedList = mkLinkedList ()
    linkedList |> push 10
    linkedList |> push 20

    let val1 = pop linkedList
    let val2 = pop linkedList

    val1 |> should equal 20
    val2 |> should equal 10

[<Fact(Skip = "Remove this Skip property to run this test")>]
let ``Push and shift are first in first out order`` () =
    let linkedList = mkLinkedList ()
    linkedList |> push 10
    linkedList |> push 20

    let val1 = shift linkedList
    let val2 = shift linkedList

    val1 |> should equal 10
    val2 |> should equal 20

[<Fact(Skip = "Remove this Skip property to run this test")>]
let ``Unshift and shift are last in first out order`` () =
    let linkedList = mkLinkedList ()
    linkedList |> unshift 10
    linkedList |> unshift 20

    let val1 = shift linkedList
    let val2 = shift linkedList

    val1 |> should equal 20
    val2 |> should equal 10

[<Fact(Skip = "Remove this Skip property to run this test")>]
let ``Unshift and pop are last in last out order`` () =
    let linkedList = mkLinkedList ()
    linkedList |> unshift 10
    linkedList |> unshift 20

    let val1 = pop linkedList
    let val2 = pop linkedList

    val1 |> should equal 10
    val2 |> should equal 20

[<Fact(Skip = "Remove this Skip property to run this test")>]
let ``Push and pop can handle multiple values`` () =
    let linkedList = mkLinkedList ()
    linkedList |> push 10
    linkedList |> push 20
    linkedList |> push 30

    let val1 = pop linkedList
    let val2 = pop linkedList
    let val3 = pop linkedList

    val1 |> should equal 30
    val2 |> should equal 20
    val3 |> should equal 10

[<Fact(Skip = "Remove this Skip property to run this test")>]
let ``Unshift and shift can handle multiple values`` () =
    let linkedList = mkLinkedList ()
    linkedList |> unshift 10
    linkedList |> unshift 20
    linkedList |> unshift 30

    let val1 = shift linkedList
    let val2 = shift linkedList
    let val3 = shift linkedList

    val1 |> should equal 30
    val2 |> should equal 20
    val3 |> should equal 10

[<Fact(Skip = "Remove this Skip property to run this test")>]
let ``All methods of manipulating the linkedList can be used together`` () =
    let linkedList = mkLinkedList ()
    linkedList |> push 10
    linkedList |> push 20

    let val1 = pop linkedList

    val1 |> should equal 20

    linkedList |> push 30
    let val2 = shift linkedList

    val2 |> should equal 10

    linkedList |> unshift 40
    linkedList |> push 50

    let val3 = shift linkedList
    let val4 = pop linkedList
    let val5 = shift linkedList

    val3 |> should equal 40
    val4 |> should equal 50
    val5 |> should equal 30
module LinkedList

type LinkedListNode =
    { data: int
      mutable prev: LinkedListNode option
      mutable next: LinkedListNode option }

type LinkedList =
    { mutable front: LinkedListNode option
      mutable back: LinkedListNode option }

let mkLinkedList() =
    { front = None
      back = None }

let isEmpty =
    function
    | { front = None; back = None } -> true
    | { front = Some _; back = Some _ } -> false
    | _ -> failwith "Invalid list state"

let private setFirstValue value linkedList =
    let node =
        { data = value
          prev = None
          next = None }
    linkedList.front <- Some node
    linkedList.back <- Some node

let pop linkedList =
    match linkedList.back with
    | None -> failwith "pop on empty list"
    | Some backNode ->
        match backNode.prev with
        | None ->
            linkedList.front <- None
            linkedList.back <- None
            backNode.data
        | Some _ as node ->
            linkedList.back <- node
            backNode.data

let shift linkedList =
    match linkedList.front with
    | None -> failwith "shift on empty list"
    | Some frontNode ->
        match frontNode.next with
        | None ->
            linkedList.front <- None
            linkedList.back <- None
            frontNode.data
        | Some _ as node ->
            linkedList.front <- node
            frontNode.data

let push newValue linkedList =
    if linkedList |> isEmpty then
        linkedList |> setFirstValue newValue
    else
        // `get` is safe since the option being present is checked by the `isEmpty` function
        let backNode = Option.get linkedList.back
        let node =
            { data = newValue
              prev = linkedList.back
              next = None }
        backNode.next <- Some node
        linkedList.back <- Some node


let unshift newValue linkedList =
    if linkedList |> isEmpty then
        linkedList |> setFirstValue newValue
    else
        // `get` is safe since the option being present is checked by the `isEmpty` function
        let frontNode = Option.get linkedList.front
        let node =
            { data = newValue
              prev = None
              next = linkedList.front }
        frontNode.prev <- Some node
        linkedList.front <- Some node

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?