Rosetta Code

Doubly-linked list/Definition: Difference between revisions

Page Discussion

Doubly-linked list/Definition (view source)

Revision as of 19:29, 8 August 2009

873 bytes added ,  14 years ago
Previous implementation was O(n) in time for tail insertion.
(Common Lisp solution)
(Previous implementation was O(n) in time for tail insertion.)
Line 400:
=={{header|Common Lisp}}==
 
<lang lisp>(defstruct (nodedlist (:constructorhead make-node (element &key prev next))tail)
(defstruct dlink content prev next)
(element nil :type t)
(prev nil :type (or null node))
(next nil :type (or null node)))
 
(defun insert-headbetween (elementdlist listbefore after data)
"Insert a fresh link containing DATA after existing link BEFORE if not nil and before existing link AFTER if not nil"
"Returns the new head of the list."▼
(let ((new-link (make-nodedlink :content data :prev elementbefore :next listafter)))
(setfif (node-prevnull list) new))before)
(setf (dlist-head dlist) new-link)
(setf (nodedlink-next nodebefore) new)-link))▼
(unlessif (null nextafter)▼
(setf (dlist-tail dlist) new-link)
(setf (nodedlink-prev nextafter) new-link))▼
new-link))
 
(defun tailinsert-before (listdlist dlink data)
"Insert a fresh link containing DATA before existing link DLINK"
"Return the last node of the list."
(insert-between dlist (dlink-prev dlink) dlink data))
(do ((tail list (node-next tail)))
((null (node-next tail)) tail)))
 
(defun insert-middleafter (elementdlist nodedlink data)
"Insert a fresh link containing DATA after existing link DLINK"
"Returns the newly created node."
(let*insert-between ((nextdlist dlink (nodedlink-next nodedlink) data))
(new (make-node element :prev node :next next)))
▲ (unless (null next)
▲ (setf (node-prev next) new))
▲ (setf (node-next node) new)))
 
(defun insert-tailhead (elementdlist listdata)
"ReturnsInsert a fresh link containing DATA at the head of the list.DLIST"
(insert-middlebetween elementdlist nil (taildlist-head dlist) listdata))
list)
 
(defun listinsert-elementstail (listdlist &aux (elements '())data)
"ReturnsInsert a normalfresh Lisplink listcontaining ofDATA at the elementstail of list.DLIST"
(insert-between dlist (dlist-tail dlist) nil data))
(do ((node list (node-next node)))
 
((null node) (nreverse elements))
(defun remove-link (dlist dlink)
(push (node-element node) elements)))</lang>
"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 new headelements of theDLIST as a list."
(labels ((extract-values (dlink acc)
(if (null dlink)
acc
(extract-values (dlink-next dlink) (cons (dlink-content dlink) acc)))))
(reverse (extract-values (dlist-head dlist) nil))))</lang>
 
The following produces <code>(1 2 3 4)</code>.
 
<lang lisp>(let* ((dldlist (make-node 3dlist)))
(dl (insert-head dlist 1 dl))
(dl (insert-tail dlist 4 dl)))
(insert-middleafter 2dlist dl(dlist-head dlist) 2)
(let* ((next-to-last (insert-before dlist (dlist-tail dlist) 3))
(list-elements dl))</lang>▼
(bad-link (insert-before dlist next-to-last 42)))
(remove-link dlist bad-link))
▲ (listprint (dlist-elements dldlist)))</lang>
 
=={{header|Visual Basic .NET}}==
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/94615"