Doubly-linked list/Traversal

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

• Array
• Associative array: Creation, Iteration
• Collections
• Compound data type
• Doubly-linked list: Definition, Element definition, Element insertion, List Traversal, Element Removal
• Linked list
• Queue: Definition, Usage
• Set
• Singly-linked list: Element definition, Element insertion, List Traversal, Element Removal
• Stack

Action!

The user must type in the monitor the following command after compilation and before running the program!

SET EndProg=*

Library: Action! Tool Kit

CARD EndProg ;required for ALLOCATE.ACT

INCLUDE "D2:ALLOCATE.ACT" ;from the Action! Tool Kit. You must type 'SET EndProg=*' from the monitor after compiling, but before running this program!

DEFINE PTR="CARD"
DEFINE NODE_SIZE="6"
TYPE ListNode=[INT data PTR prv,nxt]

ListNode POINTER listBegin,listEnd

PROC Append(INT v)
  ListNode POINTER n

  n=Alloc(NODE_SIZE)
  n.data=v
  n.prv=listEnd
  n.nxt=0
  IF listEnd THEN
    listEnd.nxt=n
  ELSE
    listBegin=n
  FI
  listEnd=n
RETURN

PROC Clear()
  ListNode POINTER n,next

  n=listBegin
  WHILE n
  DO
    next=n.nxt
    Free(n,NODE_SIZE)
    n=next
  OD
  listBegin=0
  listEnd=0
RETURN

PROC ForwardTraverse()
  ListNode POINTER n

  n=listBegin
  PrintE("Forward traverse:")
  Print("(")
  WHILE n
  DO
    PrintI(n.data)
    IF n.nxt THEN
      Print(", ")
    FI
    n=n.nxt
  OD
  PrintE(")")
RETURN

PROC BackwardTraverse()
  ListNode POINTER n

  n=listEnd
  PrintE("Backward traverse")
  Print("(")
  WHILE n
  DO
    PrintI(n.data)
    IF n.prv THEN
      Print(", ")
    FI
    n=n.prv
  OD
  PrintE(")")
RETURN

PROC Main()
  INT i
  Put(125) PutE() ;clear screen
  
  AllocInit(0)
  listBegin=0
  listEnd=0

  FOR i=0 TO 50
  DO
    Append(i*i)
  OD
  ForwardTraverse()
  PutE()
  BackwardTraverse()

  Clear()
RETURN

Output:

Screenshot from Atari 8-bit computer

Forward traverse:
(0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361,
400, 441, 484, 529, 576, 625, 676, 729, 784, 841, 900, 961, 1024, 1089, 1156, 1225, 1296,
1369, 1444, 1521, 1600, 1681, 1764, 1849, 1936, 2025, 2116, 2209, 2304, 2401, 2500)

Backward traverse
(2500, 2401, 2304, 2209, 2116, 2025, 1936, 1849, 1764, 1681, 1600, 1521, 1444, 1369, 1296,
1225, 1156, 1089, 1024, 961, 900, 841, 784, 729, 676, 625, 576, 529, 484, 441, 400, 361,
324, 289, 256, 225, 196, 169, 144, 121, 100, 81, 64, 49, 36, 25, 16, 9, 4, 1, 0)

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;

ALGOL 68

LinkedList.alg:

# Node struct - contains next and prev NODE pointers and DATA #
MODE NODE = STRUCT(
    DATA data, 
    REF NODE prev, 
    REF NODE next 
    );

# List structure - contains head and tail NODE pointers #    
MODE LIST = STRUCT(
    REF NODE head, 
    REF NODE tail 
    );

# --- PREPEND - Adds a node to the beginning of the list ---#
PRIO PREPEND = 1;
OP   PREPEND = (REF LIST list, DATA data) VOID: 
(    		
    HEAP NODE n := (data, NIL, NIL); 
    IF head OF list IS REF NODE(NIL) THEN
        head OF list := tail OF list := n 
    ELSE
        next OF n := head OF list; 
        prev OF head OF list := head OF list := n
    FI
);
#--- APPEND - Adds a node to the end of the list ---#
PRIO APPEND = 1; 
OP   APPEND = (REF LIST list, DATA data) VOID: 
(                                              
    HEAP NODE n := (data, NIL, NIL);
    IF head OF list IS REF NODE(NIL) THEN
        head OF list := tail OF list := n     
    ELSE
        prev OF n := tail OF list;
        next OF tail OF list := tail OF list := n
    FI
);

