Define the data structure for a complete Doubly Linked List.

 The structure should support adding elements to the head, tail and middle of the list. 
 The structure should not allow circular loops


See also

 Array
 Associative array: Creation, Iteration
 Collections
 Compound data type
 Doubly-linked list: Definition, Element definition, Element insertion, List Traversal, Element Removal
 Linked list
 Queue: Definition, Usage
 Set
 Singly-linked list: Element definition, Element insertion, List Traversal, Element Removal
 Stack


(ns double-list)
 
(defprotocol PDoubleList
  (get-head [this])
  (add-head [this x])
  (get-tail [this])
  (add-tail [this x])
  (remove-node [this node])
  (add-before [this node x])
  (add-after [this node x])
  (get-nth [this n]))
 
(defrecord Node [prev next data])
 
(defn make-node
  "Create an internal or finalized node"
  ([prev next data] (Node. prev next data))
  ([m key] (when-let [node (get m key)]
            (assoc node :m m :key key))))
 
(defn get-next [node] (make-node (:m node) (:next node)))
(defn get-prev [node] (make-node (:m node) (:prev node)))
 
(defn- seq* [m start next]
  (seq
   (for [x (iterate #(get m (next %)) (get m start))
         :while x]
     (:data x))))
 
(defmacro when->
  ([x pred form] `(let [x# ~x] (if ~pred (-> x# ~form) x#)))
  ([x pred form & more] `(when-> (when-> ~x ~pred ~form) ~@more)))
 
(declare get-nth-key)
 
(deftype DoubleList [m head tail]
  Object
    (equals [this x]
      (and (instance? DoubleList x)
           (= m (.m ^DoubleList x))))
    (hashCode [this] (hash (or this ())))
  clojure.lang.Sequential
  clojure.lang.Counted
    (count [_] (count m))
  clojure.lang.Seqable
    (seq [_] (seq* m head :next))
  clojure.lang.Reversible
    (rseq [_] (seq* m tail :prev))
  clojure.lang.IPersistentCollection
    (empty [_] (DoubleList. (empty m) nil nil))
    (equiv [this x]
      (and (sequential? x)
           (= (seq x) (seq this))))
    (cons [this x] (.add-tail this x))
  PDoubleList
    (get-head [_] (make-node m head))
    (add-head [this x]
      (let [new-key (Object.)
            m (when-> (assoc m new-key (make-node nil head x))
                head (assoc-in [head :prev] new-key))
            tail (if tail tail new-key)]
        (DoubleList. m new-key tail)))
    (get-tail [_] (make-node m tail))
    (add-tail [this x]
      (if-let [tail (.get-tail this)]
        (.add-after this tail x)
        (.add-head this x)))
    (remove-node [this node]
      (if (get m (:key node))
        (let [{:keys [prev next key]} node
              head (if prev head next)
              tail (if next tail prev)
              m (when-> (dissoc m key)
                  prev (assoc-in [prev :next] next)
                  next (assoc-in [next :prev] prev))]
          (DoubleList. m head tail))
        this))
    (add-after [this node x]
      (if (get m (:key node))
        (let [{:keys [prev next key]} node
              new-key (Object.)
              m (when-> (-> (assoc m new-key  (make-node key next x))
                            (assoc-in , [key :next] new-key))
                  next (assoc-in [next :prev] new-key))
              tail (if next tail new-key)]
          (DoubleList. m head tail))
        this))
    (add-before [this node x]
      (if (:prev node)
        (.add-after this (get-prev node) x)
        (.add-head this x)))
    (get-nth [this n] (make-node m (get-nth-key this n))))
 
(defn get-nth-key [^DoubleList this n]
  (if (< -1 n (.count this))
    (let [[start next n] (if (< n (/ (.count this) 2))
                           [(.head this) :next n]
                           [(.tail this) :prev (- (.count this) n 1)])]
      (nth (iterate #(get-in (.m this) [% next]) start) n))
    (throw (IndexOutOfBoundsException.))))
 
(defn double-list
  ([] (DoubleList. nil nil nil))
  ([coll] (into (double-list) coll)))
 
(defmethod print-method DoubleList [dl w]
  (print-method (interpose '<-> (seq dl)) w))
 
(defmethod print-method Node [n w]
  (print-method (symbol "#:double_list.Node") w)
  (print-method (into {} (dissoc n :m)) w))