Реализация связанных списков в Clojure


Фон

Связанные списки являются известные структуры данных, так что я не тратить слишком много деталей на них. Достаточно сказать, что связанный список состоит из "клеток". Каждая ячейка содержит какую-то ценность и ссылку на следующую ячейку (кроме последнего, который содержит пустую ссылку).

Я реализовал связанный список в Clojure в качестве упражнения.

Код

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

Тесты

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

Цели обзора

  • Что вы думаете о выбранной структуры данных (вложенные словари)? Можно ли реализовать это в Clojure, в более эффективный способ?

  • Есть ли способ, чтобы переписать add-to-linked-list (или, может быть, create-linked-list) Так что не надо проверять конкретный случай для пустой список, при добавлении нового элемента?

  • Это можно сделать without-element-linked-list менее сложным?

  • Есть ли места, где хорошие практики в Clojure может быть улучшено?

  • Вы можете придумать любой (край) случаях, не предусмотренных модульные тесты?

На GitHub

Источник на этот вопрос доступен здесь.



243
2
задан 12 марта 2018 в 06:03 Источник Поделиться
Комментарии