Doubly-linked list/Traversal: Difference between revisions
m (→{{header|Ruby}}: simpler get_tail method) |
(Added a python solution) |
||
Line 88: | Line 88: | ||
b |
b |
||
a</pre> |
a</pre> |
||
=={{header|Python}}== |
|||
This provides two solutions. One that explicitly builds a linked list and traverses it two ways, and another which uses pythons combined list/array class. Unless two lists explicitly needed to be spliced together in O(1) time, or a double linked list was needed for some other reason, most python programmers would probably use the second solution. |
|||
<lang python> |
|||
class List: |
|||
def __init__(self, data, next=None, prev=None): |
|||
self.data = data |
|||
self.next = next |
|||
self.prev = prev |
|||
def append(self, data): |
|||
if self.next == None: |
|||
self.next = List(data, None, self) |
|||
return self.next |
|||
else: |
|||
return self.next.append(data) |
|||
# Build the list |
|||
tail = head = List(10) |
|||
for i in [ 20, 30, 40 ]: |
|||
tail = tail.append(i) |
|||
# Traverse forwards |
|||
node = head |
|||
while node != None: |
|||
print(node.data) |
|||
node = node.next |
|||
# Traverse Backwards |
|||
node = tail |
|||
while node != None: |
|||
print(node.data) |
|||
node = node.prev |
|||
</lang> |
|||
This produces the desired output. However, I expect most python programmers would do the following instead: |
|||
<lang python> |
|||
l = [ 10, 20, 30, 40 ] |
|||
for i in l: |
|||
print(i) |
|||
for i in reversed(l): # reversed produces an iterator, so only O(1) memory is used |
|||
print(i) |
|||
</lang> |
|||
Double-ended queues in python are provided by the collections.deque class and the array/list type can perform all the operations of a C++ vector (and more), so building one's own doubly-linked list would be restricted to very specialized situations. |
Revision as of 19:44, 6 December 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 # parent class (ListNode) includes Enumerable, so the find method is available to us self.find {|node| node.succ.nil?} 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
Python
This provides two solutions. One that explicitly builds a linked list and traverses it two ways, and another which uses pythons combined list/array class. Unless two lists explicitly needed to be spliced together in O(1) time, or a double linked list was needed for some other reason, most python programmers would probably use the second solution.
<lang python> class List:
def __init__(self, data, next=None, prev=None): self.data = data self.next = next self.prev = prev
def append(self, data): if self.next == None: self.next = List(data, None, self) return self.next else: return self.next.append(data)
- Build the list
tail = head = List(10) for i in [ 20, 30, 40 ]:
tail = tail.append(i)
- Traverse forwards
node = head while node != None:
print(node.data) node = node.next
- Traverse Backwards
node = tail while node != None:
print(node.data) node = node.prev
</lang>
This produces the desired output. However, I expect most python programmers would do the following instead:
<lang python> l = [ 10, 20, 30, 40 ] for i in l:
print(i)
for i in reversed(l): # reversed produces an iterator, so only O(1) memory is used
print(i)
</lang>
Double-ended queues in python are provided by the collections.deque class and the array/list type can perform all the operations of a C++ vector (and more), so building one's own doubly-linked list would be restricted to very specialized situations.