Doubly-linked list/Definition: Difference between revisions

Content added Content deleted
(Added C++ solution)
Line 1,489: Line 1,489:


<lang oforth>Object Class new: DNode(value, mutable prev, mutable next)
<lang oforth>Object Class new: DNode(value, mutable prev, mutable next)

DNode method: initialize { := value := prev := next }
DNode method: initialize := next := prev := value ;
DNode method: value { @value }
DNode method: value @value ;
DNode method: prev { @prev }
DNode method: prev @prev ;
DNode method: next { @next }
DNode method: next @next ;
DNode method: setPrev { := prev }
DNode method: setPrev := prev ;
DNode method: setNext { := next }
DNode method: setNext := next ;
DNode method: << { @value << }
DNode method: << @value << ;

DNode method: insertAfter(node)
DNode method: insertAfter(node)
{
| n |
node setPrev(self)
node setPrev(self)
node setNext(@next)
node setNext(@next)
@next ifNotNull: [ @next setPrev(node) ]
@next ifNotNull: [ @next setPrev(node) ]
node := next
node := next ;
}

// Double linked list definition
// Double linked list definition
Collection Class new: DList(mutable head, mutable tail)
Collection Class new: DList(mutable head, mutable tail)
DList method: head { @head }
DList method: head @head ;
DList method: tail { @tail }
DList method: tail @tail ;

DList method: insertFront(v)
DList method: insertFront(v)
{
| p |
| p |
@head ->p
@head ->p
DNode new(v, null, p) := head
DNode new(v, null, p) := head
p ifNotNull: [ p setPrev(@head) ]
p ifNotNull: [ p setPrev(@head) ]
@tail ifNull: [ @head := tail ]
@tail ifNull: [ @head := tail ] ;
}

DList method: insertBack(v)
DList method: insertBack(v)
{
| n |
| n |
@tail ->n
@tail ->n
DNode new(v, n, null) := tail
DNode new(v, n, null) := tail
n ifNotNull: [ n setNext(@tail) ]
n ifNotNull: [ n setNext(@tail) ]
@head ifNull: [ @tail := head ]
@head ifNull: [ @tail := head ] ;
}

DList method: forEachNext
DList method: forEachNext
{
dup ifNull: [ drop @head ifNull: [ false ] else: [ @head @head true] return ]
dup ifNull: [ drop @head ifNull: [ false ] else: [ @head @head true] return ]
next dup ifNull: [ drop false ] else: [ dup true ]
next dup ifNull: [ drop false ] else: [ dup true ] ;
}

DList method: forEachPrev
DList method: forEachPrev
{
dup ifNull: [ drop @tail ifNull: [ false ] else: [ @tail @tail true] return ]
dup ifNull: [ drop @tail ifNull: [ false ] else: [ @tail @tail true] return ]
prev dup ifNull: [ drop false ] else: [ dup true ]
prev dup ifNull: [ drop false ] else: [ dup true ] ;
}

: test // ( -- aDList )
: test // ( -- aDList )
{
| dl dn |
| dl dn |
DList new ->dl
DList new ->dl
Line 1,550: Line 1,537:
dl insertBack("B")
dl insertBack("B")
dl head insertAfter(DNode new("C", null , null))
dl head insertAfter(DNode new("C", null , null))
dl
dl ;</lang>
}

</lang>


{{out}}
{{out}}
Retrieved from "https://rosettacode.org/wiki/Doubly-linked_list/Definition"