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.
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"
To run the tests, run the command dotnet test
from within the exercise directory.
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.
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.
Classic computer science topic
// 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 Node<'a> = {
mutable prev: Node<'a> option
mutable next: Node<'a> option
value: 'a
}
type LinkedList<'a> = {
mutable head: Node<'a> option
mutable tail: Node<'a> option
}
let mkLinkedList () = { head = None; tail = None }
let pop (linkedList: LinkedList<'a>) =
match linkedList.tail with
| None -> failwith "Cannon pop an empty list."
| Some(tailNode) ->
let result = tailNode.value
match tailNode.prev with
| Some(prevNode) ->
prevNode.next <- None
linkedList.tail <- Some(prevNode)
| None ->
linkedList.head <- None
linkedList.tail <- None
result
let shift (linkedList: LinkedList<'a>) : 'a =
match linkedList.head with
| None -> failwith "Cannon shift an empty list."
| Some(headNode) ->
let result = headNode.value
match headNode.next with
| Some(nextNode) ->
nextNode.prev <- None
linkedList.head <- Some(nextNode)
| None ->
linkedList.head <- None
linkedList.tail <- None
result
let push newValue (linkedList: LinkedList<'a>) =
match linkedList.tail with
| None ->
let node = { prev = None; next = None; value = newValue }
linkedList.head <- Some(node)
linkedList.tail <- Some(node)
| Some(tailNode) ->
let node = { prev = Some(tailNode); next = None; value = newValue }
tailNode.next <- Some(node)
linkedList.tail <- Some(node)
let unshift newValue (linkedList: LinkedList<'a>) =
match linkedList.head with
| None ->
let node = { prev = None; next = None; value = newValue }
linkedList.head <- Some(node)
linkedList.tail <- Some(node)
| Some(headNode) ->
let node = { prev = None; next = Some(headNode); value = newValue }
headNode.prev <- Some(node)
linkedList.head <- Some(node)
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.
Level up your programming skills with 3,443 exercises across 52 languages, and insightful discussion with our volunteer team of welcoming mentors. Exercism is 100% free forever.
Sign up Learn More
Community comments