ðŸŽ‰ Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io ðŸŽ‰

# birchmd's solution

## to Linked List in the F# Track

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

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.

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

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

open Xunit
open FsUnit.Xunit

[<Fact>]
let ``Push and pop are first in last out order`` () =

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`` () =

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`` () =

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`` () =

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`` () =

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`` () =

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`` () =

val1 |> should equal 20

val2 |> should equal 10

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

{ data: int

{ 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 }

| None -> failwith "pop on empty list"
| Some backNode ->
match backNode.prev with
| None ->
backNode.data
| Some _ as node ->
backNode.data

| None -> failwith "shift on empty list"
| Some frontNode ->
match frontNode.next with
| None ->
frontNode.data
| Some _ as node ->
frontNode.data

else
// `get` is safe since the option being present is checked by the `isEmpty` function
let node =
{ data = newValue
next = None }
backNode.next <- Some node

else
// `get` is safe since the option being present is checked by the `isEmpty` function
let node =
{ data = newValue
prev = None