#--- REMOVE_FIRST - removes & returns node at end of the list ---#
PRIO REMOVE_FIRST = 1;
OP   REMOVE_FIRST = (REF LIST list) DATA: 
(                                         
    IF head OF list ISNT REF NODE(NIL) THEN
        DATA d := data OF head OF list;
        prev OF next OF head OF list := NIL;
        head OF list := next OF head OF list;
        d # return d #
    FI
);
#--- REMOVE_LAST: removes & returns node at front of list ---   #
PRIO REMOVE_LAST = 1;
OP   REMOVE_LAST = (REF LIST list) DATA:
(
    IF head OF list ISNT REF NODE(NIL) THEN
        DATA d := data OF tail OF list;
        next OF prev OF tail OF list := NIL;
        tail OF list := prev OF tail OF list;
        d # return d #
    FI
);
#--- PURGE - removes all elements from the list ---#
PRIO PURGE = 2;
OP   PURGE = (REF LIST list) VOID:
(
    head OF list := tail OF list := NIL 
);

#--- returns the data at the end of the list ---#
PRIO LAST_IN = 2;
OP LAST_IN = (REF LIST list) DATA: (  
    IF head OF list ISNT REF NODE(NIL) THEN
        data OF tail OF list  
    FI 
);

#--- returns the data at the front of the list ---#
PRIO FIRST_IN  = 2;
OP FIRST_IN = (REF LIST list) DATA: (  
    IF head OF list ISNT REF NODE(NIL) THEN 
        data OF head OF list 
    FI 
);

#--- Traverses through the list forwards ---#
PROC forward traversal = (LIST list) VOID:
(
    REF NODE travel := head OF list;
    WHILE travel ISNT REF NODE(NIL) DO
        list visit(data OF travel);
        travel := next OF travel
    OD
);

#--- Traverses through the list backwards ---#
PROC backward traversal = (LIST list) VOID:
(
    REF NODE travel := tail OF list;
    WHILE travel ISNT REF NODE(NIL) DO
        list visit(data OF travel);
        travel := prev OF travel
    OD
)

main.alg:

PR READ "LinkedList.alg" PR; 

MODE EMPLOYEE = STRUCT(STRING name, INT salary, INT years);
MODE DATA = EMPLOYEE; #Sets the data type that is in the list#

# Function that traversals call for each node in list  #
PROC list visit = (REF DATA data) VOID:  
(
    print((
        "EMPLOYEE NAME  :  ", name OF data ,  newline,
        "         SALARY: " , salary OF data, newline,
        "         YEARS : " , years OF data,  newline
    ))
);

#***************************************************************#
main:
(
    EMPLOYEE empl;
    name OF empl := "one";
    salary OF empl := 100;
    years OF empl := 10;
    
    LIST list := (NIL, NIL);

    list PREPEND empl; 
    name OF empl := "two";
    salary OF empl := 200;
    years OF empl := 20;
    list APPEND empl; 
    name OF empl := "three";
    salary OF empl := 300;
    years OF empl := 30;
    list APPEND empl; 
    salary OF empl := 400;
    years OF empl := 40;
    name OF empl := "four";
    list APPEND empl;

    forward traversal(list);
    PURGE list;
    forward traversal(list)
)

Output:

EMPLOYEE NAME  :  one                                                                                                
         SALARY:        +100                                                                                         
         YEARS :         +10                                                                                         
EMPLOYEE NAME  :  two                                                                                                
         SALARY:        +200                                                                                         
         YEARS :         +20                                                                                         
EMPLOYEE NAME  :  three                                                                                              
         SALARY:        +300                                                                                         
         YEARS :         +30                                                                                         
EMPLOYEE NAME  :  four                                                                                               
         SALARY:        +400                                                                                         
         YEARS :         +40   

ALGOL W

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

