Doubly-linked list/Traversal: Difference between revisions

Traverse from the beginning of a [[Doubly-linked list/Definition|doubly-linked list]] to the end, and from the end to the beginning.

 

{{Template:See also lists}}

=={{header|Ada}}==

{{works with|Ada 2005}}

with Ada.Text_IO;

 

My_List.Reverse_Iterate (Print'Access);

Ada.Text_IO.New_Line;

 

=={{header|ALGOL 68}}==

MODE NODE = STRUCT(

DATA data,

REF NODE travel := head OF list;

WHILE travel ISNT REF NODE(NIL) DO

travel := next OF travel

OD

travel := prev OF travel

OD

 

 

MODE EMPLOYEE = STRUCT(STRING name, INT salary, INT years);

PURGE list;

forward traversal(list)

{{out}}

<pre>

YEARS : +40

</pre>

 

=={{header|AutoHotkey}}==

see [[Doubly-linked list/AutoHotkey]]

 

=={{header|BBC BASIC}}==

{{works with|BBC BASIC for Windows}}

DIM a{} = node{}, b{} = node{}, c{} = node{}

here.pNext% = new{}

ENDPROC

Output:

<pre>Traverse forwards:

 

=={{header|C}}==

#include <stdio.h>

#include <stdlib.h>

//uhhh-- delete list??

return 0;

 

using System.Collections.Generic;

 

}

}

Output:

<pre>

e

h</pre>

 

=={{header|Clojure}}==

Given the definition in [[../Definition#Clojure]],

;=> #'user/dl

 

;=> #:double_list.Node{:prev #<Object...>, :next #<Object...>, :data :c, :key #<Object...>}

;=> #:double_list.Node{:prev #<Object...>, :next #<Object...>, :data :b, :key #<Object...>}

 

=={{header|D}}==

===Standard Doubly-linked List===

import std.stdio, std.container, std.range;

 

dll[].writeln;

dll[].retro.writeln;

{{out}}

<pre>ABCD

===User-defined Doubly-linked list===

Same output.

T data;

typeof(this)* prev, next;

p.data.write;

writeln;

 

=={{header|Delphi}}==

 

type

while not (pList^.prev = NIL) do pList := pList^.prev ;

 

 

=={{header|E}}==

{{incorrect|E|Doesn't work, probably due to a bug in the list definition: runs over the beginning of the list. Needs debugging.}}

Given the definition in [[../Definition#E]],

var node := list.atFirst()

while (true) {

}

}

 

# value: <>

 

3

2

 

=={{header|Erlang}}==

The task in [[Doubly-linked_list/Element_insertion]] uses traversal as proof that the insertion worked.

 

=={{header|Fortran}}==

see [[Doubly-linked list/Definition#Fortran]]

 

=={{header|Go}}==

 

Also note that there is a doubly linked list in the Go standard library in package container/list.

 

import "fmt"

}

fmt.Println("")

Output:

<pre>

From tail: B C A

</pre>

 

=={{header|Haskell}}==

 

data DList a = Leaf | Node { prev::(DList a), elt::a, next::(DList a) }

traverse _ Leaf = []

traverse True (Node l v Leaf) = v : v : traverse False l

 

==Icon and {{header|Unicon}}==

Uses Unicon classes.

 

# insert given node after this one, removing its existing connections

every (node := l2.traverse_backwards ()) do

write (node.value)

 

Output:

 

=={{header|J}}==

work=. result=. conew 'DoublyLinkedListHead'

current=. y

end.

result

 

This traverses a doubly linked list, applying the verb u to the data in each list element and creates a new doubly linked list containing the results. A reference to the new doubly linked list is returned.

 

=={{header|Java}}==

 

 

 

=={{header|JavaScript}}==

See [[Doubly-Linked List (element)#JavaScript]]. The <code>traverse()</code> and <code>print()</code> functions have been inherited from [[Singly-Linked List (traversal)#JavaScript]].

var tail;

this.traverse(function(node){tail = node;});

var head = createDoublyLinkedListFromArray([10,20,30,40]);

head.print();

 

outputs:

10</pre>

Uses the <code>print()</code> function from [[Rhino]] or [[SpiderMonkey]].

 

=={{header|Liberty BASIC}}==

struct block,nxt as ulong,prev as ulong,nm as char[20],age as long'Our structure of the blocks in our list.

 

calldll #kernel32,"HeapDestroy",hHeap as ulong,ret as void

end sub

 

=={{header|Nim}}==

List[T] = object

head, tail: Node[T]

 

for i in l.traverseBackward():

 

=={{header|Objeck}}==

class Traverse {

function : Main(args : String[]) ~ Nil {

}

}

 

<pre>

5

100

</pre>

 

=={{header|Oz}}==

Warning: Highly unidiomatic code. (Use built-in lists instead.)

proc {Walk Node Action}

case Node of nil then skip

{InsertAfter A C}

{Walk A Show}

 

=={{header|Pascal}}==

See [[Doubly-linked_list/Traversal#Delphi | Delphi]]

 

=={{header|PicoLisp}}==

(de 2print (DLst)

(for (L (car DLst) L (cddr L))

(for (L (cdr DLst) L (cadr L))

(printsp (car L)) )

Output for the example data produced in

[[Doubly-linked list/Definition#PicoLisp]] and

 

=={{header|PL/I}}==

doubly_linked_list: proc options (main);

 

t => back_pointer = tail; /* Point the new tail back to the old */

/* tail. */

tail => fwd_pointer = bind(:node, null:);

/* Set the tail link to NULL */

t = t => back_pointer;

end;

Output:

<pre>

 

=={{header|PureBasic}}==

 

;Set up a randomly long linked list in the range 25-125 elements

Repeat

Debug MyData() ; Present the value in the current cell

 

=={{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.

def __init__(self, data, next=None, prev=None):

self.data = data

while node != None:

print(node.data)

 

This produces the desired output. However, I expect most python programmers would do the following instead:

 

for i in l:

print(i)

for i in reversed(l): # reversed produces an iterator, so only O(1) memory is used

 

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.

These functions traverse the list in the two directions.

They create a native (singly-linked) list by adding to the front, so they traverse in the reverse order from the desired result order.

(let loop ([elements '()] [dlink (dlist-tail dlist)])

(if dlink

(if dlink

(loop (cons (dlink-content dlink) elements) (dlink-next dlink))

 

=={{header|REXX}}==

REXX doesn't have linked lists, as there are no pointers (or handles).

However, linked lists can be simulated with lists in REXX.

/*┌────────────────────────────────────────────────────────────────────┐

┌─┘ Functions of the List Manager └─┐

$.@=_

call @adjust

'''output'''

<pre style="height:30ex;overflow:scroll">

─── showing list ───

Oy! Was it a black cat I saw there, in the shadows, stalking its prey (and next

</pre>

 

=={{header|Ruby}}==

def get_tail

# parent class (ListNode) includes Enumerable, so the find method is available to us

head = DListNode.from_array([:a, :b, :c])

head.each {|node| p node.value}

 

=={{header|Salmon}}==

Without explicit type information:

{

variable next,

follow.data!

step

 

With explicit type information:

{

variable next: item | {null},

follow.data!

step

 

Both of these produce the following output:

a

</pre>

 

=={{header|Tcl}}==

Assuming that the <code>List</code> class from [[Doubly-Linked List (element)#Tcl|this other task]] is already present...

oo::define List {

method foreach {varName script} {

$first foreach char { puts $char }

puts "Backward..."

Which produces this output:

<pre>Forward...

b

a</pre>

 

{{omit from|ACL2}}