Doubly-linked list/Traversal

From Rosetta Code
Jump to: navigation, search
Task
Doubly-linked list/Traversal
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.

See also: ArrayAssociative array: Creation, IterationCollectionsCompound data type • Doubly-linked list: Definition, Element definition, Element insertion, Element removal, TraversalLinked list • Queue: Definition, UsageSet • Singly-linked list: Element definition, Element insertion, Element removal, TraversalStack

Contents

[edit] Ada

Works with: Ada 2005
with Ada.Containers.Doubly_Linked_Lists;
with Ada.Text_IO;
 
procedure Traversing is
package Char_Lists is new Ada.Containers.Doubly_Linked_Lists (Character);
 
procedure Print (Position : in Char_Lists.Cursor) is
begin
Ada.Text_IO.Put (Char_Lists.Element (Position));
end Print;
 
My_List : Char_Lists.List;
begin
My_List.Append ('R');
My_List.Append ('o');
My_List.Append ('s');
My_List.Append ('e');
My_List.Append ('t');
My_List.Append ('t');
My_List.Append ('a');
 
My_List.Iterate (Print'Access);
Ada.Text_IO.New_Line;
 
My_List.Reverse_Iterate (Print'Access);
Ada.Text_IO.New_Line;
end Traversing;

[edit] AutoHotkey

see Doubly-linked list/AutoHotkey

[edit] BBC BASIC

      DIM node{pPrev%, pNext%, iData%}
DIM a{} = node{}, b{} = node{}, c{} = node{}
 
a.pNext% = b{}
a.iData% = 123
b.pPrev% = a{}
b.iData% = 789
c.iData% = 456
 
PROCinsert(a{}, c{})
 
PRINT "Traverse forwards:"
pnode% = a{}
REPEAT
 !(^node{}+4) = pnode%
PRINT node.iData%
pnode% = node.pNext%
UNTIL pnode% = 0
 
PRINT "Traverse backwards:"
pnode% = b{}
REPEAT
 !(^node{}+4) = pnode%
PRINT node.iData%
pnode% = node.pPrev%
UNTIL pnode% = 0
 
END
 
DEF PROCinsert(here{}, new{})
LOCAL temp{} : DIM temp{} = node{}
new.pNext% = here.pNext%
new.pPrev% = here{}
 !(^temp{}+4) = new.pNext%
temp.pPrev% = new{}
here.pNext% = new{}
ENDPROC
 

Output:

Traverse forwards:
       123
       456
       789
Traverse backwards:
       789
       456
       123

[edit] C

// A doubly linked list of strings;
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
typedef struct sListEntry {
const char *value;
struct sListEntry *next;
struct sListEntry *prev;
} *ListEntry, *LinkedList;
 
typedef struct sListIterator{
ListEntry link;
LinkedList head;
} *LIterator;
 
LinkedList NewList() {
ListEntry le = malloc(sizeof(struct sListEntry));
if (le) {
le->value = NULL;
le->next = le->prev = NULL;
}
return le;
}
 
int LL_Append(LinkedList ll, const char *newVal)
{
ListEntry le = malloc(sizeof(struct sListEntry));
if (le) {
le->value = strdup(newVal);
le->prev = ll->prev;
le->next = NULL;
if (le->prev)
le->prev->next = le;
else
ll->next = le;
ll->prev = le;
}
return (le!= NULL);
}
 
int LI_Insert(LIterator iter, const char *newVal)
{
ListEntry crnt = iter->link;
ListEntry le = malloc(sizeof(struct sListEntry));
if (le) {
le->value = strdup(newVal);
if ( crnt == iter->head) {
le->prev = NULL;
le->next = crnt->next;
crnt->next = le;
if (le->next)
le->next->prev = le;
else
crnt->prev = le;
}
else {
le->prev = ( crnt == NULL)? iter->head->prev : crnt->prev;
le->next = crnt;
if (le->prev)
le->prev->next = le;
else
iter->head->next = le;
if (crnt)
crnt->prev = le;
else
iter->head->prev = le;
}
}
return (le!= NULL);
}
 
LIterator LL_GetIterator(LinkedList ll )
{
LIterator liter = malloc(sizeof(struct sListIterator));
liter->head = ll;
liter->link = ll;
return liter;
}
 
#define LLI_Delete( iter ) \
{free(iter); \
iter = NULL;}

 
int LLI_AtEnd(LIterator iter)
{
return iter->link == NULL;
}
const char *LLI_Value(LIterator iter)
{
return (iter->link)? iter->link->value: NULL;
}
int LLI_Next(LIterator iter)
{
if (iter->link) iter->link = iter->link->next;
return(iter->link != NULL);
}
int LLI_Prev(LIterator iter)
{
if (iter->link) iter->link = iter->link->prev;
return(iter->link != NULL);
}
 
int main()
{
static const char *contents[] = {"Read", "Orage", "Yeller",
"Glean", "Blew", "Burple"};
int ix;
LinkedList ll = NewList(); //new linked list
LIterator iter;
 
for (ix=0; ix<6; ix++) //insert contents
LL_Append(ll, contents[ix]);
 
iter = LL_GetIterator(ll); //get an iterator
printf("forward\n");
while(LLI_Next(iter)) //iterate forward
printf("value=%s\n", LLI_Value(iter));
LLI_Delete(iter); //delete iterator
 
printf("\nreverse\n");
iter = LL_GetIterator(ll);
while(LLI_Prev(iter)) //iterate reverse
printf("value=%s\n", LLI_Value(iter));
LLI_Delete(iter);
//uhhh-- delete list??
return 0;
}

[edit] C#

using System;
using System.Collections.Generic;
 
namespace RosettaCode.DoublyLinkedList
{
internal static class Program
{
private static void Main()
{
var list = new LinkedList<char>("hello");
 
var current = list.First;
do
{
Console.WriteLine(current.Value);
} while ((current = current.Next) != null);
 
Console.WriteLine();
 
current = list.Last;
do
{
Console.WriteLine(current.Value);
} while ((current = current.Previous) != null);
}
}
}

Output:

h
e
l
l
o

o
l
l
e
h

[edit] Clojure

Given the definition in Doubly-linked list/Definition#Clojure,

(def dl (double-list [:a :b :c :d]))
;=> #'user/dl
 
((juxt seq rseq) dl)
;=> [(:a :b :c :d) (:d :c :b :a)]
 
(take-while identity (iterate get-next (get-head dl)))
;=> (#:double_list.Node{:prev nil,  :next #<Object...>, :data :a, :key #<Object...>}
;=> #:double_list.Node{:prev #<Object...>, :next #<Object...>, :data :b, :key #<Object...>}
;=> #:double_list.Node{:prev #<Object...>, :next #<Object...>, :data :c, :key #<Object...>}
;=> #:double_list.Node{:prev #<Object...>, :next nil,  :data :d, :key #<Object...>})
 
(take-while identity (iterate get-prev (get-tail dl)))
 
;=> (#:double_list.Node{:prev #<Object...>, :next nil,  :data :d, :key #<Object...>}
;=> #:double_list.Node{:prev #<Object...>, :next #<Object...>, :data :c, :key #<Object...>}
;=> #:double_list.Node{:prev #<Object...>, :next #<Object...>, :data :b, :key #<Object...>}
;=> #:double_list.Node{:prev nil,  :next #<Object...>, :data :a, :key #<Object...>})

[edit] D

[edit] Standard Doubly-linked List

void main() {
import std.stdio, std.container, std.range;
 
auto dll = DList!dchar("DCBA"d.dup);
 
dll[].writeln;
dll[].retro.writeln;
}
Output:
ABCD 
DCBA 

[edit] User-defined Doubly-linked list

Same output.

struct Node(T) {
T data;
typeof(this)* prev, next;
}
 
void prepend(T)(ref Node!T* head, in T item) pure nothrow {
auto newNode = new Node!T(item, null, head);
if (head)
head.prev = newNode;
head = newNode;
}
 
void main() {
import std.stdio;
 
Node!char* head;
foreach (char c; "DCBA")
head.prepend(c);
 
auto last = head;
for (auto p = head; p; p = p.next) {
p.data.write;
last = p;
}
writeln;
 
for (auto p = last; p; p = p.prev)
p.data.write;
writeln;
}

[edit] Delphi

uses system ;
 
type
 
// declare the list pointer type
plist = ^List ;
 
// declare the list type, a generic data pointer prev and next pointers
List = record
data : pointer ;
prev : pList ;
next : pList ;
end;
 
// since this task is just showing the traversal I am not allocating the memory and setting up the root node etc.
// Note the use of the carat symbol for de-referencing the pointer.
 
begin
 
// beginning to end
while not (pList^.Next = NIL) do pList := pList^.Next ;
 
// end to beginning
while not (pList^.prev = NIL) do pList := pList^.prev ;
 
end;

[edit] E

This example is incorrect. Doesn't work, probably due to a bug in the list definition: runs over the beginning of the list. Needs debugging. Please fix the code and remove this message.

Given the definition in Doubly-linked list/Definition#E,

def traverse(list) {
var node := list.atFirst()
while (true) {
println(node[])
if (node.hasNext()) {
node := node.next()
} else {
break
}
}
while (true) {
println(node[])
if (node.hasPrev()) {
node := node.prev()
} else {
break
}
}
}
? def list := makeDLList()
# value: <>
 
? list.push(1)
? list.push(2)
? list.push(3)
 
? traverse(list)
1
2
3
3
2
1

[edit] Erlang

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

[edit] Fortran

see Doubly-linked list/Definition#Fortran

[edit] Icon and Unicon

Uses Unicon classes.

class DoubleLink (value, prev_link, next_link)
 
# insert given node after this one, removing its existing connections
method insert_after (node)
node.prev_link := self
if (\next_link) then next_link.prev_link := node
node.next_link := next_link
self.next_link := node
end
 
# use a generator to traverse
# - keep suspending the prev/next link until a null node is reached
method traverse_backwards ()
current := self
while \current do {
suspend current
current := current.prev_link
}
end
 
method traverse_forwards ()
current := self
while \current do {
suspend current
current := current.next_link
}
end
 
initially (value, prev_link, next_link)
self.value := value
self.prev_link := prev_link # links are 'null' if not given
self.next_link := next_link
end
 
procedure main ()
l1 := DoubleLink (1)
l2 := DoubleLink (2)
l1.insert_after (l2)
l1.insert_after (DoubleLink (3))
 
write ("Traverse from beginning to end")
every (node := l1.traverse_forwards ()) do
write (node.value)
 
write ("Traverse from end to beginning")
every (node := l2.traverse_backwards ()) do
write (node.value)
end

Output:

Traverse from beginning to end
1
3
2
Traverse from end to beginning
2
3
1

[edit] J

traverse=:1 :0
work=. result=. conew 'DoublyLinkedListHead'
current=. y
while. y ~: current=. successor__current do.
work=. (work;result;<u data__current) conew 'DoublyLinkedListElement'
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.

[edit] Java

import java.util.LinkedList;
 
public static void main(){
LinkedList<String> LL = new LinkedList<String>();
traverse(LL.iterator());
traverse(LL.descendingIterator());
}
 
private static void traverse(Iterator<String> iter){
while(iter.hasNext()){
iter.next();
}
}

[edit] JavaScript

See Doubly-Linked List (element)#JavaScript. The traverse() and print() functions have been inherited from Singly-Linked List (traversal)#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();

outputs:

10
20
30
40
40
30
20
10

Uses the print() function from Rhino or SpiderMonkey.

[edit] Go

Code is identical to that for task Doubly-linked list/Element insertion except for addition of section at the end of main noted "traverse from end to beginning." Traversal from beginning to end is adequately demonstrated by the String method of dlList.

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

package main
 
import "fmt"
 
type dlNode struct {
string
next, prev *dlNode
}
 
type dlList struct {
head, tail *dlNode
}
 
func (list *dlList) String() string {
if list.head == nil {
return fmt.Sprint(list.head)
}
r := "[" + list.head.string
for p := list.head.next; p != nil; p = p.next {
r += " " + p.string
}
return r + "]"
}
 
func (list *dlList) insertTail(node *dlNode) {
if list.tail == nil {
list.head = node
} else {
list.tail.next = node
}
node.next = nil
node.prev = list.tail
list.tail = node
}
 
func (list *dlList) insertAfter(existing, insert *dlNode) {
insert.prev = existing
insert.next = existing.next
existing.next.prev = insert
existing.next = insert
if existing == list.tail {
list.tail = insert
}
}
 
func main() {
dll := &dlList{}
fmt.Println(dll)
a := &dlNode{string: "A"}
dll.insertTail(a)
dll.insertTail(&dlNode{string: "B"})
fmt.Println(dll)
dll.insertAfter(a, &dlNode{string: "C"})
fmt.Println(dll)
 
// traverse from end to beginning
fmt.Print("From tail:")
for p := dll.tail; p != nil; p = p.prev {
fmt.Print(" ", p.string)
}
fmt.Println("")
}

Output:

<nil>
[A B]
[A C B]
From tail: B C A

[edit] Haskell

main = print . traverse True $ create [10,20,30,40]
 
data DList a = Leaf | Node { prev::(DList a), elt::a, next::(DList a) }
 
create = go Leaf
where go _ [] = Leaf
go prev (x:xs) = current
where current = Node prev x next
next = go current xs
 
isLeaf Leaf = True
isLeaf _ = False
 
lastNode Leaf = Leaf
lastNode dl = until (isLeaf.next) next dl
 
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)

[edit] 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.
 
global hHeap
global hFirst
global hLast
global blockCount
global blockSize
blockSize=len(block.struct)
 
 
call Init
if hHeap=0 then
print "Error occured! Could not create heap, exiting..."
end
end if
 
FirstUser=New("David",20)
notImportant=New("Jessica",35)
notImportant=New("Joey",38)
MiddleUser=New("Jack",56)
notImportant=New("Amy",17)
notImportant=New("Bob",28)
LastUser=New("Kenny",56)
 
 
print "-Traversing the list forwards"
 
hCurrent=hFirst
while hCurrent<>0
print tab(2);dechex$(hCurrent);" ";Block.name$(hCurrent);" ";Block.age(hCurrent)
hCurrent=Block.next(hCurrent)
wend
 
print
print "-Deleting first, middle, and last person."
 
call Delete FirstUser'1
call Delete MiddleUser'2
call Delete LastUser'3
 
print
print "-Traversing the list backwards"
hCurrent=hLast
while hCurrent<>0
print tab(2);dechex$(hCurrent);" ";Block.name$(hCurrent);" ";Block.age(hCurrent)
hCurrent=Block.prev(hCurrent)
wend
 
call Uninit
 
end
 
 
function Block.next(hBlock)
calldll #kernel32,"RtlMoveMemory",block as struct,hBlock as ulong,blockSize as long,ret as void
Block.next=block.nxt.struct
end function
 
function Block.prev(hBlock)
calldll #kernel32,"RtlMoveMemory",block as struct,hBlock as ulong,blockSize as long,ret as void
Block.prev=block.prev.struct
end function
 
function Block.age(hBlock)
calldll #kernel32,"RtlMoveMemory",block as struct,hBlock as ulong,blockSize as long,ret as void
Block.age=block.age.struct
end function
 
function Block.name$(hBlock)
calldll #kernel32,"RtlMoveMemory",block as struct,hBlock as ulong,blockSize as long,ret as void
Block.name$=block.nm.struct
end function
 
sub Block.age hBlock,age
calldll #kernel32,"RtlMoveMemory",block as struct,hBlock as ulong,blockSize as long,ret as void
block.age.struct=age
calldll #kernel32,"RtlMoveMemory",hBlock as ulong,block as struct,blockSize as long,ret as void
end sub
 
sub Block.name hBlock,name$
calldll #kernel32,"RtlMoveMemory",block as struct,hBlock as ulong,blockSize as long,ret as void
block.nm.struct=name$
calldll #kernel32,"RtlMoveMemory",hBlock as ulong,block as struct,blockSize as long,ret as void
end sub
 
sub Block.next hBlock,nxt
calldll #kernel32,"RtlMoveMemory",block as struct,hBlock as ulong,blockSize as long,ret as void
block.nxt.struct=nxt
calldll #kernel32,"RtlMoveMemory",hBlock as ulong,block as struct,blockSize as long,ret as void
end sub
 
sub Block.prev hBlock,prev
calldll #kernel32,"RtlMoveMemory",block as struct,hBlock as ulong,blockSize as long,ret as void
block.prev.struct=prev
calldll #kernel32,"RtlMoveMemory",hBlock as ulong,block as struct,blockSize as long,ret as void
end sub
 
function New(name$,age)
calldll #kernel32,"HeapAlloc",hHeap as ulong,_HEAP_ZERO_MEMORY as ulong,blockSize as long,New as ulong
if New<>0 then
blockCount=blockCount+1
if hFirst=0 then
hFirst=New
hLast=New
else
call Block.next hLast,New
call Block.prev New,hLast
hLast=New
end if
call Block.name New,name$
call Block.age New,age
end if
end function
 
sub Delete hBlock
if hBlock<>0 then
blockCount=blockCount-1
if blockCount=0 then
hFirst=0
hLast=0
else
if hBlock=hFirst then
hFirst=Block.next(hBlock)
call Block.prev hFirst,0
else
if hBlock=hLast then
hLast=Block.prev(hBlock)
call Block.next hLast,0
else
call Block.next Block.prev(hBlock),Block.next(hBlock)
call Block.prev Block.next(hBlock),Block.prev(hBlock)
end if
end if
end if
calldll #kernel32,"HeapFree",hHeap as ulong,0 as long,hBlock as ulong,ret as void
end if
end sub
 
 
sub Init
calldll #kernel32,"HeapCreate",0 as long,10000 as long,0 as long,hHeap as ulong
end sub
 
sub Uninit
calldll #kernel32,"HeapDestroy",hHeap as ulong,ret as void
end sub
 

[edit] Nimrod

type
List[T] = object
head, tail: Node[T]
 
Node[T] = ref TNode[T]
 
TNode[T] = object
next, prev: Node[T]
data: T
 
proc initList[T](): List[T] = discard
 
proc newNode[T](data: T): Node[T] =
new(result)
result.data = data
 
proc prepend[T](l: var List[T], n: Node[T]) =
n.next = l.head
if l.head != nil: l.head.prev = n
l.head = n
if l.tail == nil: l.tail = n
 
proc append[T](l: var List[T], n: Node[T]) =
n.next = nil
n.prev = l.tail
if l.tail != nil:
l.tail.next = n
l.tail = n
if l.head == nil:
l.head = n
 
proc insertAfter[T](l: var List[T], r, n: Node[T]) =
n.prev = r
n.next = r.next
n.next.prev = n
r.next = n
if r == l.tail: l.tail = n
 
proc remove[T](l: var List[T], n: Node[T]) =
if n == l.tail: l.tail = n.prev
if n == l.head: l.head = n.next
if n.next != nil: n.next.prev = n.prev
if n.prev != nil: n.prev.next = n.next
 
proc `$`[T](l: var List[T]): string =
result = ""
var n = l.head
while n != nil:
if result.len > 0: result.add(" -> ")
result.add($n.data)
n = n.next
 
iterator traverseForward[T](l: List[T]): T =
var n = l.head
while n != nil:
yield n.data
n = n.next
 
iterator traverseBackward[T](l: List[T]): T =
var n = l.tail
while n != nil:
yield n.data
n = n.prev
 
var l = initList[int]()
var n = newNode(12)
var m = newNode(13)
var i = newNode(14)
var j = newNode(15)
l.append(n)
l.prepend(m)
l.insertAfter(m, i)
l.prepend(j)
l.remove(m)
 
for i in l.traverseForward():
echo "> ", i
 
for i in l.traverseBackward():
echo "< ", i

[edit] Objeck

 
class Traverse {
function : Main(args : String[]) ~ Nil {
list := Collection.IntList->New();
list->Insert(100);
list->Insert(50);
list->Insert(25);
list->Insert(10);
list->Insert(5);
 
"-- forward --"->PrintLine();
list->Rewind();
while(list->More()) {
list->Get()->PrintLine();
list->Next();
};
 
"-- backward --"->PrintLine();
list->Forward();
while(list->More()) {
list->Get()->PrintLine();
list->Previous();
};
}
}
 
-- forward --
100
5
10
25
50
-- backward --
50
25
10
5
100

[edit] Oz

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

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}

[edit] Pascal

See Delphi

[edit] Perl 6

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

say $dll.list;
say $dll.reverse;

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

[edit] PicoLisp

# Print the elements a doubly-linked list
(de 2print (DLst)
(for (L (car DLst) L (cddr L))
(printsp (car L)) )
(prinl) )
 
# Print the elements a doubly-linked list in reverse order
(de 2printReversed (DLst)
(for (L (cdr DLst) L (cadr L))
(printsp (car L)) )
(prinl) )

Output for the example data produced in Doubly-linked list/Definition#PicoLisp and Doubly-linked list/Element definition#PicoLisp:

: (2print *DLst)                 # Print the list
not was it a cat I saw

: (2printReversed *DLst)         # Print it in reversed order
saw I cat a it was not

Output for the example data produced in Doubly-linked list/Element insertion#PicoLisp:

: (2print *DL)                   # Print the list
A C B

: (2printReversed *DL)           # Print it in reversed order
B C A

[edit] PL/I

/* To implement a doubly-linked list -- i.e., a 2-way linked list. */
doubly_linked_list: proc options (main);
 
define structure
1 node,
2 value fixed,
2 fwd_pointer handle(node),
2 back_pointer handle(node);
 
declare (head, tail, t) handle (node);
declare null builtin;
declare i fixed binary;
 
head, tail = bind(:node, null:);
 
do i = 1 to 10; /* Add ten items to the tail of the queue. */
if head = bind(:node, null:) then
do;
head,tail = new(:node:);
get list (head => value);
put skip list (head => value);
head => back_pointer,
head => fwd_pointer = bind(:node, null:); /* A NULL link */
end;
else
do;
t = new(:node:);
t => back_pointer = tail; /* Point the new tail back to the old */
/* tail. */
tail => fwd_pointer = t; /* Point the tail to the new node. */
t => back_pointer = tail; /* Point the new tail back to the old */
/* tail. */
tail = t; /* Point at teh new tail. */
tail => fwd_pointer = bind(:node, null:);
/* Set the tail link to NULL */
get list (tail => value) copy;
put skip list (tail => value);
end;
end;
 
if head = bind(:node, null:) then return; /* Empty list. */
 
/* Traverse the list from the head. */
put skip list ('In a forwards direction, the list has:');
t = head;
do while (t ^= bind(:node, null:));
put skip list (t => value);
t = t => fwd_pointer;
end;
/* Traverse the list from the tail to the head. */
put skip list ('In the reverse direction, the list has:');
t = tail;
do while (t ^= bind(:node, null:));
put skip list (t => value);
t = t => back_pointer;
end;
end doubly_linked_list;

Output:

In a forwards direction, the list has: 
       1 
       2 
       3 
       4 
       5 
      16 
       7 
       8 
       9 
      10 
In the reverse direction, the list has: 
      10 
       9 
       8 
       7 
      16 
       5 
       4 
       3 
       2 
       1

[edit] PureBasic

NewList MyData.i() ; Create a double linked list holding a single value (integer)
 
;Set up a randomly long linked list in the range 25-125 elements
For i=0 To (Random(100)+25)
AddElement(MyData()) ; Create a new tailing element
MyData()=Random(314) ; Inert a vale into it
Next
;
;Traverse from the beginning of a doubly-linked list to the end.
FirstElement(MyData())
Repeat
Debug MyData() ; Present the value in the current cell
Until Not NextElement(MyData())
;
;Traverse from the end to the beginning.
LastElement(MyData())
Repeat
Debug MyData() ; Present the value in the current cell
Until Not PreviousElement(MyData())

[edit] 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.

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

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

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)

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.

[edit] Racket

See Doubly-Linked List for the structure definitions.

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.

(define (dlist-elements dlist)
(let loop ([elements '()] [dlink (dlist-tail dlist)])
(if dlink
(loop (cons (dlink-content dlink) elements) (dlink-prev dlink))
elements)))
 
(define (dlist-elements/reverse dlist)
(let loop ([elements '()] [dlink (dlist-head dlist)])
(if dlink
(loop (cons (dlink-content dlink) elements) (dlink-next dlink))
elements)))

[edit] REXX

REXX doesn't have linked lists, as there are no pointers (or handles). However, linked lists can be simulated with lists in REXX.

/*REXX program that implements various   List Manager   functions.      */
/*┌────────────────────────────────────────────────────────────────────┐
┌─┘ Functions of the List Manager └─┐
│ │
│ @init ─── initializes the List. │
│ │
│ @size ─── returns the size of the List [could be 0 (zero)]. │
│ │
│ @show ─── shows (displays) the complete List. │
│ @show k,1 ─── shows (displays) the Kth item. │
│ @show k,m ─── shows (displays) M items, starting with Kth item. │
│ @show ,,─1 ─── shows (displays) the complete List backwards. │
│ │
│ @get k ─── returns the Kth item. │
│ @get k,m ─── returns the M items starting with the Kth item. │
│ │
│ @put x ─── adds the X items to the end (tail) of the List. │
│ @put x,0 ─── adds the X items to the start (head) of the List. │
│ @put x,k ─── adds the X items to before of the Kth item. │
│ │
│ @del k ─── deletes the item K. │
│ @del k,m ─── deletes the M items starting with item K. │
└─┐ ┌─┘
└────────────────────────────────────────────────────────────────────┘*/

call sy 'initializing the list.'  ; call @init
call sy 'building list: Was it a cat I saw'; call @put 'Was it a cat I saw'
call sy 'displaying list size.'  ; say 'list size='@size()
call sy 'forward list'  ; call @show
call sy 'backward list'  ; call @show ,,-1
call sy 'showing 4th item'  ; call @show 4,1
call sy 'showing 6th & 6th items'  ; call @show 5,2
call sy 'adding item before item 4: black' ; call @put 'black',4
call sy 'showing list'  ; call @show
call sy 'adding to tail: there, in the ...'; call @put 'there, in the shadows, stalking its prey (and next meal).'
call sy 'showing list'  ; call @show
call sy 'adding to head: Oy!'  ; call @put 'Oy!',0
call sy 'showing list'  ; call @show
exit /*stick a fork in it, we're done.*/
/*──────────────────────────────────subroutines─────────────────────────*/
p: return word(arg(1),1)
sy: say; say left('',30) "───" arg(1) '───'; return
@hasopt: arg o; return pos(o,opt)\==0
@size: return $.#
@init: $.@=''; $.#=0; return 0
@adjust: $.@=space($.@); $.#=words($.@); return 0
 
@parms: arg opt
if @hasopt('k') then k=min($.#+1,max(1,p(k 1)))
if @hasopt('m') then m=p(m 1)
if @hasopt('d') then dir=p(dir 1)
return
 
@show: procedure expose $.; parse arg k,m,dir
if dir==-1 & k=='' then k=$.#
m=p(m $.#);
call @parms 'kmd'
say @get(k,m,dir);
return 0
 
@get: procedure expose $.; arg k,m,dir,_
call @parms 'kmd'
do j=k for m by dir while j>0 & j<=$.#
_=_ subword($.@,j,1)
end /*j*/
return strip(_)
 
@put: procedure expose $.; parse arg x,k
k=p(k $.#+1)
call @parms 'k'
$.@=subword($.@,1,max(0,k-1)) x subword($.@,k)
call @adjust
return 0
 
@del: procedure expose $.; arg k,m
call @parms 'km'
_=subword($.@,k,k-1) subword($.@,k+m)
$.@=_
call @adjust
return

output

                               ─── initializing the list. ───

                               ─── building list: Was it a cat I saw ───

                               ─── displaying list size. ───
list size=6

                               ─── forward list ───
Was it a cat I saw

                               ─── backward list ───
saw I cat a it Was

                               ─── showing 4th item ───
cat

                               ─── showing 6th & 6th items ───
I saw

                               ─── adding item before item 4: black ───

                               ─── showing list ───
Was it a black cat I saw

                               ─── adding to tail: there, in the ... ───

                               ─── showing list ───
Was it a black cat I saw there, in the shadows, stalking its prey (and next meal

                               ─── adding to head: Oy! ───

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

[edit] 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}

[edit] Salmon

Without explicit type information:

class item(init_data)
{
variable next,
previous,
data := init_data;
};
 
function prepend(tail, new_data)
{
immutable result := item(new_data);
result.next := tail;
result.previous := null;
if (tail != null)
tail.previous := result;;
return result;
};
 
variable my_list := null;
my_list := prepend(my_list, "R");
my_list := prepend(my_list, "o");
my_list := prepend(my_list, "s");
my_list := prepend(my_list, "e");
my_list := prepend(my_list, "t");
my_list := prepend(my_list, "t");
my_list := prepend(my_list, "a");
 
"Items in the list going forward:"!
variable follow := my_list;
while (true)
{
follow.data!
if (follow.next == null)
break;;
}
step
follow := follow.next;;
 
"Items in the list going backward:"!
while (follow != null)
follow.data!
step
follow := follow.previous;;

With explicit type information:

class item(init_data : string)
{
variable next: item | {null},
previous : item | {null},
data : string := init_data;
};
 
function prepend(tail : item | {null}, new_data : string) returns item
{
immutable result := item(new_data);
result.next := tail;
result.previous := null;
if (tail != null)
tail.previous := result;;
return result;
};
 
variable my_list : item | {null} := null;
my_list := prepend(my_list, "R");
my_list := prepend(my_list, "o");
my_list := prepend(my_list, "s");
my_list := prepend(my_list, "e");
my_list := prepend(my_list, "t");
my_list := prepend(my_list, "t");
my_list := prepend(my_list, "a");
 
"Items in the list going forward:"!
variable follow : item | {null} := my_list;
while (true)
{
follow.data!
if (follow.next == null)
break;;
}
step
follow := follow.next;;
 
"Items in the list going backward:"!
while (follow != null)
follow.data!
step
follow := follow.previous;;

Both of these produce the following output:

Items in the list going forward:
a
t
t
e
s
o
R
Items in the list going backward:
R
o
s
e
t
t
a

[edit] Tcl

Assuming that the List class from this other task is already present...

# 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 }

Which produces this output:

Forward...
a
b
c
d
Backward...
d
c
b
a
Personal tools
Namespaces

Variants
Actions
Community
Explore
Misc
Toolbox