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

# mafu's solution

## to Linked List in the F# Track

Published at Oct 15 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
type Node<'t> = {
Value : 't;
mutable Prev : 't Node option
mutable Next : 't Node option
}

mutable First : 't Node option;
mutable Last : 't Node option;
}

{First = None; Last = None;}
let mkNode (value : 't) (prev : 't Node option) (next : 't Node option) =
{Value = value; Prev = prev; Next = next}
linkedList.First <- mkNode newValue None None |> Some

| (None, None) -> failwith "Empty list. Nothing to shift"
| (Some some, None) ->
some.Value
| (None, Some some) ->
some.Value
| (Some first, Some last) ->
let (Some next) = first.Next
next.Prev <- None
first.Value

| (Some some as sngle, None) ->
let newNode = mkNode newValue None sngle |> Some
some.Prev <- newNode
| (None, (Some some as sngle)) | (Some some as sngle, _)  ->
let newNode = mkNode newValue None sngle |> Some
some.Prev <- newNode

| None, None -> failwith "Empty list. Nothing to pop."
| Some node, None ->
node.Value
| None, Some node ->
node.Value
| Some first, Some node ->
let (Some newLast) = node.Prev
newLast.Next <- None
if(newLast = first) then
None
else
Some newLast
node.Value

| (None, (Some some as last)) ->
let newNode = mkNode newValue last None |> Some
some.Next <- newNode
| (Some some as sngle, None) | (_, (Some some as sngle)) ->
let newNode = mkNode newValue sngle None |> Some
some.Next <- newNode