begin
    % record type to hold an element of a doubly linked list of integers      %
    record DListIElement ( reference(DListIElement) prev
                         ; integer iValue
                         ; reference(DListIElement) next
                         );
    % additional record types would be required for other element types       %
    % inserts a new element into the list, before e                           %
    reference(DListIElement) procedure insertIntoDListIBefore( reference(DListIElement) value e
                                                             ; integer                  value v
                                                             );
    begin
        reference(DListIElement) newElement;
        newElement := DListIElement( null, v, e );
        if e not = null then begin
            % the element we are inserting before is not null                 %
            reference(DListIElement) ePrev;
            ePrev            := prev(e);
            prev(newElement) := ePrev;
            prev(e)          := newElement;
            if ePrev not = null then next(ePrev) := newElement
        end if_e_ne_null ;
        newElement
    end insertIntoDListiAfter ;

    begin
        reference(DListIElement) head, e, last;
        head := null;
        head := insertIntoDListIBefore( head,        1701 );
        head := insertIntoDListIBefore( head,        9000 );
        e    := insertIntoDListIBefore( next(head), 90210 );
        e    := insertIntoDListIBefore( next(e),     4077 );
        e    := head;
        last := null;
        write( "Forward:" );
        while e not = null do begin
            write( i_w := 1, s_w := 0, " ", iValue(e) );
            last := e;
            e    := next(e)
        end while_e_ne_null ;
        write( "Backward:" );
        e := last;
        while e not = null do begin
            write( i_w := 1, s_w := 0, " ", iValue(e) );
            last := e;
            e    := prev(e)
        end while_e_ne_null
    end
end.

Output:

Forward:
 9000
 90210
 4077
 1701
Backward:
 1701
 4077
 90210
 9000

Applesoft BASIC

 100  REM BUILD THE LIST
 110  FOR I = 20 TO 40 STEP 10
 120      LET S$ =  STR$ (I): GOSUB 260"APPEND"
 130  NEXT I
 140  REM TRAVERSE FORWARDS
 150  LET N = HEAD
 160  FOR Q = 1 TO 1
 170      IF N <  > NIL THEN  PRINT S$(N)" ";:N = N(N):Q = 0
 180  NEXT Q
 190  PRINT 
 200  REM TRAVERSE BACKWARDS
 210  LET N = TAIL
 220  FOR Q = 1 TO 1
 230      IF N <  > NIL THEN  PRINT S$(N)" ";:N = P(N):Q = 0
 240  NEXT Q
 250  END 
 260  REM APPEND S$
 270  LET NIL =  - 1
 280  LET P(L) = NIL
 290  LET N(L) = NIL
 300  REM TRAVERSE UNTIL LAST NODE FOUND
 310  FOR Q = 1 TO 1
 320      IF N(N) <  > NIL THEN N = N(N):Q = 0
 330  NEXT Q
 340  REM NEW NODE
 350  LET S$(L) = S$
 360  LET N(L) = NIL
 370  IF N <  > L THEN P(L) = N
 380  REM POINT THE LAST NODE AT THE NEW NODE
 390  IF N <  > L THEN N(N) = L
 400  LET TAIL = L
 410  LET N = TAIL
 420  LET L = L + 1
 430  RETURN

ARM Assembly

Works with: as version Raspberry Pi

/* ARM assembly Raspberry PI  */
/*  program transDblList.s   */
/* REMARK 1 : this program use routines in a include file 
   see task Include a file language arm assembly 
   for the routine affichageMess conversion10S 
   see at end of this program the instruction include */

/* Constantes    */
.equ STDOUT, 1                           @ Linux output console
.equ EXIT,   1                           @ Linux syscall
.equ READ,   3
.equ WRITE,  4

/*******************************************/
/* Structures                               */
/********************************************/
/* structure Doublylinkedlist*/
    .struct  0
dllist_head:                    @ head node
    .struct  dllist_head + 4
dllist_tail:                    @ tail node
    .struct  dllist_tail  + 4
dllist_fin:
/* structure Node Doublylinked List*/
    .struct  0
NDlist_next:                    @ next element
    .struct  NDlist_next + 4 
NDlist_prev:                    @ previous element
    .struct  NDlist_prev + 4 
NDlist_value:                   @ element value or key
    .struct  NDlist_value + 4 
NDlist_fin:
/* Initialized data */
.data
szMessInitListe:         .asciz "List initialized.\n"
szMessListInv:           .asciz "Display list inverse :\n"
szCarriageReturn:        .asciz "\n"
szMessErreur:            .asciz "Error detected.\n"
/* datas message display */
szMessResult:            .ascii "Result value :"
sValue:                  .space 12,' '
                         .asciz "\n"
/* UnInitialized data */
.bss 
dllist1:              .skip dllist_fin    @ list memory place 

