Doubly-linked list/Traversal

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:

Uses the print() function from Rhino or SpiderMonkey.

Haskell

<lang haskell> main = print . traverse True $ create [10,20,30,40]

data DList a = Leaf | Node (DList a) a (DList a)

create = worker Leaf

   where worker _    []     = Leaf
         worker prev (x:xs) = current
             where current = Node prev x next
                   next = worker current xs

traverse _ Leaf = [] traverse True (Node l v Leaf) = v : v : traverse False l traverse dir (Node l v r) = v : traverse dir (if dir then r else l) </lang>

Oz

Warning: Highly unidiomatic code. (Use built-in lists instead.) <lang oz>declare

 proc {Walk Node Action}
    case Node of nil then skip
    [] node(value:V next:N ...) then

{Action V} {Walk @N Action}

    end
 end

 proc {WalkBackwards Node Action}
    Tail = {GetLast Node}
    proc {Loop N}

case N of nil then skip [] node(value:V prev:P ...) then {Action V} {Loop @P} end

    end
 in
    {Loop Tail}
 end

 fun {GetLast Node}
    case @(Node.next) of nil then Node
    [] NextNode=node(...) then {GetLast NextNode}
    end
 end
 
 fun {CreateNewNode Value}
    node(prev:{NewCell nil}
         next:{NewCell nil}
         value:Value)
 end

 proc {InsertAfter Node NewNode}
    Next = Node.next
 in
    (NewNode.next) := @Next
    (NewNode.prev) := Node
    case @Next of nil then skip
    [] node(prev:NextPrev ...) then
       NextPrev := NewNode
    end
    Next := NewNode
 end

 A = {CreateNewNode a}
 B = {CreateNewNode b}
 C = {CreateNewNode c}

in

 {InsertAfter A B}
 {InsertAfter A C}
 {Walk A Show}
 {WalkBackwards A Show}</lang>

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>

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.

Doubly-linked list/Traversal

C

JavaScript

Haskell

Oz

PL/I

Ruby

Tcl

Python