3
\$\begingroup\$

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 maybe create-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.

\$\endgroup\$

1 Answer 1

4
\$\begingroup\$

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?

Conceptually it works. I wouldn't use plain maps here though. You know every node in the list should contain only the keys :value and :next-node. In a case like this, I'd use a record instead:

(defrecord Node [value, next-node])

(defn new-node [value]
  (->Node value nil))

This comes with slight performance benefits, and just generally makes more sense. If you needed to create a object in Java, and you knew it only needed two specific fields, would you represent that object as a Map, or as a class? I would say a class. If you don't need an object with a variable number of fields, don't represent it as something that has a variable number of fields. Yes, records are basically just maps, but I would consider them more appropriate here because it's explicit what keys they should contain.

This raises the problem of what an empty list would be. nil works here, and should go well with recursion (more on that in a bit).


Is there a way to rewrite add-to-linked-list (or maybe create-linked-list) so that it is not necessary to check the specific case for empty list, when adding a new element?

You'll always need to handle the base-case check in some way, so I can't see a way of taking it out completely. You could use multimethods to "pattern match" like you'd do in Haskell, but that would add a lot of bulk and not a lot of clarity. The entire function can be significantly neatened up through other means though:

(defn add-to-linked-list2 [node new-value]
  ; An empty list is now nil, which is falsey
  (if node
    ; Using update frees us from needing to destructure the node
    (update node :next-node #(add-to-linked-list2 % new-value))
    ; This also be written as (update node :next-node add-to-linked-list2 new-value)
    ;  thanks to update's overloads, which is even nicer

    (new-node new-value)))

The major changes:

  • Because an empty list is now nil, you don't have to worry about an empty list being {}, but an empty :next-node being nil. This greatly simplifies the recursing line.

  • Instead of checking if the list is equal to an empty map, we can just check its truthiness directly.

  • I'm using my new-node here. I know a new node will have a next-node of nil, so I might as well remove that fact from this code and let a separate function handle that.

Of course, the major problem with both our implementations is that they can't be written using recur, meaning they're susceptible to Stack Overflows. I tried writing a solution in terms of loop, but it got super messy, and really, the use case doesn't make sense anyway. It's unreasonable to iterate the entire list just to append an element anyway. If you're going to use a linked list, just prepend at the head which entirely does away with the need for iteration on addition. Look at Haskell and how well its standard linked list goes with recursion. Every operation is done at the head, and that simplifies (and speeds up) additions.


Is it possible to make without-element-linked-list less complicated?

Firstly, your loop accumulators are written in a super confusing way. At least separate each binding with commas, or ideally, place each on its own line:

(loop [{:keys [value next-node] :as act-node} linked-list
       counter 0
       linked-list-accum (create-linked-list)]

Going against what I said earlier about using unoptimized recursion, the best method I could find is unoptimized:

(defn without-element-linked-list2 [{:keys [next-node] :as node} n]
  (cond
    ; We hit the end of the list without finding it. Throw an error?
    ;  Apparently n was out of bounds.
    (nil? node) nil

    ; We found the element to delete. Just "skip" over it.
    (zero? n) next-node

    ; Very similar to the add method. We're part way through the list, so keep iterating.
    :else (update node :next-node without-element-linked-list2 (dec n))))

I decided to just decrement n as we iterate to avoid a second counter.

I understand that you're probably doing this purely as an exercise, but the fact that getting an optimized solution is so difficult should be a sign that's somethings wrong. In the ~2 years that I've been writing Clojure, I've never written my own basic structure. In most other languages, it's a very common exercise. In Clojure though, the lower level implementation of the structures used are best tucked away somewhere, and it's much more common to just use the basic structures of the language. If you need linked list behavior, use plain lists. If you need array behavior, use a vector. Sometimes a more custom structure is needed, but tend to reach for native structures first, since they're almost always sufficient, and already have an extensive API.


Are there any places where good Clojure practices could be improved?

In contains-linked-list?, you make good use of or. It can still be improved on though:

(defn contains-linked-list?2 [{:keys [value next-node] :as node} query-value]
  (when node
    (or (= value query-value) (recur next-node query-value))))

when is great. It neatens up code nicely. If you ever find yourself conditionally returning a falsey value, consider just negating the condition, and using when to implicitly return nil. Or, instead of negating the condition like I did here, you could use when-not.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.