/*  code section */
.text
.global main 
main: 
    ldr r0,iAdrdllist1
    bl newDList                      @ create new list
    ldr r0,iAdrszMessInitListe
    bl affichageMess
    ldr r0,iAdrdllist1               @ list address
    mov r1,#10                       @ value
    bl insertHead                    @ insertion at head
    cmp r0,#-1
    beq 99f
    ldr r0,iAdrdllist1
    mov r1,#20
    bl insertTail                    @ insertion at tail
    cmp r0,#-1
    beq 99f
    ldr r0,iAdrdllist1               @ list address
    mov r1,#10                       @ value to after insered
    mov r2,#15                       @ new value
    bl insertAfter
    cmp r0,#-1
    beq 99f
    ldr r0,iAdrdllist1               @ list address
    mov r1,#20                       @ value to after insered
    mov r2,#25                       @ new value
    bl insertAfter
    cmp r0,#-1
    beq 99f
    ldr r0,iAdrdllist1
    bl transHeadTail                 @ display value head to tail
    ldr r0,iAdrszMessListInv
    bl affichageMess
    ldr r0,iAdrdllist1
    bl transTailHead                 @ display value tail to head
    b 100f
99:
    ldr r0,iAdrszMessErreur
    bl affichageMess
100:                                 @ standard end of the program
    mov r7, #EXIT                    @ request to exit program
    svc 0                            @ perform system call
