The DC-DLIST package provides a simple, doubly-linked list via the
dlist and dlist-node classes. Here are some examples of how to use
dlists:
(let ((dlist (make-instance 'dlist)))
(push-tail dlist 3)
(push-tail dlist 4)
(push-tail dlist 5)
(push-head dlist 2)
(push-head dlist 1)
(push-head dlist 0)
(list :list (to-list dlist)
:head (peek-head dlist)
:tail (peek-tail dlist)
:len (len dlist)))
;; (:list (0 1 2 3 4 5) :head 0 :tail 5 :len 6)
(let ((dlist (from-list '(1 2 3))))
(pop-head dlist)
(pop-tail dlist)
(list :list (to-list dlist)
:head (peek-head dlist)
:tail (peek-tail dlist)
:len (len dlist)))
;; (:list (2) :head 2 :tail 2 :len 1)
(let* ((dlist (from-list '(1 2 3 4)))
(node (node-at dlist 1)))
(delete-node-at dlist 2) ;; delete the node with value 3
(delete-node dlist node) ;; deletet he node with value 2
(list :list (to-list dlist)
:head (peek-head dlist)
:tail (peek-tail dlist)
:len (len dlist)))
;; (:list (1 4) :head 1 :tail 4 :len 2)
(at dlist index)
Returns the value associated with the node at the given index.
;; This returns 22
(let ((dlist (from-list '(0 11 22 33 44))))
(at dlist 2))An object of type dlist.
An integer that is a zero-based index to the node in dlist.
If the index you provide is outside of the range of the dlist, this function
returns the value nil. If the dlist object is not a dlist or if the index
is not a number, the call generates an error. If the index is a number that
can’t evaluate to an integer, then the function returns nil.
(contains-node dlist dlist-node)
Returns true if the given dlist-node object exists in the given dlist object.
;; This returns (t nil)
(let* ((dlist (from-list '(0 11 22 33 44)))
(existing-node (find-first-node dlist (lambda (v) (= v 22))))
(non-existing-node (make-instance 'dlist-node :value 123)))
(list (contains-node dlist existing-node)
(contains-node dlist non-existing-node)))An object of type dlist.
An object of type dlist-node.
If the dlist-node object doesn’t exist among the nodes in dlist, this function
returns nil.
(copy dlist)
Returns a copy of the dlist.
;; This returns (:at-first t :then nil)
(let* ((dlist-1 (from-list '(1 2 3)))
(dlist-2 (copy dlist-1)))
(list :at-first (equal (to-list dlist-1) (to-list dlist-2))
:then (progn (pop-head dlist-1)
(equal (to-list dlist-1) (to-list dlist-2)))))An object of type dlist.
This function creates a whole new copy of the original dlist, such that if you delete a node from the original dlist, the copy is not affected. However, the function does not create deep copies of the values associated with the original nodes. If you’re values are objects, then the new list contains references to to same objects that the original list referenced.
(delete-node dlist dlist-node)
Deletes the given dlist-node from dlist and returns the value associated with the deleted node.
(let* ((dlist (from-list '(1 2 3)))
(node (node-at dlist 1))) ;; The node with the value 2
(delete-node dlist node)
(list :list (to-list dlist)))
;; (:list (1 3))An object of type dlist.
An object of type dlist-node.
If dlist-node doesn’t exist in dlist, this function deletes nothing and
returns nil.
(delete-node-at dlist index)
Deletes the node at the given index from dlist and returns value associated with the deleted node.
(let ((dlist (from-list '(1 2 3))))
(delete-node-at dlist 1)
(list :list (to-list dlist)))
;; (:list 1 3)An object of type dlist.
A zero-based index to the dlist-node object to be deleted in dlist.
If the index is out of range, this function deletes nothing and returns nil.
(find-first-node dlist comparison-function)
Finds and returns the first node in dlist where calling comparison-function
with the node’s value returns true. If no such node exists, this value returns
nil.
;; Returns 2
(let ((dlist (from-list '(1 2 3))))
(value (find-first-node dlist #'evenp)))An object of type dlist.
A function that takes a single parameter and evaluates to true when called with the value of the desired node.
This function returns a node, not a value. To obtain the value from the
node, you can use the value function.
(from-list some-list)
Returns a dlist object that contains nodes with the values in the given list.
A standard Common Lisp list containing any values.
This function creates a new dlist object, then iterates through the given list
calling the push-tail method to add each element to the dlist. The function
returns the new dlist. The list you provide can be empty, in which case this
function retruns an empty dlist, which is equivalent to calling
(make-instance 'dlist).
(insert-before-node dlist dlist-node value)
Creates a new dlist-node object using the given value and inserts that object
in the given dlist at the position immediately preceding the position of the
given dlist-node object. In other words, this function inserts a value in
front of the given dlist-node. This function returns the dlist object upon
success and nil on failure.
An object of type dlist.
An object of type dlist-node.
A value of any type. This function will wrap the value in a dlist-node object and insert the object into the give dlist.
You can get get a reference to the dlist-node object that this function
requires by calling find-first-node. Alternatively, if you can use
the insert-before-value function instead of the insert-before-node
function, as you can use a value instead of a node with the former function.
If the given dlist-node object doesn’t exist in the given dlist object,
this function makes no insertion and returns nil.
(node-at dlist index)
Retrieves the dlist-node object at the given index in the given dlist.
Returns a dlist-node object upon success, or nil if index is out of
bounds.
An object of type dlist.
An integer or a number that can evaluate to an integer. This integer is the
zero-based index of the dlist-node object you want to retrieve.
If the index is out of bounds, this function returns nil.
(peek-head dlist)
Returns the value of the first node in dlist wtihout changing dlist in any way.
An object of type dlist.
If dlist is empty, this function return nil.
(peek-tail dlist)
Returns the value of the last node in dlist without changing dlist in any way.
An object of type dlist.
If dlist is empty, this function returns nil.
(pop-head dlist)
Removes the first node from dlist and retuns the value of that node, decreasing
the length of dlist by 1.
An object of type dlist.
If dlist is empty, this function makes no changes and returns nil.
(pop-tail dlist)
Removes the last node from dlist and retuns the value of that node, decreasing
the length of dlist by 1.
An object of type dlist.
If dlist is empty, this function makes no changes and returns nil.
(push-head dlist value)
Creates a new dlist-node object using the given value and inserts the new object
at the beginning of dlist, increasing the length of dlist by 1.
An object of type dlist.
A value of any type.
(push-tail dlist value)
Creates a new dlist-node object using the given value and appends the new object
to the end of dlist, increasing the length of dlist by 1.
An object of type dlist.
A value of any type.
(to-list dlist)
Returns a regular Common Lisp list containing the values in the nodes of dlist,
in the same order as the they appear in dlist.
;; returns t
(equal (to-list (from-list '(1 2 3))) '(1 2 3))An object of type dlist.