Jump to content

Singly-linked list/Traversal

From Rosetta Code
Task
Singly-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 singly-linked list to the end.


See also



6502 Assembly

These implementations use the zero page to hold the linked list nodes. The equivalent implementation for any arbitrary address will be left as an exercise to the reader.

Using self-modifying code

In this example, we'll create three nodes, and read the value of the last node. You can copy and paste this code into easy6502 and run it there. Note that the debugger shows that the value in the accumulator is $25, just as expected.

Self-modifying code is an efficient way to perform this task. Unfortunately, easy6502 does not support ORG directives or compile-time pointer arithmetic, so the easiest way to do this was to place a jump to the main program at the beginning and put the self-modifying section between the jump and the main program. (Easy6502's memory layout starts execution at $0600 so it was a simple matter of knowing that JMP takes three bytes and LDA takes two.)

The program will look up the pointer to the next node, modify the operand of the traverse function with that address, and repeat until a null pointer ($00) is read. Then it uses the same traverse function to fetch the value. 

define nullptr 0
jmp main
traverse:
;change the $00 to anything you want
;by writing the desired value to $0604
LDA $00,X	
rts

main:
;create three nodes
; node 0 = #$23 stored at $0003
; node 1 = #$24 stored at $0013
; node 2 = #$25 stored at $0033

LDA #$03
STA $0604 
;alter our code to have the starting address.
;create the linked list.
LDA #$23
STA $03
LDA #$13
STA $04

LDA #$24
STA $13
LDA #$33
STA $14

LDA #$25
STA $33
LDA #nullptr
STA $34

;traverse to last element and load it into A.
LDX #1
loop_traverse:
jsr traverse
;CMP #nullptr	;LDA implicitly compares to zero.
BEQ done	;if equal to nullptr, exit.
STA $0604
jmp loop_traverse
done:
dex
jsr traverse	;get the value of the last element.
brk

Without self-modifying code

This is mostly the same, except it uses the ($nn),y addressing mode which is a bit slower, but can be executed on ROM cartridges no problem. 

define nullptr 0
define tempptr $fc


main:
;create three nodes
; node 0 = #$23 stored at $0003
; node 1 = #$24 stored at $0013
; node 2 = #$25 stored at $0033

;create the linked list.
LDA #$03
STA $FC	;store the pointer to node 0.
LDA #$00
STA $FD ;if you're using the zero page to hold your linked list entries, you need to make the high byte zero.

LDA #$23
STA $03
LDA #$13
STA $04

LDA #$24
STA $13
LDA #$33
STA $14

LDA #$25
STA $33
LDA #nullptr
STA $34

LDY #1
loop:
jsr traverse
BEQ done
STA $FC
BNE loop ;branch always
done:
DEY
JSR traverse
brk

traverse:
LDA ($FC),Y
rts

AArch64 Assembly

Works with: as version Raspberry Pi 3B version Buster 64 bits
/* ARM assembly AARCH64 Raspberry PI 3B */
/*  program afficheList64.s   */

/*******************************************/
/* Constantes file                         */
/*******************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeConstantesARM64.inc"

.equ NBELEMENTS,      100              // list size

/*******************************************/
/* Structures                               */
/********************************************/
/* structure linkedlist*/
    .struct  0
llist_next:                            // next element
    .struct  llist_next + 8
llist_value:                           // element value
    .struct  llist_value + 8
llist_fin:
/* Initialized data */
.data
szMessInitListe:         .asciz "List initialized.\n"
szCarriageReturn:        .asciz "\n"
/* datas error display */
szMessErreur:            .asciz "Error detected.\n"
/* datas message display */
szMessResult:            .asciz "Element No : @ value @ \n"

/* UnInitialized data */
.bss 
lList1:              .skip llist_fin * NBELEMENTS    // list memory place
sZoneConv:           .skip 100
/*  code section */
.text
.global main 
main: 
    ldr x0,qAdrlList1
    mov x1,#0                           // list init
    str x1,[x0,#llist_next]
    ldr x0,qAdrszMessInitListe
    bl affichageMess
    ldr x0,qAdrlList1
    mov x1,#2
    bl insertElement                    // add element value 2
    ldr x0,qAdrlList1
    mov x1,#5
    bl insertElement                    // add element value 5
    //                                   // display elements of list
    ldr x3,qAdrlList1
    mov x2,#0                           // ident element
1:
    ldr x0,[x3,#llist_next]             // end list ?
    cmp x0,#0
    beq 100f                            // yes
    add x2,x2,#1
    mov x0,x2                           // display No element and value
    ldr x1,qAdrsZoneConv
    bl conversion10S
    ldr x0,qAdrszMessResult
    ldr x1,qAdrsZoneConv
    bl strInsertAtCharInc
    mov x5,x0                          // address of new string
    ldr x0,[x3,#llist_value]
    ldr x1,qAdrsZoneConv
    bl conversion10S
    mov x0,x5                          // new address of message
    ldr x1,qAdrsZoneConv
    bl strInsertAtCharInc
    bl affichageMess
    ldr x3,[x3,#llist_next]             // next element
    b 1b                                // and loop
100:                                    // standard end of the program
    mov x8, #EXIT                       // request to exit program
    svc 0                               // perform system call
qAdrszMessInitListe:       .quad szMessInitListe
qAdrszMessErreur:          .quad szMessErreur
qAdrszCarriageReturn:      .quad szCarriageReturn
qAdrlList1:                .quad lList1
qAdrszMessResult:          .quad szMessResult
qAdrsZoneConv:             .quad sZoneConv

/******************************************************************/
/*     insert element at end of list                          */ 
/******************************************************************/
/* x0 contains the address of the list */
/* x1 contains the value of element  */
/* x0 returns address of element or - 1 if error */
insertElement:
    stp x1,lr,[sp,-16]!                   // save  registers
    stp x2,x3,[sp,-16]!                   // save  registers
    mov x2,#llist_fin * NBELEMENTS
    add x2,x2,x0                          // compute address end list
1:                                        // start loop 
    ldr x3,[x0,#llist_next]               // load next pointer
    cmp x3,#0                             // = zero
    csel  x0,x3,x0,ne
    bne 1b                                // no -> loop with pointer
    add x3,x0,#llist_fin                  // yes -> compute next free address
    cmp x3,x2                             // > list end 
    bge 99f                               // yes -> error
    str x3,[x0,#llist_next]               // store next address in current pointer
    str x1,[x0,#llist_value]              // store element value
    mov x1,#0
    str x1,[x3,#llist_next]               // init next pointer in next address
    b 100f
99:                                       // error
    mov x0,-1
100:
    ldp x2,x3,[sp],16                     // restaur  2 registers
    ldp x1,lr,[sp],16                     // restaur  2 registers
    ret                                   // return to address lr x30
/********************************************************/
/*        File Include fonctions                        */
/********************************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"

ACL2

The standard list data type is a singly linked list. 

(defun traverse (xs)
   (if (endp xs)
       (cw "End.~%")
       (prog2$ (cw "~x0~%" (first xs))
               (traverse (rest xs)))))

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="4"
TYPE ListNode=[INT data PTR nxt]

ListNode POINTER listBegin

PTR FUNC FindLast()
  ListNode POINTER last
  
  last=listBegin
  IF last=0 THEN
    RETURN (0)
  FI
  WHILE last.nxt#0
  DO
    last=last.nxt
  OD
RETURN (last)

PROC Append(INT v)
  ListNode POINTER n,last

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

PROC Clear()
  ListNode POINTER n,next

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

PROC Traverse()
  ListNode POINTER n

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

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

  FOR i=0 TO 50
  DO
    Append(i*i)
  OD
  Traverse()

  Clear()
RETURN
Output:

Screenshot from Atari 8-bit computer 

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)

ActionScript

See Singly-Linked List (element) in ActionScript 

var A:Node;
//...
for(var i:Node = A; i != null; i = i.link)
{
	doStuff(i);
}

Ada

The Ada standard container library provides a doubly-linked list. List traversal is demonstrated for the forward links. 

with Ada.Containers.Doubly_Linked_Lists;
with Ada.Text_Io; use Ada.Text_Io;

procedure Traversal_Example is
   package Int_List is new Ada.Containers.Doubly_Linked_Lists(Integer);
   use Int_List;
   procedure Print(Position : Cursor) is
   begin
      Put_Line(Integer'Image(Element(Position)));
   end Print;
   The_List : List;
begin
   for I in 1..10 loop
      The_List.Append(I);
   end loop;
   -- Traverse the list, calling Print for each value
   The_List.Iterate(Print'access);
end traversal_example;

ALGOL 68

Works with: ALGOL 68 version Revision 1 - no extensions to language used
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny
Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d

Linked lists are not built into ALGOL 68 per se, nor any available standard library. However Linked lists are presented in standard text book examples. Or can be manually constructed, eg: 

MODE STRINGLIST = STRUCT(STRING value, REF STRINGLIST next);

STRINGLIST list := ("Big",
  LOC STRINGLIST := ("fjords",
    LOC STRINGLIST := ("vex",
      LOC STRINGLIST := ("quick",
        LOC STRINGLIST := ("waltz",
          LOC STRINGLIST := ("nymph",NIL))))));

REF STRINGLIST node := list;
WHILE node ISNT REF STRINGLIST(NIL) DO
  print((value OF node, space));
  node := next OF node
OD;
print(newline)
Output:
Big fjords vex quick waltz nymph

ALGOL W 

begin
    % record type to hold a singly linked list of integers                    %
    record ListI ( integer iValue; reference(ListI) next );

    % inserts a new value after the specified element of a list               %
    procedure insert( reference(ListI) value list
                    ; integer          value newValue
                    ) ;
        next(list) := ListI( newValue, next(list) );

    % declare variables to hold the list                                      %
    reference(ListI) head, pos;

    % create a list of integers                                               %
    head := ListI( 1701, ListI( 9000, ListI( 42, ListI( 90210, null ) ) ) );

    % insert a new value into the list                                        %
    insert( next(head), 4077 );

    % traverse the list                                                       %
    pos := head;

    while pos not = null do begin
        write( iValue(pos) );
        pos := next(pos);
    end;

end.
Output:
          1701  
          9000  
          4077  
            42  
         90210

ARM Assembly

Works with: as version Raspberry Pi
/* ARM assembly Raspberry PI  */
/*  program afficheList.s   */

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

.equ NBELEMENTS,      100              @ list size

/*******************************************/
/* Structures                               */
/********************************************/
/* structure linkedlist*/
    .struct  0
llist_next:                            @ next element
    .struct  llist_next + 4 
llist_value:                           @ element value
    .struct  llist_value + 4 
llist_fin:
/* Initialized data */
.data
szMessInitListe:         .asciz "List initialized.\n"
szCarriageReturn:        .asciz "\n"
/* datas error display */
szMessErreur:            .asciz "Error detected.\n"
/* datas message display */
szMessResult:            .ascii "Element No :"
sNumElement:             .space 12,' '
                         .ascii " value :  "
sValue:                  .space 12,' '
                         .asciz "\n"

/* UnInitialized data */
.bss 
lList1:              .skip llist_fin * NBELEMENTS    @ list memory place 
/*  code section */
.text
.global main 
main: 
    ldr r0,iAdrlList1
    mov r1,#0                           @ list init
    str r1,[r0,#llist_next]
    ldr r0,iAdrszMessInitListe
    bl affichageMess
    ldr r0,iAdrlList1
    mov r1,#2
    bl insertElement                    @ add element value 2
    ldr r0,iAdrlList1
    mov r1,#5
    bl insertElement                    @ add element value 5
    @                                   @ display elements of list
    ldr r3,iAdrlList1
    mov r2,#0                           @ ident element
1:
    ldr r0,[r3,#llist_next]             @ end list ?
    cmp r0,#0
    beq 100f                            @ yes
    add r2,#1
    mov r0,r2                           @ display No element and value
    ldr r1,iAdrsNumElement
    bl conversion10S
    ldr r0,[r3,#llist_value]
    ldr r1,iAdrsValue
    bl conversion10S
    ldr r0,iAdrszMessResult
    bl affichageMess
    ldr r3,[r3,#llist_next]             @ next element
    b 1b                                @ and loop
100:                                    @ standard end of the program
    mov r7, #EXIT                       @ request to exit program
    svc 0                               @ perform system call
iAdrszMessInitListe:       .int szMessInitListe
iAdrszMessErreur:          .int szMessErreur
iAdrszCarriageReturn:      .int szCarriageReturn
iAdrlList1:                .int lList1
iAdrszMessResult:          .int szMessResult
iAdrsNumElement:           .int sNumElement
iAdrsValue:                .int sValue

/******************************************************************/
/*     insert element at end of list                          */ 
/******************************************************************/
/* r0 contains the address of the list */
/* r1 contains the value of element  */
/* r0 returns address of element or - 1 if error */
insertElement:
    push {r1-r3,lr}                       @ save  registers 
    mov r2,#llist_fin * NBELEMENTS
    add r2,r0                             @ compute address end list
1:                                        @ start loop 
    ldr r3,[r0,#llist_next]               @ load next pointer
    cmp r3,#0                             @ = zero
    movne r0,r3                           @ no -> loop with pointer
    bne 1b
    add r3,r0,#llist_fin                  @ yes -> compute next free address
    cmp r3,r2                             @ > list end 
    movge r0,#-1                          @ yes -> error
    bge 100f
    str r3,[r0,#llist_next]               @ store next address in current pointer
    str r1,[r0,#llist_value]              @ store element value
    mov r1,#0
    str r1,[r3,#llist_next]               @ init next pointer in next address

100:
    pop {r1-r3,lr}                        @ restaur registers
    bx lr                                 @ return
/******************************************************************/
/*     display text with size calculation                         */ 
/******************************************************************/
/* r0 contains the address of the message */
affichageMess:
    push {r0,r1,r2,r7,lr}                       @ save  registers 
    mov r2,#0                                   @ counter length */
1:                                              @ loop length calculation
    ldrb r1,[r0,r2]                             @ read octet start position + index 
    cmp r1,#0                                   @ if 0 its over
    addne r2,r2,#1                              @ else add 1 in the length
    bne 1b                                      @ and loop 
                                                @ so here r2 contains the length of the message 
    mov r1,r0                                   @ address message in r1 
    mov r0,#STDOUT                              @ code to write to the standard output Linux
    mov r7, #WRITE                              @ code call system "write" 
    svc #0                                      @ call system
    pop {r0,r1,r2,r7,lr}                        @ restaur registers
    bx lr                                       @ return
/***************************************************/
/*  Converting a register to a signed decimal      */
/***************************************************/
/* r0 contains value and r1 area address    */
conversion10S:
    push {r0-r4,lr}       @ save registers
    mov r2,r1             @ debut zone stockage
    mov r3,#'+'           @ par defaut le signe est +
    cmp r0,#0             @ negative number ? 
    movlt r3,#'-'         @ yes
    mvnlt r0,r0           @ number inversion
    addlt r0,#1
    mov r4,#10            @ length area
1:                        @ start loop
    bl divisionpar10U
    add r1,#48            @ digit
    strb r1,[r2,r4]       @ store digit on area
    sub r4,r4,#1          @ previous position
    cmp r0,#0             @ stop if quotient = 0
    bne 1b	

    strb r3,[r2,r4]       @ store signe 
    subs r4,r4,#1         @ previous position
    blt  100f             @ if r4 < 0 -> end

    mov r1,#' '           @ space
2:
    strb r1,[r2,r4]       @store byte space
    subs r4,r4,#1         @ previous position
    bge 2b                @ loop if r4 > 0
100: 
    pop {r0-r4,lr}        @ restaur registers
    bx lr  
/***************************************************/
/*   division par 10   unsigned                    */
/***************************************************/
/* r0 dividende   */
/* r0 quotient    */
/* r1 remainder   */
divisionpar10U:
    push {r2,r3,r4, lr}
    mov r4,r0                                          @ save value
    //mov r3,#0xCCCD                                   @ r3 <- magic_number lower  raspberry 3
    //movt r3,#0xCCCC                                  @ r3 <- magic_number higter raspberry 3
    ldr r3,iMagicNumber                                @ r3 <- magic_number    raspberry 1 2
    umull r1, r2, r3, r0                               @ r1<- Lower32Bits(r1*r0) r2<- Upper32Bits(r1*r0) 
    mov r0, r2, LSR #3                                 @ r2 <- r2 >> shift 3
    add r2,r0,r0, lsl #2                               @ r2 <- r0 * 5 
    sub r1,r4,r2, lsl #1                               @ r1 <- r4 - (r2 * 2)  = r4 - (r0 * 10)
    pop {r2,r3,r4,lr}
    bx lr                                              @ leave function 
iMagicNumber:  	.int 0xCCCCCCCD

ATS

I repeated the ‘Rosetta Code linear list type’ here, so you can simply copy the code below, compile it, and run it.

Also I put the executable parts in initialization rather than the main program, to avoid being forced to ‘consume’ the list (free its memory). I felt that would be a distraction.

The traversal function is proven to terminate. 

(*------------------------------------------------------------------*)

(* The Rosetta Code linear list type can contain any vt@ype.
   (The ‘@’ means it doesn’t have to be the size of a pointer.
   You can read {0 <= n} as ‘for all non-negative n’. *)
dataviewtype rclist_vt (vt : vt@ype+, n : int) =
| rclist_vt_nil (vt, 0)
| {0 <= n} rclist_vt_cons (vt, n + 1) of (vt, rclist_vt (vt, n))

(* A lemma one will need: lists never have negative lengths. *)
extern prfun {vt : vt@ype}
lemma_rclist_vt_param
          {n : int}
          (lst : !rclist_vt (vt, n)) :<prf> [0 <= n] void

(* Proof of the lemma. *)
primplement {vt}
lemma_rclist_vt_param lst =
  case+ lst of
  | rclist_vt_nil () => ()
  | rclist_vt_cons _ => ()

(*------------------------------------------------------------------*)

(* For simplicity, the Rosetta Code linear list traverse-and-print
   routine will be specifically for lists of ‘int’. *)

(* Some things that will be needed. *)
#include "share/atspre_staload.hats"

(* The list is passed by value and will be preserved with the same
   type. *)
extern fun
rclist_int_traverse_and_print
          {m   : int}                   (* ‘for all list lengths m’ *)
          (lst : !rclist_vt (int, m) >> (* ! = pass by value *)
                   (* The new type will be the same as the old
                      type. *)
                   rclist_vt (int, m)) : void

implement
rclist_int_traverse_and_print {m} (lst) =
  {
    (* A recursive nested function that traverses the list, printing
       elements along the way. *)
    fun
    traverse {k : int | 0 <= k}
             .<k>. (* Means: ‘k must uniformly decrease towards zero.’
                      If so, that is proof that ‘find’ terminates. *)
             (lst : !rclist_vt (int, k) >> rclist_vt (int, k)) :
        void =
      case+ lst of
      | rclist_vt_nil () => ()  (* End of list. *)
      | rclist_vt_cons (head, tail) =>
        begin
          println! (head);
          traverse tail
        end

    (* The following is needed to prove that the initial k above
       satisfies 0 <= k. *)
    prval _ = lemma_rclist_vt_param lst

    val _ = traverse lst
  }

(* Now let’s try it. *)

(* Some convenient notation. *)
#define NIL rclist_vt_nil ()
#define :: rclist_vt_cons
overload traverse_and_print with rclist_int_traverse_and_print

val A = 123
val B = 789
val C = 456

val lst = A :: C :: B :: NIL

val () = traverse_and_print lst

(*------------------------------------------------------------------*)

implement
main0 () = ()
Output:
$ patscc -DATS_MEMALLOC_LIBC singly_linked_list_traversal.dats && ./a.out
123
456
789

AutoHotkey 

a = 1
a_next = b
b = 2
b_next = c
c = 3

traverse("a")
return

traverse(element)
{
  MsgBox % element . "= " . %element%
  name := element . "_next"
  while, %name%
  {
  element := %name%
  msgbox % %name% . "= " . %element%
  name := %name% . "_next"
  }
}

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

BASIC

BBC BASIC

Works with: BBC BASIC for Windows
      DIM node{pNext%, iData%}
      DIM a{} = node{}, b{} = node{}, c{} = node{}
      
      a.pNext% = b{}
      a.iData% = 123
      b.iData% = 789
      c.iData% = 456
      
      PROCinsert(a{}, c{})
      
      PRINT "Traverse list:"
      pnode% = a{}
      REPEAT
        !(^node{}+4) = pnode%
        PRINT node.iData%
        pnode% = node.pNext%
      UNTIL pnode% = 0
      
      END
      
      DEF PROCinsert(here{}, new{})
      new.pNext% = here.pNext%
      here.pNext% = new{}
      ENDPROC
Output:
Traverse list:
       123
       456
       789

C

See Singly-Linked List (element) in C. 

struct link *first;
// ...
struct link *iter;
for(iter = first; iter != NULL; iter = iter->next) {
  // access data, e.g. with iter->data
}

C#

Uses the generic version of the node type located here. 

var current = [head of list to traverse]
while(current != null)
{
    // Do something with current.Value.

    current = current.Next;
}

Alternatively, as a for loop: 

for (var current = [head of list to traverse]; current != null; current = current.Next)
{
    // Do something with current.Value.
}

C++

Works with: C++11

For each traversal version. 

#include <iostream>
#include <forward_list>

int main()
{
    std::forward_list<int> list{1, 2, 3, 4, 5};
    for (int e : list)
        std::cout << e << std::endl;
}

Clojure 

(doseq [x xs] (println x))

Common Lisp 

(dolist (x list)
  (print x))

Using LOOP: 

(loop for x in list do (print x))

Using MAPC 

(mapc #'print list)

Using MAP 

(map nil #'print list)


Not using builtin list iteration: 

(loop for ref = list then (rest ref)
      until (null ref)
      do (print (first ref)))

Computer/zero Assembly

A linked list can be implemented as a chain of CONS cells, where each cell is made up of two neighbouring memory locations: the CAR, storing an item of data, and the CDR, storing the address of the next cell in the list. The CDR of the last cell contains not an address but a special NIL value that is guaranteed not to be a valid address; in this implementation, we use 0 to represent NIL. The order of CONS cells in memory is of course entirely unimportant. For the sake of example, this program traverses the list '(1 2 3 4 5 6) and halts with the final value in the accumulator. The program is reasonably straightforward, but it does make some use of instruction arithmetic (self-modifying code). 

start:  LDA  load
        ADD  car   ; head of list
        STA  ldcar

        ADD  one
        STA  ldcdr

ldcar:  NOP
        STA  value

ldcdr:  NOP
        BRZ  done  ; 0 == NIL
        STA  car

        JMP  start

done:   LDA  value
        STP

load:   LDA  0
value:       0
car:         28    ; head of list
one:         1

20,21:       6, 0
22,23:       2, 26
24,25:       5, 20
26,27:       3, 30
28,29:       1, 22
30,31:       4, 24

D 

struct SLinkedNode(T) {
    T data;
    typeof(this)* next;
}

void main() {
    import std.stdio;

    alias N = SLinkedNode!int;
    auto lh = new N(1, new N(2, new N(3, new N(4))));

    for (auto p = lh; p; p = p.next)
        write(p.data, " ");
    writeln();
}
Output:
1 2 3 4

Alternative Version

Using tango's collections (written by Doug Lea, ported to D): 

import tango.io.Stdout;
import tango.util.collection.LinkSeq;

void main() {
    auto m = new LinkSeq!(char[]);
    m.append("alpha");
    m.append("bravo");
    m.append("charlie");
    foreach (val; m)
        Stdout(val).newline;
}

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

Dyalect

Dyalect doesn't support linked lists out of the box, but it is fairly simple to implement one: 

type List = Cons(value, tail) or Nil()
    with Lookup
 
static func List.FromArray(xs) {
    var list = List.Nil()
    var len = xs.Length()
 
    for i in (len-1)^-1..0 {
        list = List.Cons(xs[i], list)
    }
 
    return list
}
 
func List.Iterate() {
    var xs = this
    do {
        match xs {
            Cons(value, tail) => {
                yield value
                xs = tail
            },
            Nil() => {
                yield break
            }
        }
 
    } while true
}
 
var xs = List.FromArray([1..10])
 
for x in xs {
    print(x)
}

It is also possible to provide an ad hoc solution to the problem:

Translation of: E
var xs = (1, (2, (3, (4, (5, (6, (7, (8, (9, (10, nil))))))))))

while xs is (value, tail) {
    print(value)
    xs = tail
}

Here a linked list is emulated using tuples.

E

Using a list made from tuples: 

var linkedList := [1, [2, [3, [4, [5, [6, [7, null]]]]]]]

while (linkedList =~ [value, next]) {
    println(value)
    linkedList := next
}

Using a list made from the structure defined at Singly-Linked List (element): 

var linkedList := makeLink(1, makeLink(2, makeLink(3, empty)))

while (!(linkedList.null())) {
    println(linkedList.value())
    linkedList := linkedList.next()
}

EchoLisp

Lists - linked-lists - are the fundamental data type in EchoLisp. A lot of fuctions exist to scan lists or operate on successive elements. 

(define friends '( albert ludwig elvis 🌀))

(for-each write friends)→  albert ludwig elvis 🌀

; for loop
(for ((friend friends)) (write friend)) → albert ludwig elvis 🌀

; map a function
(map string-upcase friends)  → ("ALBERT" "LUDWIG" "ELVIS" "🌀")
(map string-randcase friends) → ("ALBerT" "LudWIG" "elVis" "🌀")

; recursive way
(define (rscan L)
    (unless (null? L) 
        (write (first L)) 
         (rscan (rest L))))

(rscan friends)  →  albert ludwig elvis 🌀

; folding a list
; check that ∑ 1..n = n (n+1)/2

(define L (iota 1001))
(foldl + 0 L) → 500500 ; 1000 * 1001 / 2

Ela 

traverse [] = []
traverse (x::xs) = x :: traverse xs

This function traverses a list and constructs a new list at the same time. For a list in Ela it is the same as identity function, e.g. traverse [1,2,3] == [1,2,3]. However it can be useful in some cases. For example, to enforce a lazy list: 

xs = [& x \\ x <- [1..1000]]//lazy list

traverse xs

Elena

Simple iteration with a while loop. 

while(nil != current){ 
    console printLine(current.Item);
    current := current.Next
}

Erlang

Use built in functions like lists:map/2 and lists:foldl/3. 

1> lists:map( fun erlang:is_integer/1, [1,2,3,a,b,c] ).
[true,true,true,false,false,false]
4> lists:foldl( fun erlang:'+'/2, 0, [1,2,3] ).
6

Factor 

: list-each ( linked-list quot: ( data -- ) -- )
    [ [ data>> ] dip call ]
    [ [ next>> ] dip over [ list-each ] [ 2drop ] if ] 2bi ; inline recursive

SYMBOLS: A B C ;

A <linked-list>
[ C <linked-list> list-insert ] keep
[ B <linked-list> list-insert ] keep

[ . ] list-each
Output:
A
B
C

Fantom

Using the definitions from Singly-Linked_List_(element_insertion): 

    // traverse the linked list
    Node? current := a
    while (current != null)
    {
      echo (current.value)
      current = current.successor
    }

Forth 

: last ( list -- end )
  begin dup @ while @ repeat ;

And here is a function to walk a list, calling an XT on each data cell: 

: walk ( a xt -- )
   >r begin ?dup while
     dup cell+ @ r@ execute
   @ repeat r> drop ;

Testing code: 

A ' emit walk ABC ok

Fortran

Fortran 95. See Singly-Linked List (element) in Fortran. 

subroutine traversal(list,proc)
   type(node), target    :: list
   type(node), pointer   :: current
   interface
      subroutine proc(node)
         real, intent(in) :: node
      end subroutine proc
   end interface
   current => list
   do while ( associated(current) )
      call proc(current%data)
      current => current%next
   end do
end subroutine traversal

Print data from all nodes of a singly-linked list: 

subroutine printNode(data)
   real, intent(in)  :: data
   write (*,*) data
end subroutine

subroutine printAll(list)
   type(node), intent(in)  :: list
   call traversal(list,printNode)
end subroutine printAll

FreeBASIC

Requires the type definition and node insertion routine here and here respectively. Also includes a routine for allocating space for a node. 

#define NULL 0

function alloc_ll_int( n as integer ) as ll_int ptr
    dim as ll_int ptr ret = allocate(sizeof(ll_int))
    ret->n = n
    ret->nxt = NULL
    return ret
end function

sub traverse_ll_int( head as ll_int ptr )
    dim as ll_int ptr curr = head
    while curr <> NULL
        print curr->n
        curr = curr->nxt
    wend
end sub

dim as ll_int ptr curr, head = alloc_ll_int( 0 ), node
dim as integer i
curr=head
for i = 1 to 50
    'build a list to traverse. This is basically a traversal itself...
    node = alloc_ll_int( i )
    insert_ll_int( curr, node )
    curr = curr->nxt
next i

traverse_ll_int( head )

Go

See Singly-Linked List (element) in Go. 

start := &Ele{"tacos", nil}
end := start.Append("burritos")
end = end.Append("fajitas")
end = end.Append("enchilatas")
for iter := start; iter != nil; iter = iter.Next {
    fmt.Println(iter)
}

Haskell

Lists are ubiquitous in Haskell, simply use Haskell's map library function: 

map (>5) [1..10] -- [False,False,False,False,False,True,True,True,True,True]

map (++ "s") ["Apple", "Orange", "Mango", "Pear"] -- ["Apples","Oranges","Mangos","Pears"]

foldr (+) 0 [1..10] -- prints 55

traverse :: [a] -> [a]
traverse list = map func list
	where func a = -- ...do something with a

Note that the traverse function is polymorphic; denoted by traverse :: [a] -> [a] where a can be of any type.

Icon and Unicon

Using either the record or class-based definitions from Singly-Linked List (element) in Icon and Unicon: 

procedure main ()
  ns := Node(1, Node(2, Node (3)))
  until /ns do { # repeat until ns is null
    write (ns.value)
    ns := ns.successor
  }
end

Prints the numbers 1, 2, 3 in turn.

J

Using the implementation mentioned at Singly-Linked List (element) in J, we can apply a function foo to each node the following way: 

foo"0 {:"1 list

Java

Works with: Java version 1.5+

For Java.util.LinkedList<T>, use a for each loop (from Loop Structures): 

LinkedList<Type> list = new LinkedList<Type>();

for(Type i: list){
  //each element will be in variable "i"
  System.out.println(i);
}

Note that java.util.LinkedList can also perform as a stack, queue, or doubly-linked list.

JavaScript

Extending Singly-Linked_List_(element)#JavaScript 

LinkedList.prototype.traverse = function(func) {
    func(this);
    if (this.next() != null)
        this.next().traverse(func);
}

LinkedList.prototype.print = function() {
    this.traverse( function(node) {print(node.value())} );
}

var head = createLinkedListFromArray([10,20,30,40]);
head.print();

Uses the print() function from Rhino


Alternatively, translating the Haskell examples in terms of JavaScript's Array.map, Array.reduce, and Array.forEach: 

var map = function (fn, list) {
        return list.map(fn);
    },

    foldr = function (fn, acc, list) {
        var listr = list.slice();
        listr.reverse();

        return listr.reduce(fn, acc);
    },

    traverse = function (list, fn) {
        return list.forEach(fn);
    };

var range = function (m, n) {
    return Array.apply(null, Array(n - m + 1)).map(
        function (x, i) {
            return m + i;
        }
    );
};

//      --> [false, false, false, false, false, true, true, true, true, true]
map(function (x) {
    return x > 5;
}, range(1, 10));

//      --> ["Apples", "Oranges", "Mangos", "Pears"]
map(function (x) {
    return x + 's';
}, ["Apple", "Orange", "Mango", "Pear"])

//      --> 55
foldr(function (acc, x) {
    return acc + x;
}, 0, range(1, 10))


traverse(["Apple", "Orange", "Mango", "Pear"], function (x) {
    console.log(x);
})
/* Apple */
/* Orange */
/* Mango */
/* Pear */

Joy 

['a 'b 'c '\n] [putch] step.

jq

Works with: jq

Works with gojq, the Go implementation of jq

For context see Singly-linked_list/Element_definition#jq.

Here we define a "map" filter as well as a traversal filter. The "map" filter is similar to the built-in `map` in that it can be used to remove items as per the comment below. 

# Produce a stream of the items in the input SLL.
def items:
  while(.; .next) | .item;

def to_singly_linked_list(s):
  reduce ([s]|reverse[]) as $item (null; {$item, next:.});

# If f evaluates to empty at any item, that item is removed;
# if f evaluates to more than one item, all are added separately.
def map_singly_linked_list(f): to_singly_linked_list( items | f );

Examples 

{
  "item": 1,
  "next": {
    "item": 2,
    "next": null
  }
}
| reduce items as $item (null; .+$item),
  map_singly_linked_list(- .)
Output:
3
{
  "item": -1,
  "next": {
    "item": -2,
    "next": null
  }
}

Julia

Works with: Julia version 0.6

Julia let you implement list traversal very easily: see Singly-linked_list/Element_definition#Julia for the LinkedList struct definition. 

Base.start(ll::LinkedList) = ll.head
Base.done(ll::LinkedList{T}, st::AbstractNode{T}) where T = st isa EmptyNode
Base.next(ll::LinkedList{T}, st::AbstractNode{T}) where T = st.data, st.next

lst = LinkedList{Int}()
push!(lst, 1)
push!(lst, 2)
push!(lst, 3)

for n in lst
    print(n, " ")
end

Kotlin

Lists in Kotlin may be instanciated from Java classes or from Kotlin methods or extensions. 

fun main(args: Array<String>) {
    val list = IntRange(1, 50).toList()

    // classic traversal:
    for (i in list) { print("%4d ".format(i)); if (i % 10 == 0) println() }

    // list iterator:
    list.asReversed().forEach { print("%4d ".format(it)); if (it % 10 == 1) println() }
}
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

Limbo

Lists are a built-in type in Limbo. 

implement Command;

include "sys.m";
sys: Sys;

include "draw.m";

include "sh.m";

init(nil: ref Draw->Context, nil: list of string)
{
	sys = load Sys Sys->PATH;

	l := list of {1, 2, 3, 4, 5};

	# the unary 'tl' operator gets the tail of a list
	for (; l != nil; l = tl l)
		sys->print("%d\n", hd l);
		# the unary 'hd' operator gets the head of a list
}

LAST is already a Logo built-in, but it could be defined this way: 

to last :list
  if empty? bf :list [output first :list]
  output last bf :list
end

Logtalk

The built-in list type can be viewed as a singly linked list. Traversing can be trivially done using a tail-recursive predicate: 

:- object(singly_linked_list).

    :- public(show/0).

    show :-
        traverse([1,2,3]).

    traverse([]).
    traverse([Head| Tail]) :-
        write(Head), nl,
        traverse(Tail).

:- end_object.
Output:
| ?- singly_linked_list::show.
1
2
3
yes

Mathematica /Wolfram Language 

Print /@ {"rosettacode", "kitten", "sitting", "rosettacode",  "raisethysword"}
Output:
rosettacode
kitten
sitting
rosettacode
raisethysword

MATLAB / Octave

Matlab and Octave do not have pointers. Linked lists are implemented as vectors (i.e. arrays of size 1xN) 

list = 1:10; 
    for k=1:length(list)
        printf('%i\n',list(k))	
    end;

It is recommended to avoid loops and "vectorize" the code: 

  printf('%d\n', list(:));

MiniScript

We're choosing here to use the built-in list type, rather than make our own from scratch, since this is more representative of how one is likely to actually use MiniScript. 

myList = [2, 4, 6, 8]
for i in myList
    print i
end for
Output:
2
4
6
8

Nanoquery

Translation of: C

See Singly-Linked List (element) in Nanoquery. 

first = new(link)
//
for (iter = first) (iter != null) (iter = iter.next)
        println iter.data
end

NewLISP 

(dolist (x '(a b c d e))
  (println x))

Nim 

type Node[T] = ref object
  next: Node[T]
  data: T

proc newNode[T](data: T): Node[T] =
  Node[T](data: data)

var a = newNode 12
var b = newNode 13
var c = newNode 14

proc insertAppend(a, n: var Node) =
  n.next = a.next
  a.next = n

a.insertAppend(b)
b.insertAppend(c)

iterator items(a: Node) =
  var x = a
  while not x.isNil:
    yield x
    x = x.next

for item in a:
  echo item.data

Objeck 

for(node := head; node <> Nil; node := node->GetNext();) {
  node->GetValue()->PrintLine();
};

Objective-C

(See Singly-Linked List (element)) 

RCListElement *current;
for(current=first_of_the_list; current != nil; current = [current next] )
{
  // to get the "datum":
  // id dat_obj = [current datum];
}

OCaml 

# let li = ["big"; "fjords"; "vex"; "quick"; "waltz"; "nymph"] in
  List.iter print_endline li ;;
big
fjords
vex
quick
waltz
nymph
- : unit = ()

Odin 

package main

import "core:fmt"

Node :: struct {
	data: rune,
	next: ^Node,
}

insert_after :: proc(node, new_node: ^Node) {
  new_node.next = node.next
  node.next = new_node
}

main :: proc() {
  a := new(Node)
  a.data = 'A'

  b := new(Node)
  b.data = 'B'

  c := new(Node)
  c.data = 'C'

  insert_after(a, b) // A -> B
  insert_after(a, c) // A -> C -> B

  for n := a; n != nil; n = n.next {
	  fmt.print(n.data)
  } // prints: ACB
}

Oforth

See Singly-Linked List/Element_insertion in Oforth for the full class definition.

Because forEachNext is defined, a linked list responds to all methods defined for Collections : apply, map, filter, .... 

: testLink LinkedList new($A, null) dup add($B) dup add($C) ;
testLink apply(#println)
Output:
A
C
B

ooRexx

See Singly-Linked List/Element Definition in ooRexx for the full class definition. 

list=.list~of('A','B','X')
say "Manual list traversal"
index=list~first
loop while index \== .nil
    say list~at(index)
    index = list~next(index)
end

say
say "Do ... Over traversal"
do value over list
    say value
end
Output:
Manual list traversal
A
B
X

Do ... Over traversal
A
B
X

Pascal

See Delphi

Peloton

This makes a list of the Chinese Public Holiday and lists them first till last and then last till first. 

<@ LETCNSLSTLIT>public holidays|開國紀念日^和平紀念日^婦女節、兒童節合併假期^清明節^國慶日^春節^端午節^中秋節^農曆除夕</@>
<@ OMT>From First to Last</@>
<@ ITEFORSZELSTLIT>public holidays|
<@ SAYLST>...</@><@ ACTMOVFWDLST>...</@>
</@>
<@ OMT>From Last to First (pointer is still at end of list)</@>
<@ ITEFORSZELSTLIT>public holidays|
<@ SAYLST>...</@><@ ACTMOVBKWLST>...</@>
</@>

This variable length Simplified Chinese rendition of the same code is 

<# 指定构造列表字串>public holidays|開國紀念日^和平紀念日^婦女節、兒童節合併假期^清明節^國慶日^春節^端午節^中秋節^農曆除夕</#>
<# 忽略>From First to Last</#>
<# 迭代迭代次数结构大小列表字串>public holidays|
<# 显示列表>...</#><# 运行移位指针向前列表>...</#>
</#>
<# 忽略>From Last to First (pointer is still at end of list)</#>
<# 迭代迭代次数结构大小列表字串>public holidays|
<# 显示列表>...</#><# 运行移位指针向后列表>...</#>
</#>

Perl

We use Class::Tiny to get OO functionality with minimal effort. 

package SSL_Node;
use strict;
use Class::Tiny qw( val next );

sub BUILD {
    my $self = shift;
    exists($self->{val}) or die "Must supply 'val'";
    if (exists $self->{next}) {
        ref($self->{next}) eq 'SSL_Node'
            or die "If supplied, 'next' must be an SSL_Node";
    }
    return;
}

package main;
use strict;
# Construct an example list,
my @vals = 1 .. 10;
my $countdown = SSL_Node->new(val => shift(@vals));
while (@vals) {
    my $head = SSL_Node->new(val => shift(@vals), next => $countdown);
    $countdown = $head;
}
# ...then traverse it.
my $node = $countdown;
while ($node) {
    print $node->val, "... ";
    $node = $node->next;
}
print "\n";
Output:
10... 9... 8... 7... 6... 5... 4... 3... 2... 1...

Phix

See also Removal. 

with javascript_semantics
enum NEXT,DATA
constant empty_sll = {{NULL}}
sequence sll = deep_copy(empty_sll)
 
procedure insert_after(object data, integer pos=length(sll))
    sll = append(sll,{sll[pos][NEXT],data})
    sll[pos][NEXT] = length(sll)
end procedure
 
insert_after("ONE")
insert_after("TWO")
insert_after("THREE")
 
?sll
 
procedure show()
    integer idx = sll[1][NEXT]
    while idx!=NULL do
        ?sll[idx][DATA]
        idx = sll[idx][NEXT]
    end while
end procedure
show()
Output:
{{2},{3,"ONE"},{4,"TWO"},{0,"THREE"}}
"ONE"
"TWO"
"THREE"

PicoLisp

We might use map functions 

(mapc println '(a "cde" (X Y Z) 999))

or flow control functions 

(for X '(a "cde" (X Y Z) 999)
   (println X) )
Output:

for both cases 

a
"cde"
(X Y Z)
999

PL/I 

*process source attributes xref or(!);
 /*********************************************************************
 * 25.10.2013 Walter Pachl
 * 'set dd:in=d:\sll.txt,recsize(80)'
 * 'sll'
 *********************************************************************/
 sll: Proc Options(main);
 Dcl in       Record Input;
 Dcl sysprint Print;
 Dcl 1 elem Based(p),
      2 next Ptr Init(null()),
      2 value Char(20) Var;
 Dcl head Ptr;
 Dcl p    Ptr;
 Dcl prev Ptr;
 Dcl i    Bin Fixed(31);
 Dcl rec  Char(80) Var;
 Dcl null Builtin;
 On Endfile(in) goto show;
 Do i=1 By 1;
   Read File(in) Into(rec);
   alloc elem set(p);
   If i=1 Then Do;
     head=p;
     prev=head;
     value=rec;
     End;
   Else Do;
     prev->next=p;
     prev=p;
     value=rec;
     End;
   End;

 show:
   p=head;
   Do i=1 By 1 while(p^=null());
     Put Edit(i,p->value)(skip,f(3),x(1),a);
     p=p->next;
     End;
 End;
Output:
  1 Walter
  2 Pachl
  3 wrote
  4 this

PureBasic 

Procedure traverse(*node.MyData)
  While *node
    ;access data, i.e. PrintN(Str(*node\Value)) 
    *node = *node\next
  Wend
EndProcedure

;called using
traverse(*firstnode.MyData)

Python 

for node in lst:
    print node.value

Any Python class can define next() and __iter__() methods so that it can be used with the normal for iteration syntax. In this example the "lst" could be an instance of any Python list, tuple, dictionary, or any sort of object which defines an iterator. It could also be a generator (a type of function which yields results upon each successive invocation). The notion of a "singly linked list" is somewhat more primitive than normal Python built-in objects. 

class LinkedList(object):
  """USELESS academic/classroom example of a linked list implemented in Python.
     Don't ever consider using something this crude!  Use the built-in list() type!
  """
  def __init__(self, value, next):
    self.value = value;
    self.next = next
  def __iter__(self):
    node = self
    while node != None:
      yield node.value
      node = node.next;

lst = LinkedList("big",  next=
  LinkedList(value="fjords",next=
    LinkedList(value="vex",   next=
      LinkedList(value="quick", next=
        LinkedList(value="waltz", next=
          LinkedList(value="nymph", next=None))))));

for value in lst:
  print value,;
print
Output:
big fjords vex quick waltz nymph

Racket

Since singly-linked lists that are made of cons cells are one of the most common primitive types in Racket, there is a lot of built-in functionality that scans these lists: 

#lang racket

(define l (list 1 2 3))

;; scan the list and collect a list of function results
(map add1 l)

;; scan the list and run some function on each element for its side-effect
(for-each displayln l)

;; scan a list and sum up its elements
(foldl + 0 l)

;; same as the above three, using a more modern syntax that is often
;; more convenient
(for/list ([x (in-list l)]) (add1 x))
(for ([x (in-list l)]) (displayln x))
(for/fold ([sum 0]) ([x (in-list l)]) (+ x sum))

;; the same as the first, but make up a vector of results
(for/vector ([x (in-list l)]) (add1 x))

;; there is less support for mutable pairs, but it's still extensive
;; enough to cover all the basics
(require racket/mpair)
(define ml (mlist 1 2 3))
(mmap add1 ml)
(mfor-each displayln ml)
(for ([x (in-mlist ml)]) (displayln x))

Raku

(formerly Perl 6)

With Pair

Built-in list processing in Raku is not specifically based on singly-linked lists, but works at a higher abstraction level that encapsulates such implementation choices. Nonetheless, it's trivial to use the Pair type to build what is essentially a Lisp-style cons list, and in fact, the => pair constructor is right associative for precisely that reason. We traverse such a list here using a 3-part loop: 

my $list = 1 => 2 => 3 => 4 => 5 => 6 => Mu;

loop (my $l = $list; $l; $l.=value) {
    say $l.key;
}
Output:
1
2
3
4
5
6

It would be pretty easy to make such lists iterable as normal Raku lists, if anyone really cared to...

Well, shoot, let's just go ahead and do it. We'll pretend the Pair type is really a list type. (And we show how you turn an ordinary list into a cons list using a reduction. Note how the [=>] reduction is also right associative, just like the base operator.) 

use MONKEY-TYPING;
augment class Pair {
    method traverse () {
        gather loop (my $l = self; $l; $l.=value) {
            take $l.key;
        }
    }
}

my $list = [=>] 'Ⅰ' .. 'Ⅻ', Mu;
say ~$list.traverse;
Output:
Ⅰ Ⅱ Ⅲ Ⅳ Ⅴ Ⅵ Ⅶ Ⅷ Ⅸ Ⅹ Ⅺ Ⅻ

With custom type

Extending class Cell from Singly-linked_list/Element_definition#Raku: 

    method Seq {
        self, *.next ...^ !*
    }

Usage: 

my $list = (cons 10, (cons 20, (cons 30, Nil)));

for $list.Seq -> $cell {
    say $cell.value;
}
Output:
10
20
30

Retro 

: traverse ( l- ) repeat @ 0; again ;

Or, using combinators: 

last [ drop ] ^types'LIST each@

With combinators you can also perform an operation on each element in a linked list: 

last [ @d->name puts space ] ^types'LIST each@

REXX 

/* REXX ********************************************************************
* 25.10.2013 Walter Pachl
*********************************************************************/
in='d:\sll.txt'
Do i=1 By 1 while lines(in)>0
  rec=linein(in)
  elem.i.val=rec
  elem.i.next=0
  ip=i-1
  elem.ip.next=i
  End;
c=1
Do While c<>0
  Say c elem.c.val
  c=elem.c.next
  End

Ruby

referring to Singly-Linked List (element)#Ruby and Singly-Linked List (element insertion)#Ruby 

head = ListNode.new("a", ListNode.new("b", ListNode.new("c")))
head.insertAfter("b", "b+")

# then:
head.each {|node| print node.value, ","}
puts

# or
current = head
begin
  print current.value, ","
end while current = current.succ
puts
Output:
a,b,b+,c,
a,b,b+,c,

Run BASIC 

list$ = "now is the time for all good men"
for lnk = 1 to 8
 print lnk;"->";word$(list$,lnk)
next lnk
Output:
1->now
2->is
3->the
4->time
5->for
6->all
7->good
8->men

Rust

Extending Singly-Linked List (element)#Rust. Please see that page for the Linked List struct declarations.

In Rust, there are three ways to pass something: by value (which forfeits ownership), by reference (there can be infinitely many immutable references to an object), or by mutable reference (there may only be one mutable reference and no other immutable ones).

The following will demonstrate iteration all three ways. 

// 
//
// Iteration by value (simply empties the list as the caller now owns all values)
//
//
pub struct IntoIter<T>(List<T>);

impl<T> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.head.take().map(|node| { 
            let node = *node;
            self.0.head = node.next;
            node.elem
        })
    }
}

//
//
// Iteration by immutable reference
//
//

pub struct Iter<'a, T: 'a> {
    next: Option<&'a Node<T>>,
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        self.next.take().map(|node| {
            self.next = node.next.as_ref().map(|node| &**node);
            &node.elem
        })
    }
}

//
//
// Iteration by mutable reference
//
//

pub struct IterMut<'a, T: 'a> {
    next: Option<&'a mut Node<T>>,
}

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item> {
        self.next.take().map(|node| {
            self.next = node.next.as_mut().map(|node| &mut **node);
            &mut node.elem
        })
    }
}

//
//
// Methods implemented for List<T>
//
//

impl<T> List<T> {
    pub fn into_iter(self) -> IntoIter<T> {
        IntoIter(self)
    }

    pub fn iter<'a>(&'a self) -> Iter<'a,T> {
        Iter { next: self.head.as_ref().map(|node| &**node) }
    }

    pub fn iter_mut(&mut self) -> IterMut<T> {
        IterMut { next: self.head.as_mut().map(|node| &mut **node) }
    }

}

Scala

You can use pattern matching for traversing a list. 

/*
Here is a basic list definition

sealed trait List[+A]
case class Cons[+A](head: A, tail: List[A]) extends List[A]
case object Nil extends List[Nothing]
*/

def traverse[A](as: List[A]): Unit = as match {
  case Nil => print("End")
  case Cons(h, t) => {
    print(h + " ")
    traverse(t)
  }
}

Scheme 

(define (traverse seq func)
  (if (null? seq)
      '()
      (begin
        (func (car seq))
        (traverse (cdr seq) func))))

Sidef 

var list = 'a':'b':'c':nil;
#var list = ['a', ['b', ['c']]];
#var list = Pair.new('a', Pair.new('b', Pair.new('c', nil)));

for (var l = list; l != nil; l = l[1]) {
    say l[0];
}
Output:
a
b
c

SSEM

Linked lists are a comparatively easy data structure to implement in machine language, although the SSEM does not really have enough storage to make them practically useful. A linked list consists of any number of cons cells, i.e. pairs of successive words in storage where the first word holds a data item and the second holds either a pointer to the next pair or else a special nil value—represented here by 0, although any negative address would also work—indicating we have reached the end of the list. The pairs or cons cells can be scattered arbitrarily through the available storage space. This program traverses the list '(1 2 3), and halts with the last value in the accumulator. It makes some use of instruction arithmetic (self-modifying code). 

11101000000000100000000000000000   0. -23 to c
10011000000000010000000000000000   1. Sub. 25
10010000000001100000000000000000   2. c to 9
10101000000000010000000000000000   3. Sub. 21
11010000000001100000000000000000   4. c to 11
10010000000000100000000000000000   5. -9 to c
10010000000001100000000000000000   6. c to 9
11010000000000100000000000000000   7. -11 to c
11010000000001100000000000000000   8. c to 11
00000000000000000000000000000000   9. to be generated at run time
00101000000001100000000000000000  10. c to 20
00000000000000000000000000000000  11. to be generated at run time
00000000000000110000000000000000  12. Test
00011000000000000000000000000000  13. 24 to CI
10011000000001100000000000000000  14. c to 25
10011000000000100000000000000000  15. -25 to c
10011000000001100000000000000000  16. c to 25
01101000000000000000000000000000  17. 22 to CI
00101000000000100000000000000000  18. -20 to c
00000000000001110000000000000000  19. Stop
00000000000000000000000000000000  20. variable: negation of car
10000000000000000000000000000000  21. constant 1
11111111111111111111111111111111  22. constant -1
00000000000000100000000000000000  23. -0 to c
10001000000000000000000000000000  24. constant 17 (jump target)
00111000000000000000000000000000  25. 28 (pointer variable)
01000000000000000000000000000000  26. 2
01111000000000000000000000000000  27. pointer: 30
10000000000000000000000000000000  28. 1
01011000000000000000000000000000  29. pointer: 26
11000000000000000000000000000000  30. 3
00000000000000000000000000000000  31. 0 (nil)

SSEM programs can be difficult to take in: the constant negations, subtractions, and indirect jumps often obscure the underlying algorithm. To clarify what is going on, here is a pseudocode version of the same program: 

start:    load         loadZero
          add          pointer
          store        loadCar
          add          #1
          store        loadCdr
loadCar:  ; generated at run time
          store        value
loadCdr:  ; generated at run time
          branchOnZero end
          store        pointer
          jump         start
end:      load         value
          halt
value:            0 ; variable
loadZero: load         #0
pointer:          28

26 and 27:        (2 . 30)
28 and 29:        (1 . 26)
30 and 31:        (3 . 0)

Stata

See Singly-linked list/Element definition#Stata.

Tcl

Using the class definition from Singly-Linked List (element) (and bearing in mind the general notes on lists given there) we'll modify that class so that lists have an iteration method...

Works with: Tcl version 8.6
oo::define List {
    method for {varName script} {
        upvar 1 $varName var
        set elem [self]
        while {$elem ne ""} {
            set var [$elem value]
            uplevel 1 $script
            set elem [$elem next]
        }
    }
}

Now, a demonstration... 

set list {}
foreach n {1 3 5 7 2 4 6 8} {
    set list [List new $n $list]
}
$list for x {
    puts "we have a $x in the list"
}

Trith 

[1 2 3 4 5] [print] each

Visual Basic .NET 

Private Sub Iterate(ByVal list As LinkedList(Of Integer))
    Dim node = list.First
    Do Until node Is Nothing
        node = node.Next
    Loop
    End Sub

Wart 

each x '(1 2 3)
  prn x

Wren

Library: Wren-llist
Library: Wren-fmt
import "./llist" for LinkedList
import "./fmt" for Fmt

//create a new linked list and add the first 50 positive integers to it
var ll = LinkedList.new(1..50)

// traverse the linked list
for (i in ll) {
    Fmt.write("$4d ", i)
    if (i % 10 == 0) 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

XPL0 

def \Node\ Link, Data;          \linked list element definition
int Node, List;
[Node:= List;                   \traverse the linked list
while Node # 0 do
    Node:= Node(Link);          \move to next node
]

Yabasic 

// Rosetta Code problem: http://rosettacode.org/wiki/Singly-linked_list/Element_insertion & removal & traverse
// by Galileo, 02/2022

FIL = 1 : DATO = 2 : LINK = 3
countNodes = 0 : Nodes = 10

dim list(Nodes, 3)


sub searchNode(node)
    local i, prevNode
    
    for i = 1 to countNodes
        if i = node break
        prevNode = list(prevNode, LINK)
    next
    
    return prevNode
end sub

sub insertNode(node, newNode, after)
    local prevNode, i
    
    prevNode = searchNode(node)
    
    if after prevNode = list(prevNode, LINK)
    
    for i = 1 to Nodes
        if not list(i, FIL) break
    next
    
    list(i, FIL) = true
    list(i, DATO) = newNode
    list(i, LINK) = list(prevNode, LINK)
    list(prevNode, LINK) = i
    
    countNodes = countNodes + 1
    if countNodes = Nodes then Nodes = Nodes + 10 : redim list(Nodes, 3) : end if
end sub


sub removeNode(n)
    local prevNode, node
    
    prevNode = searchNode(n)
    node = list(prevNode, LINK)
    list(prevNode, LINK) = list(node, LINK)
    list(node, FIL) = false
    countNodes = countNodes - 1
end sub


sub printNode(node)
    local prevNode
    
    prevNode = searchNode(node)
    node = list(prevNode, LINK)
    print list(node, DATO);
    print
end sub


sub traverseList()
    local i
    
    for i = 1 to countNodes
        printNode(i)
    next
end sub


insertNode(1, 1000, true)
insertNode(1, 2000, true)
insertNode(1, 3000, true)

traverseList()

removeNode(2)

print
traverseList()
Output:
1000
3000
2000

1000
2000
---Program done, press RETURN---

Zig

Using the LinkedList struct definition from Singly-Linked List (element) 

const std = @import("std");

pub fn main() anyerror!void {
    var l1 = LinkedList(i32).init();

    try l1.add(1);
    try l1.add(2);
    try l1.add(4);
    try l1.add(3);

    var h = l1.head;

    while (h) |head| : (h = head.next) {
        std.log.info("> {}", .{ head.value });
    }
}
Output:
info: > 1
info: > 2
info: > 4
info: > 3

zkl 

foreach n in (List(1,2,3) {...}
List(1,2,3).pump(...) // traverse and munge elements, generalized apply/map
List(1,2,3).filter(...)
List(1,2,3).filter22(...) // partition list
List(1,2,3).reduce(...)
List(1,2,3).apply(...)
List(1,2,3).sum()
List(1,2,3).run()  // treat each element as f, perform f()
List(1,2,3).enumerate()
List(1,2,3).reverse()
List(1,2,3).concat()
List(1,2,3).shuffle()
Retrieved from "https://rosettacode.org/wiki/Singly-linked_list/Traversal?oldid=348569"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information