Anonymous user
Singly-linked list/Reversal: Difference between revisions
Added Common Lisp with various examples
m (Fixed C header) |
imported>StraightDoubt (Added Common Lisp with various examples) |
||
Line 71:
}
</syntaxhighlight>
=={{header|Common Lisp}}==
Common Lisp has functions for reversing a list in its standard library. The destructive version is called nreverse, and the version that makes a reversed copy of the list is called reverse. However, it's simple to make your own versions of these functions.
A non-destructive reversal using dolist:
<syntaxhighlight lang="Lisp">
(defun my-reverse (list)
(let ((result nil))
(dolist (obj list)
(push obj result))
result))
</syntaxhighlight>
A non-destructive reversal using reduce:
<syntaxhighlight lang="Lisp">
(defun my-reverse (list)
(reduce #'(lambda (acc x)
(cons x acc))
list
:initial-value NIL))
</syntaxhighlight>
A destructive reversal using tail-recursion. It returns the new beginning of the reversed list, or the empty list when passed the empty list.
<syntaxhighlight lang="Lisp">
(defun my-nreverse (list)
(labels ((iter (prev cur)
(if (endp cur)
prev
(let ((next (cdr cur)))
(setf (cdr cur) prev)
(iter cur next)))))
(iter nil list)))
</syntaxhighlight>
Two versions using explicit iteration. They both do exactly the same thing, just one uses the DO macro and the other uses the LOOP macro.
<syntaxhighlight lang="Lisp">
(defun my-nreverse (list)
;; (cdr nil) is nil in Common Lisp, so (cdr list) is always safe.
(do ((next (cdr list) (cdr next))
(cur list next)
(prev nil cur))
((endp cur) prev)
(setf (cdr cur) prev)))
</syntaxhighlight>
<syntaxhighlight lang="Lisp">
(defun my-nreverse (list)
(loop for next = (cdr list) then (cdr next)
and cur = list then next
and prev = nil then cur
until (endp cur)
do (setf (cdr cur) prev)
finally (return prev)))
</syntaxhighlight>
| |||