Jump to content

Doubly-linked list/Definition: Difference between revisions

Doubly-linked list/Definition (view source)

Revision as of 19:36, 8 August 2009

105 bytes added ,  14 years ago
m
Changed htabs to 8 spaces, indentation was screwed up.
(Previous implementation was O(n) in time for tail insertion.)
m (Changed htabs to 8 spaces, indentation was screwed up.)
Line 407:
(let ((new-link (make-dlink :content data :prev before :next after)))
(if (null before)
(setf (dlist-head dlist) new-link)
(setf (dlink-next before) new-link))
(if (null after)
(setf (dlist-tail dlist) new-link)
(setf (dlink-prev after) new-link))
new-link))
 
Line 433:
"Remove link DLINK from DLIST and return its content"
(let ((before (dlink-prev dlink))
(after (dlink-next dlink)))
(if (null before)
(setf (dlist-head dlist) after)
(setf (dlink-next before) after))
(if (null after)
(setf (dlist-tail dlist) before)
(setf (dlink-prev after) before))))
 
(defun dlist-elements (dlist)
"Returns the elements of DLIST as a list"
(labels ((extract-values (dlink acc)
(if (null dlink)
acc
acc
(extract-values (dlink-next dlink) (cons (dlink-content dlink) acc)))))
(reverse (extract-values (dlist-head dlist) nil))))</lang>
 
Line 456:
(insert-after dlist (dlist-head dlist) 2)
(let* ((next-to-last (insert-before dlist (dlist-tail dlist) 3))
(bad-link (insert-before dlist next-to-last 42)))
(remove-link dlist bad-link))
(print (dlist-elements dlist)))</lang>
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/94616"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information