Doubly-linked list/Traversal: Difference between revisions

{{Template:See also lists}}

<br><br>

 

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

travel := prev OF travel

OD

 

 

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

PURGE list;

forward traversal(list)

{{out}}

<pre>

=={{header|ALGOL W}}==

Using the element type and insertion routine from the Doubly Linked List/Eleemnt Insertion task.

% record type to hold an element of a doubly linked list of integers %

record DListIElement ( reference(DListIElement) prev

end while_e_ne_null

end

{{out}}

<pre>

</pre>

 

=={{header|ARM Assembly}}==

{{works with|as|Raspberry Pi}}

/* ARM assembly Raspberry PI */

/* program transDblList.s */

.include "../affichage.inc"

 

 

=={{header|AutoHotkey}}==

 

=={{header|Axe}}==

LINK(L₁+10,2)→B

LINK(L₁+50,3)→C

Disp VALUE(I)▶Dec,i

PREV(I)→I

 

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

=={{header|C++}}==

{{works with|C++11}}

#include <list>

 

std::cout << i << ' ';

std::cout << '\n';

{{out}}

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

 

open System.Collections.Generic

 

printfn ""

traverseBackward cs

{{out}}

<pre>

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

 

=={{header|Groovy}}==

static void main(args) {

def linkedList = (1..9).collect() as LinkedList

}

}

 

{{out}}

 

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

{{works with|Java|8 or higher}}

 

package com.rosettacode;

 

doubleLinkedList.descendingIterator().forEachRemaining(System.out::print);

}

 

{{out}}

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

 

=={{header|Julia}}==

value::T

pred::Union{DLNode{T}, Nothing}

print("From beginning to end: "); printconnected(node1)

print("From end to beginning: "); printconnected(node1, fromtail = true)

From beginning to end: 1 -> 2 -> 3

From end to beginning: 3 -> 2 -> 1

=={{header|Kotlin}}==

To complete this task, we just need to add a couple of traversal functions to the class we defined in the [[Doubly-linked list/Definition]] task:

 

class LinkedList<E> {

println("First to last : ${ll.firstToLast()}")

println("Last to first : ${ll.lastToFirst()}")

 

{{out}}

=={{header|Lua}}==

Begin with this: [[Doubly-linked_list/Definition#Lua]], then extend with this:

-- TRAVERSAL:

--------------

for i = 1, 5 do list:insertTail(i) end

io.write("Forward: ") for node in list:iterateForward() do io.write(node.data..",") end print()

{{out}}

<pre>Forward: 1,2,3,4,5,

 

=={{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|Oberon-2}}==

MODULE Collections;

IMPORT Box;

 

END Collections.

 

=={{header|Objeck}}==

class Traverse {

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

}

}

 

<pre>

Defining #forEachNext and #forEachPrev allow to traverse this double linked list using #forEach: and #revEach: syntax

 

dup ifNull: [ drop @head ifNull: [ false ] else: [ @head @head true] return ]

next dup ifNull: [ drop false ] else: [ dup true ] ;

 

"\nTraversal (end to beginning) : " println

 

{{out}}

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

 

=={{header|Phix}}==

<span style="color: #008080;">enum</span> <span style="color: #000000;">NEXT</span><span style="color: #0000FF;">,</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">,</span><span style="color: #000000;">DATA</span>

<span style="color: #008080;">constant</span> <span style="color: #000000;">empty_dll</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}}</span>

<span style="color: #0000FF;">?</span><span style="color: #008000;">"=="</span>

<span style="color: #000000;">show</span><span style="color: #0000FF;">(</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">)</span>

{{out}}

<pre>

 

=={{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 = 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|Raku}}==

 

Since the list routines are supplied by the generic roles defined in [[Doubly-linked_list/Definition#Raku]], it suffices to say:

These automatically return just the payloads, hiding the elements containing the forward and backward pointers.

 

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">

 

=={{header|Ring}}==

# Project : Doubly-linked list/Traversal

 

see travback

see nl

Output:

<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:

 

=={{header|Scala}}==

 

object DoublyLinkedListTraversal extends App {

traverse(ll.iterator)

traverse(ll.descendingIterator)

 

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

{{libheader|Wren-llist}}

{{libheader|Wren-fmt}}

 

// create a new doubly-linked list and add the first 50 positive integers to it

Fmt.write("$4d ", i)

if (i % 10 == 1) System.print()

 

{{out}}

20 19 18 17 16 15 14 13 12 11

10 9 8 7 6 5 4 3 2 1

</pre>

 

=={{header|zkl}}==

fcn init(_value,_prev=Void,_next=Void)

{ var value=_value, prev=_prev, next=_next; }

b

}

n:=a; while(n){ print(n," "); n=n.next }

println();

n:=c; while(n){ print(n," "); n=n.prev }

{{out}}

<pre>