Doubly-linked list/Traversal: Difference between revisions
(add Ruby) |
(→Tcl: Added implementation) |
||
Line 51: | Line 51: | ||
head.each {|node| p node.value} |
head.each {|node| p node.value} |
||
head.get_tail.each_previous {|node| p node.value}</lang> |
head.get_tail.each_previous {|node| p node.value}</lang> |
||
=={{header|Tcl}}== |
|||
Assuming that the <code>List</code> class from [[Doubly-Linked List (element)#Tcl|this other task]] is already present... |
|||
<lang tcl># Modify the List class to add the iterator methods |
|||
oo::define List { |
|||
method foreach {varName script} { |
|||
upvar 1 $varName v |
|||
for {set node [self]} {$node ne ""} {set node [$node next]} { |
|||
set v [$node value] |
|||
uplevel 1 $script |
|||
} |
|||
} |
|||
method revforeach {varName script} { |
|||
upvar 1 $varName v |
|||
for {set node [self]} {$node ne ""} {set node [$node previous]} { |
|||
set v [$node value] |
|||
uplevel 1 $script |
|||
} |
|||
} |
|||
} |
|||
# Demonstrating... |
|||
set first [List new a [List new b [List new c [set last [List new d]]]]] |
|||
puts "Forward..." |
|||
$first foreach char { puts $char } |
|||
puts "Backward..." |
|||
$last revforeach char { puts $char }</lang> |
|||
Which produces this output: |
|||
<pre>Forward... |
|||
a |
|||
b |
|||
c |
|||
d |
|||
Backward... |
|||
d |
|||
c |
|||
b |
|||
a</pre> |
Revision as of 21:08, 9 October 2009
You are encouraged to solve this task according to the task description, using any language you may know.
Traverse from the beginning of a doubly-linked list to the end, and from the end to the beginning.
JavaScript
See Doubly-Linked List (element)#JavaScript. The traverse()
and print()
functions have been inherited from Singly-Linked List (traversal)#JavaScript.
<lang javascript>DoublyLinkedList.prototype.getTail = function() {
var tail; this.traverse(function(node){tail = node;}); return tail;
} DoublyLinkedList.prototype.traverseBackward = function(func) {
func(this); if (this.prev() != null) this.prev().traverseBackward(func);
} DoublyLinkedList.prototype.printBackward = function() {
this.traverseBackward( function(node) {print(node.value())} );
}
var head = createDoublyLinkedListFromArray([10,20,30,40]); head.print(); head.getTail().printBackward();</lang>
outputs:
10 20 30 40 40 30 20 10
Uses the print()
function from Rhino or SpiderMonkey.
Ruby
<lang ruby>class DListNode
def get_tail tail = nil self.each {|node| tail = node} tail end
def each_previous(&b) yield self self.prev.each_previous(&b) if self.prev end
end
head = DListNode.from_array([:a, :b, :c]) head.each {|node| p node.value} head.get_tail.each_previous {|node| p node.value}</lang>
Tcl
Assuming that the List
class from this other task is already present...
<lang tcl># Modify the List class to add the iterator methods
oo::define List {
method foreach {varName script} { upvar 1 $varName v for {set node [self]} {$node ne ""} {set node [$node next]} { set v [$node value] uplevel 1 $script } } method revforeach {varName script} { upvar 1 $varName v for {set node [self]} {$node ne ""} {set node [$node previous]} { set v [$node value] uplevel 1 $script } }
}
- Demonstrating...
set first [List new a [List new b [List new c [set last [List new d]]]]] puts "Forward..." $first foreach char { puts $char } puts "Backward..." $last revforeach char { puts $char }</lang> Which produces this output:
Forward... a b c d Backward... d c b a