Background
Linked lists are a well-known data structure, so I won't waste too much detail on them. Suffice to say that a linked list consists of "cells". Each cell contains some kind of value and a reference to the next cell (except the last one, which contains an empty reference).
I implemented a linked list in Clojure as an exercise.
The code
(ns linked-list.core)
(defn create-linked-list [] {})
(defn add-to-linked-list [{:keys [value next-node] :as linked-list} new-value]
(let [new-node {:value new-value :next-node nil}]
(if (= {} linked-list)
new-node
(let [new-tail (if (nil? next-node) new-node (add-to-linked-list next-node new-value))]
(assoc-in linked-list [:next-node] new-tail)))))
(defn contains-linked-list? [{:keys [value next-node] :as linked-list} query-value]
(if (empty? linked-list)
false
(or (= value query-value) (recur next-node query-value))))
(defn get-nth-linked-list [{:keys [value next-node] :as linked-list} n]
(if (< n 1)
value
(recur next-node (dec n))))
(defn without-element-linked-list [linked-list n]
(loop [{:keys [value next-node] :as act-node} linked-list counter 0 linked-list-accum (create-linked-list)]
(let [new-linked-list (if (= counter n) linked-list-accum (add-to-linked-list linked-list-accum value))]
(if (nil? next-node) new-linked-list
(recur next-node (inc counter) new-linked-list)))))
The tests
(ns linked-list.core-test
(:require [clojure.test :refer :all]
[linked-list.core :refer :all]))
(deftest create-linked-list-test
(testing "create linked list"
(is (= {} (create-linked-list)))))
(def empty-linked-list (create-linked-list))
(deftest add-to-linked-list-test
(testing "add to linked list"
(is (= {:value 10 :next-node nil} (add-to-linked-list empty-linked-list 10)))
(is (= {:value 10 :next-node {:value 20 :next-node nil}} (add-to-linked-list (add-to-linked-list empty-linked-list 10) 20)))
(is (= {:value 10 :next-node {:value 20 :next-node {:value 30 :next-node nil}}} (add-to-linked-list (add-to-linked-list (add-to-linked-list empty-linked-list 10) 20) 30)))))
(def one-element-linked-list (add-to-linked-list empty-linked-list 10))
(def two-element-linked-list (add-to-linked-list one-element-linked-list 20))
(deftest contains-linked-list-test
(let [one-element-linked-list (add-to-linked-list empty-linked-list 10)
two-element-linked-list (add-to-linked-list one-element-linked-list 20)]
(testing "does a linked list contain a value"
(is (false? (contains-linked-list? empty-linked-list 10)))
(is (true? (contains-linked-list? one-element-linked-list 10)))
(is (true? (contains-linked-list? two-element-linked-list 20)))
(is (false? (contains-linked-list? two-element-linked-list 30))))))
(deftest get-nth-linked-list-test
(testing "get the nth element of linked list"
(is (nil? (get-nth-linked-list empty-linked-list 0)))
(is (= 10 (get-nth-linked-list one-element-linked-list 0)))
(is (= 20 (get-nth-linked-list two-element-linked-list 1)))))
(def three-element-linked-list (add-to-linked-list two-element-linked-list 30))
(deftest without-element-linked-list-test
(testing "remove the nth element of linked list"
(is (= empty-linked-list (without-element-linked-list empty-linked-list 0)))
(is (= empty-linked-list (without-element-linked-list one-element-linked-list 0)))
(is (= {:value 20 :next-node nil} (without-element-linked-list two-element-linked-list 0)))
(is (= one-element-linked-list (without-element-linked-list two-element-linked-list 1)))
(is (= {:value 10 :next-node {:value 30 :next-node nil}} (without-element-linked-list three-element-linked-list 1)))))
Review objectives
What do you think about the chosen data structure (nested dictionaries)? Would there be a way to implement this in Clojure, in a more efficient way?
Is there a way to rewrite
add-to-linked-list
(or maybecreate-linked-list
) so that it is not necessary to check the specific case for empty list, when adding a new element?Is it possible to make
without-element-linked-list
less complicated?Are there any places where good Clojure practices could be improved?
Can you think of any (edge) cases not covered by the unit tests?
GitHub
The source for this question is available here.