iAdrszMessInitListe:       .int szMessInitListe
iAdrszMessErreur:          .int szMessErreur
iAdrszMessListInv:         .int szMessListInv
iAdrszCarriageReturn:      .int szCarriageReturn
iAdrdllist1:               .int dllist1
/******************************************************************/
/*     create new list                         */ 
/******************************************************************/
/* r0 contains the address of the list structure */
newDList:
    push {r1,lr}                         @ save  registers 
    mov r1,#0
    str r1,[r0,#dllist_tail]
    str r1,[r0,#dllist_head]
    pop {r1,lr}                          @ restaur registers
    bx lr                                @ return
/******************************************************************/
/*     list is empty ?                         */ 
/******************************************************************/
/* r0 contains the address of the list structure */
/* r0 return 0 if empty  else return 1 */
isEmpty:
    //push {r1,lr}                         @ save  registers 
    ldr r0,[r0,#dllist_head]
    cmp r0,#0
    movne r0,#1
    //pop {r1,lr}                          @ restaur registers
    bx lr                                @ return
/******************************************************************/
/*     insert value at list head                        */ 
/******************************************************************/
/* r0 contains the address of the list structure */
/* r1 contains value */
insertHead:
    push {r1-r4,lr}                         @ save  registers 
    mov r4,r0                            @ save address
    mov r0,r1                            @ value
    bl createNode
    cmp r0,#-1                           @ allocation error ?
    beq 100f
    ldr r2,[r4,#dllist_head]             @ load address first node
    str r2,[r0,#NDlist_next]             @ store in next pointer on new node
    mov r1,#0
    str r1,[r0,#NDlist_prev]             @ store zero in previous pointer on new node
    str r0,[r4,#dllist_head]             @ store address new node in address head list 
    cmp r2,#0                            @ address first node is null ?
    strne r0,[r2,#NDlist_prev]           @ no store adresse new node in previous pointer
    streq r0,[r4,#dllist_tail]           @ else store new node in tail address
100:
    pop {r1-r4,lr}                          @ restaur registers
    bx lr                                @ return
/******************************************************************/
/*     insert value at list tail                        */ 
/******************************************************************/
/* r0 contains the address of the list structure */
/* r1 contains value */
insertTail:
    push {r1-r4,lr}                         @ save  registers 
    mov r4,r0                               @ save list address
    mov r0,r1                               @ value
    bl createNode                           @ new node
    cmp r0,#-1
    beq 100f                                @ allocation error
    ldr r2,[r4,#dllist_tail]                @ load address last node
    str r2,[r0,#NDlist_prev]                @ store in previous pointer on new node
    mov r1,#0                               @ store null un next pointer
    str r1,[r0,#NDlist_next]
    str r0,[r4,#dllist_tail]                @ store address new node on list tail
    cmp r2,#0                               @ address last node is null ?
    strne r0,[r2,#NDlist_next]              @ no store address new node in next pointer
    streq r0,[r4,#dllist_head]              @ else store in head list
100:
    pop {r1-r4,lr}                          @ restaur registers
    bx lr                                   @ return
/******************************************************************/
/*     insert value after other element                        */ 
/******************************************************************/
/* r0 contains the address of the list structure */
/* r1 contains value to search*/
/* r2 contains value to insert */
insertAfter:
    push {r1-r5,lr}                         @ save  registers 
    mov r4,r0
    bl searchValue                          @ search node with this value in r1
    cmp r0,#-1
    beq 100f                                @ not found -> error
    mov r5,r0                               @ save address of node find
    mov r0,r2                               @ new value
    bl createNode                           @ create new node
    cmp r0,#-1
    beq 100f                                @ allocation error
    ldr r2,[r5,#NDlist_next]                @ load pointer next of find node
    str r0,[r5,#NDlist_next]                @ store new node in pointer next
    str r5,[r0,#NDlist_prev]                @ store address find node in previous pointer on new node
    str r2,[r0,#NDlist_next]                @ store pointer next of find node on pointer next on new node
    cmp r2,#0                               @ next pointer is null ?
    strne r0,[r2,#NDlist_prev]              @ no store address new node in previous pointer 
    streq r0,[r4,#dllist_tail]              @ else store in list tail
100:
    pop {r1-r5,lr}                          @ restaur registers
    bx lr                                @ return
/******************************************************************/
/*     search value                                               */ 
/******************************************************************/
/* r0 contains the address of the list structure */
/* r1 contains the value to search  */
/* r0 return address of node or -1 if not found */
searchValue:
    push {r2,lr}                         @ save  registers 
    ldr r0,[r0,#dllist_head]             @ load first node
1:
    cmp r0,#0                            @ null -> end search not found
    moveq r0,#-1
    beq 100f
    ldr r2,[r0,#NDlist_value]            @ load node value
    cmp r2,r1                            @ equal ?
    beq 100f
    ldr r0,[r0,#NDlist_next]             @ load addresse next node 
    b 1b                                 @ and loop
100:
    pop {r2,lr}                          @ restaur registers
    bx lr                                @ return
/******************************************************************/
/*     transversal for head to tail                                               */ 
/******************************************************************/
/* r0 contains the address of the list structure */
transHeadTail:
    push {r2,lr}                         @ save  registers 
    ldr r2,[r0,#dllist_head]             @ load first node
1:
    ldr r0,[r2,#NDlist_value]
    ldr r1,iAdrsValue
    bl conversion10S
    ldr r0,iAdrszMessResult
    bl affichageMess
    ldr r2,[r2,#NDlist_next]
    cmp r2,#0
    bne 1b
100:
    pop {r2,lr}                          @ restaur registers
    bx lr                                @ return
iAdrszMessResult:          .int szMessResult
iAdrsValue:                .int sValue
/******************************************************************/
/*     transversal for tail to head                                               */ 
/******************************************************************/
/* r0 contains the address of the list structure */
transTailHead:
    push {r2,lr}                         @ save  registers 
    ldr r2,[r0,#dllist_tail]             @ load last node
1:
    ldr r0,[r2,#NDlist_value]
    ldr r1,iAdrsValue
    bl conversion10S
    ldr r0,iAdrszMessResult
    bl affichageMess
    ldr r2,[r2,#NDlist_prev]
    cmp r2,#0
    bne 1b
100:
    pop {r2,lr}                          @ restaur registers
    bx lr                                @ return
/******************************************************************/
/*     Create new node                                            */ 
/******************************************************************/
/* r0 contains the value */
/* r0 return node address or -1 if allocation error*/
createNode:
    push {r1-r7,lr}                         @ save  registers 
    mov r4,r0                            @ save value
    @ allocation place on the heap
    mov r0,#0                                   @ allocation place heap
    mov r7,#0x2D                                @ call system 'brk'
    svc #0
    mov r5,r0                                   @ save address heap for output string
    add r0,#NDlist_fin                            @ reservation place one element
    mov r7,#0x2D                                @ call system 'brk'
    svc #0
    cmp r0,#-1                                  @ allocation error
    beq 100f
    mov r0,r5
    str r4,[r0,#NDlist_value]                   @ store value
    mov r2,#0
    str r2,[r0,#NDlist_next]                    @ store zero to pointer next
    str r2,[r0,#NDlist_prev]                    @ store zero to pointer previous
100:
    pop {r1-r7,lr}                          @ restaur registers
    bx lr                                @ return
/***************************************************/
/*      ROUTINES INCLUDE                 */
/***************************************************/
.include "../affichage.inc"

AutoHotkey

see Doubly-linked list/AutoHotkey

Axe

LINK(L₁,1)→A
LINK(L₁+10,2)→B
LINK(L₁+50,3)→C
 
INSERT(A,B)
INSERT(A,C)

A→I
While I≠0
 Disp VALUE(I)▶Dec,i
 NEXT(I)→I
End

Disp "-----",i

B→I
While I≠0
 Disp VALUE(I)▶Dec,i
 PREV(I)→I
End

BBC BASIC

Works with: BBC BASIC for Windows

      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

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

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

C++

Works with: C++11

#include <iostream>
#include <list>

int main ()
{
    std::list<int> numbers {1, 5, 7, 0, 3, 2};
    for(const auto& i: numbers)
        std::cout << i << ' ';
    std::cout << '\n';
}

Output:

1 5 7 0 3 2 

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

D

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 

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

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;

E

This example is incorrect. Please fix the code and remove this message. Details: 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 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

Erlang

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

F#

open System.Collections.Generic

let first (l: LinkedList<char>) = l.First
let last (l: LinkedList<char>) = l.Last

let next (l: LinkedListNode<char>) = l.Next
let prev (l: LinkedListNode<char>) = l.Previous

let traverse g f (ls: LinkedList<char>) =
    let rec traverse (l: LinkedListNode<char>) =
        match l with
        | null -> ()
        | _ ->
            printf "%A" l.Value
            traverse (f l)
    traverse (g ls)

let traverseForward = traverse first next
let traverseBackward = traverse last prev

let cs = LinkedList(['a'..'z'])

traverseForward cs
printfn ""
traverseBackward cs

Output:

'a''b''c''d''e''f''g''h''i''j''k''l''m''n''o''p''q''r''s''t''u''v''w''x''y''z'
'z''y''x''w''v''u''t''s''r''q''p''o''n''m''l''k''j''i''h''g''f''e''d''c''b''a'

Fortran

see Doubly-linked list/Definition#Fortran

FreeBASIC

Dim As Integer i, MiLista()

For i = 0 To Int(Rnd * 100)+25
    Redim Preserve MiLista(i)
    MiLista(i) = Rnd * 314
Next

'Tour from the beginning 
For i = Lbound(MiLista) To Ubound(MiLista)
    Print MiLista(i)
Next i

Print
'Travel from the end 
For i = Ubound(MiLista) To Lbound(MiLista) Step -1
    Print MiLista(i)
Next i
Sleep

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

Groovy

class DoubleLinkedListTraversing {
    static void main(args) {
        def linkedList = (1..9).collect() as LinkedList

        linkedList.each {
            print it
        }

        println()

        linkedList.reverseEach {
            print it
        }
    }
}

Output:

123456789
987654321

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)

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

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.

Java

Works with: Java version 8 or higher

package com.rosettacode;

import java.util.LinkedList;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class DoubleLinkedListTraversing {

  public static void main(String[] args) {

    final LinkedList<String> doubleLinkedList =
        IntStream.range(1, 10)
            .mapToObj(String::valueOf)
            .collect(Collectors.toCollection(LinkedList::new));

    doubleLinkedList.iterator().forEachRemaining(System.out::print);
    System.out.println();
    doubleLinkedList.descendingIterator().forEachRemaining(System.out::print);
  }
}

Output:

123456789
987654321

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.

Julia

mutable struct DLNode{T}
    value::T
    pred::Union{DLNode{T}, Nothing}
    succ::Union{DLNode{T}, Nothing}
    DLNode(v) = new{typeof(v)}(v, nothing, nothing)
end

function insertpost(prevnode, node)
    succ = prevnode.succ
    prevnode.succ = node
    node.pred = prevnode
    node.succ = succ
    if succ != nothing
        succ.pred =  node
    end
    node
end

first(nd) = (while nd.pred != nothing nd = nd.prev end; nd)
last(nd) = (while nd.succ != nothing nd = nd.succ end; nd)

function printconnected(nd; fromtail = false)
    if fromtail
        nd = last(nd)
        print(nd.value)
        while nd.pred != nothing 
            nd = nd.pred
            print(" -> $(nd.value)")
        end
    else
        nd = first(nd)
        print(nd.value)
        while nd.succ != nothing
            nd = nd.succ
            print(" -> $(nd.value)")
        end
    end
    println()
end

node1 = DLNode(1)
node2 = DLNode(2)
node3 = DLNode(3)
insertpost(node1, node2)
insertpost(node2, node3)
print("From beginning to end: "); printconnected(node1)
print("From end to beginning: "); printconnected(node1, fromtail = true)

Output:

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

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:

// version 1.1.2

class LinkedList<E> {
    class Node<E>(var data: E, var prev: Node<E>? = null, var next: Node<E>? = null) {
        override fun toString(): String {
            val sb = StringBuilder(this.data.toString())
            var node = this.next
            while (node != null) {
                sb.append(" -> ", node.data.toString())
                node = node.next
            }
            return sb.toString()
        }
    }

    var first: Node<E>? = null
    var last:  Node<E>? = null

    fun addFirst(value: E) {
        if (first == null) {
            first = Node(value)
            last =  first
        }
        else {
            val node = first!!
            first = Node(value, null, node)
            node.prev = first
        }
    }

    fun addLast(value: E) {
        if (last == null) {
            last = Node(value)
            first = last
        }
        else {
            val node = last!!
            last = Node(value, node, null)
            node.next = last
        }
    }

    fun insert(after: Node<E>?, value: E) {
        if (after == null)
            addFirst(value)
        else if (after == last)
            addLast(value)
        else {
            val next = after.next
            val new = Node(value, after, next)
            after.next = new
            if (next != null) next.prev = new
        }
    }

    override fun toString() = first.toString()

    fun firstToLast() = first?.toString() ?: ""

    fun lastToFirst(): String {
        if (last == null) return ""
        val sb = StringBuilder(last.toString())
        var node = last!!.prev
        while (node != null) {
             sb.append(" -> ", node.data.toString())
             node = node.prev
        }
        return sb.toString()
    }
}

fun main(args: Array<String>) {
    val ll = LinkedList<Int>()
    ll.addFirst(1)
    ll.addLast(4)
    ll.insert(ll.first, 2)
    ll.insert(ll.last!!.prev, 3)
    println("First to last : ${ll.firstToLast()}")
    println("Last to first : ${ll.lastToFirst()}")
}

Output:

First to last : 1 -> 2 -> 3 -> 4
Last to first : 4 -> 3 -> 2 -> 1

Lua

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

--------------
-- TRAVERSAL:
--------------
List.iterateForward = function(self)
  local function iter(self, node)
    if node then return node.next else return self.head end
  end
  return iter, self, nil
end
List.iterateReverse = function(self)
  local function iter(self, node)
    if node then return node.prev else return self.tail end
  end
  return iter, self, nil
end

---------
-- TEST:
---------
local list = List()
for i = 1, 5 do list:insertTail(i) end
io.write("Forward: ") for node in list:iterateForward() do io.write(node.data..",") end print()
io.write("Reverse: ") for node in list:iterateReverse() do io.write(node.data..",") end print()

Output:

Forward: 1,2,3,4,5,
Reverse: 5,4,3,2,1,

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

Nim

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

Oberon-2

MODULE Collections;
IMPORT Box;

TYPE
  Action = PROCEDURE (o: Box.Object);

        PROCEDURE (dll: DLList) GoForth*(do: Action);
	VAR
		iter: Node;
	BEGIN
		iter := dll.first;
		WHILE iter # NIL DO
			do(iter.value);
			iter := iter.next
		END
	END GoForth;

	PROCEDURE (dll: DLList) GoBack*(do: Action);
	VAR
		iter: Node;
	BEGIN
		ASSERT(dll.last # NIL);
		iter := dll.last;
		WHILE iter # NIL DO
			do(iter.value);
			iter := iter.prev
		END
	END GoBack;

END Collections.

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

Oforth

Complete definition is here : Doubly-linked list/Definition#Oforth

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

DList method: forEachNext
   dup ifNull: [ drop @head ifNull: [ false ] else: [ @head @head true] return ]
   next dup ifNull: [ drop false ] else: [ dup true ] ;

DList method: forEachPrev
   dup ifNull: [ drop @tail ifNull: [ false ] else: [ @tail @tail true] return ]
   prev dup ifNull: [ drop false ] else: [ dup true ] ;

: test
| dl n |
   DList new ->dl
   dl insertFront("A") 
   dl insertBack("B")
   dl head insertAfter(DNode new("C", null , null))

   "Traversal (beginning to end) : " println
   dl forEach: n [ n . ]

   "\nTraversal (end to beginning) : " println
   dl revEach: n [ n . ] ;

Output:

>test
Traversal (beginning to end) :
A C B
Traversal (end to beginning) :
B C A ok

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}

Pascal

See Delphi

PascalABC.NET

begin
  var lst := new LinkedList<integer>(1..10);
  var current := lst.First;
  while current <> nil do
  begin
    Print(current.Value);
    current := current.Next;
  end;
end.

Output:

1 2 3 4 5 6 7 8 9 10 

Phix

enum NEXT,PREV,DATA
constant empty_dll = {{1,1}}
sequence dll = deep_copy(empty_dll)
 
procedure insert_after(object data, integer pos=1)
    integer prv = dll[pos][PREV]
    dll = append(dll,{pos,prv,data})
    if prv!=0 then
        dll[prv][NEXT] = length(dll)
    end if
    dll[pos][PREV] = length(dll)
end procedure
 
insert_after("ONE")
insert_after("TWO")
insert_after("THREE")
 
?dll
 
procedure show(integer d)
integer idx = dll[1][d]
    while idx!=1 do
        ?dll[idx][DATA]
        idx = dll[idx][d]
    end while
end procedure
show(NEXT)
?"=="
show(PREV)

Output:

{{2,4},{3,1,"ONE"},{4,2,"TWO"},{1,3,"THREE"}}
"ONE"
"TWO"
"THREE"
"=="
"THREE"
"TWO"
"ONE"

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

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

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())

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.

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

Raku

(formerly Perl 6)

Since the list routines are supplied by the generic roles defined in Doubly-linked_list/Definition#Raku, 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.

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

Ring

# Project : Doubly-linked list/Traversal

trav = [123, 789, 456]
travfor = sort(trav)
see "Traverse forwards:" + nl
see travfor
see nl
travback = reverse(travfor)
see "Traverse backwards:" + nl
see travback
see nl

Output:

Traverse forwards:
123
456
789

Traverse backwards:
789
456
123

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}

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

Scala

import java.util

object DoublyLinkedListTraversal extends App {

  private val ll = new util.LinkedList[String]

  private def traverse(iter: util.Iterator[String]) =
    while (iter.hasNext) iter.next

  traverse(ll.iterator)
  traverse(ll.descendingIterator)
}

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

Wren

Library: Wren-llist

Library: Wren-fmt

import "./llist" for DLinkedList
import "./fmt" for Fmt

// create a new doubly-linked list and add the first 50 positive integers to it
var dll = DLinkedList.new(1..50)

// traverse the doubly-linked list from head to tail
for (i in dll) {
    Fmt.write("$4d ", i)
    if (i % 10 == 0) System.print()
}
System.print()
// traverse the doubly-linked list from tail to head
for (i in dll.reversed) {
    Fmt.write("$4d ", i)
    if (i % 10 == 1) System.print()
}

Output:

   1    2    3    4    5    6    7    8    9   10 
  11   12   13   14   15   16   17   18   19   20 
  21   22   23   24   25   26   27   28   29   30 
  31   32   33   34   35   36   37   38   39   40 
  41   42   43   44   45   46   47   48   49   50 

  50   49   48   47   46   45   44   43   42   41 
  40   39   38   37   36   35   34   33   32   31 
  30   29   28   27   26   25   24   23   22   21 
  20   19   18   17   16   15   14   13   12   11 
  10    9    8    7    6    5    4    3    2    1 

XPL0

def \Node\ Prev, Data, Next;    \Element (Node) definition
def SizeofInt = 4;

    proc Insert(NewNode, Node);     \Insert NewNode after Node
    int  NewNode, Node, NextNode;
    [NextNode:= Node(Next);
    NextNode(Prev):= NewNode;
    NewNode(Next):= NextNode;
    NewNode(Prev):= Node;
    Node(Next):= NewNode;
    ];

int Head(3), Tail(3);           \Doubly linked list definition
int N, NewNode, Node;
[\Further define (initialize) the doubly linked list
Head(Next):= Tail;
Tail(Prev):= Head;
\Insert some Nodes containing square data
for N:= 1 to 10 do
    [NewNode:= Reserve(3*SizeofInt);
    NewNode(Data):= N*N;
    Insert(NewNode, Head);
    ];
\Traverse list from Head to Tail
Node:= Head(Next);
while Node # Tail do
    [IntOut(0, Node(Data));  ChOut(0, ^ );
    Node:= Node(Next);
    ];
CrLf(0);
\Traverse list from Tail to Head
Node:= Tail(Prev);
while Node # Head do
    [IntOut(0, Node(Data));  ChOut(0, ^ );
    Node:= Node(Prev);
    ];
CrLf(0);
]

Output:

100 81 64 49 36 25 16 9 4 1 
1 4 9 16 25 36 49 64 81 100 

zkl

class Node{
   fcn init(_value,_prev=Void,_next=Void)
      { var value=_value, prev=_prev, next=_next; }
   fcn toString{ value.toString() }
   fcn append(value){
      b,c := Node(value,self,next),next;
      next=b;
      if(c) c.prev=b;
      b
   }
}

a,c := Node("a"), a.append("b").append("c");
n:=a; while(n){ print(n,"  "); n=n.next }
println();
n:=c; while(n){ print(n,"  "); n=n.prev }
println();

Output:

a  b  c  
c  b  a