Follow a linked list

Question

For this challenge, a linked list looks like this:

[1, 2, 4, 0, 6, 1, 3, 1]

You'll notice there's no data; each item in the list is just a reference to the index of the next one. Your task is to write a program or function which will follow a linked list like this forever, outputting each item as it is encountered. For example, for the above input:

[1, 2, 4, 6, 3, 0, 1, ...]

Input and output can be represented in any reasonable manner. All numbers in the input will be valid indices in the list, and you can choose if it's 0- or 1-indexed. The output will be infinite, and as long as your program would theoretically give a correct result given infinite time and resources it's valid.

Test cases:

Zero indexed, using lists.

[0]         -> [0, 0, ...]
[1, 0]      -> [1, 0, 1, ...]
[0, 1, 2]   -> [0, 0, ...]
[2, 1, 0]   -> [2, 0, 2, ...]
[4]         -> (does not need to be handled)

Answer 1

convey, ³⁶ 29 bytes

v<<<<,{
\~./."
>"`=>!
 >!0<"}

Try it online!

{ gets the input, that will get looped around in the upper two rows, while outputting downwards the length \, its indices /. and a copy of itself ". It will only continue after ~. (batch) if n elements reach ~., whereas n will be the length.

We then take ! n copies of the current index i (starting with 0) and compare = them to the indices of the list. This returns either 1 or 0. We take the correspondent element of the copied list so many times, effectively filtering the others out. The next index then gets copied to the output "} and waits for the next iteration.

Answer 2

Haskell, 17 bytes

f x=iterate(x!!)0

0-indexed

Try it online!

Answer 3

Husk, 4 bytes

¡!¹←

Try it online!

1-indexed, returns an infinite list.

Explanation

¡!¹←
   ← take the first element as the start
¡    apply the following infinitely:
 !¹  index into the input

Answer 4

JavaScript (V8), 29 bytes

Zero-indexed. Prints forever. (Where forever means until the call stack overflow.)

f=a=>print(a.i=a[~~a.i])|f(a)

Try it online!

Commented

f = a =>       // f is a recursive function taking the input array a[]
  print(       // print:
    a.i =      //   update the current index, which is stored in the
               //   property 'i' of the surrounding object of a[]:
      a[~~a.i] //     it's initially undefined, so we use '~~' to coerce
               //     it to a number (zero) on the first iteration
  )            // end of print()
  | f(a)       // unconditional recursive call

The a.i trick saves 2 bytes over the more straightforward version:

f=(a,i=0)=>print(i=a[i])|f(a,i)

Try it online!

Answer 5

R, 35 32 bytes

-3 bytes thanks to Giuseppe.

function(l)repeat show(T<-l[+T])

Try it online!

1-indexed, prints the list indefinitely. A rare use for show, which is 1 byte shorter than print, and separates the output unlike cat.

The variable T is initially TRUE; +T converts it to the integer 1, and thereafter it is updated at each step to the relevant list entry.

Answer 6

Rattle, 11 bytes

|IP0[gpP~]0

Try it Online!

Update: changing link to new Rattle interpreter (please let me know if there are issues - I couldn't find any issues but this is a newer version of Rattle)

Explanation

|                  takes the user's input
  I                stores the user's input in an array
    P0             sets the pointer to 0
       [ ...... ]0 infinite loop
         g         gets the value at the pointer
           p       prints this value
             P~    sets the pointer to this value

Answer 7

05AB1E, 4 bytes

0[è=

0-based indexing.
Prints the numbers newline-delimited to STDOUT indefinitely.

Try it online or verify all test cases, but only printing the first 10 numbers of each.

Explanation:

0     # Start with index 0
 [    # Loop indefinitely:
  è   #  Use the current integer to index into the (implicit) input-list
   =  #  Print it with trailing newline (without popping, so it'll become the index for
      #  the next iteration)

Answer 8

dc, 29 28 bytes

[z1-:az0<L]dsLx0[;aplLx]dsLx

Try it online!

0-indexed; takes input on the stack (just prepend it). If we assume input is already in a, cut off the first 16 bytes. Will perish when the call stack overflows.

[ # Phase 1: shove stuff into an array
  z1-  # if there are 7 things on the stack, push 6
  :a   # store whatever was on top into e.g. a[6]
  z0<L # loop while stack isn't empty
]dsLx  # execute immediately and with extreme prejudice

0 # first index to check out
[ # Phase 2: the challenge
  ;a  # push a[tos]
  p   # print it
  lLx # loop forever
]dsLx # autobots, roll out

I feel like the 0!= should be reducible to 1> never mind, I just can't read. Woohoo!

Answer 9

APL (Dyalog Unicode), ¹² 11 bytes

{⍺∇⎕←⍵⌷⍺}∘0

Try it online!

0-indexed, takes input as the left argument.

-1 byte from user.

{⍺∇⎕←⍵⌷⍺}∘0
{⍺∇⎕←⍵⌷⍺}∘0 take 0 as initial right argument
   ⎕←⍺⌷⍵    print element at right arg
 ⍺∇ ⍵⌷⍺     recursive call with the input and new right arg

Answer 10

Whitespace, 89 bytes

[S S S T    N
_Push_1][S N
S _Duplicate_1][S N
S _Duplicate_1][S N
S _Duplicate_1][N
S S N
_Create_Label_READ_INPUT_LOOP][T    N
T   T   _Read_STDIN_as_integer][T   T   T   _Retrieve][N
T   S S N
_If_0_Jump_to_Label_DONE_READING][S S S T   N
_Push_1][T  S S S _Add][S N
S _Duplicate][S N
S _Duplicate][N
S N
N
_Jump_to_Label_READ_INPUT_LOOP][N
S S S N
_Create_Label_DONE_READING][S N
N
_Discard_top][N
S S T   N
_Create_Label_PRINT_LOOP][T T   T   _Retrieve_at_address][S N
S _Duplicate][T N
S T _Print_as_integer][S S S T  S S T   N
_Push_9_tab][T  N
S S _Print_as_character][N
S N
T   N
_Jump_to_Label_PRINT_LOOP]

Letters S (space), T (tab), and N (new-line) added as highlighting only.
[..._some_action] added as explanation only.

1-based indexing.
Whitespace doesn't have any lists, so we'll read the numbers one at a time from STDIN. Input numbers will end with a trailing 0, so the program knows when all the numbers are read from STDIN. I.e. test case [1,2,4,0,6,1,3,1] would be taken as input 2\n3\n5\n1\n7\n2\n4\n2\n0.
Outputs the numbers tab-delimited to STDOUT indefinitely.

Try it online (with raw spaces, tabs and new-lines only).

Explanation in pseudo-code:

Integer index = 1
Start READ_INPUT_LOOP:
  Read input as integer from STDIN, and store it in the heap at address `index`
  Integer input = retrieve the input from address `index`
  If(input == 0):
    Jump to DONE_READING
  index = index + 1
  Go to next iteration of READ_INPUT_LOOP

Label DONE_READING:
  Reset index to 1
  Start PRINT_LOOP:
    index = retrieve integer from heap at address `index`
    Print `index` as integer to STDOUT
    Print character '\t'
    Go to next iteration of PRINT_LOOP

Answer 11

Rust, 50 49 bytes

|a|(|mut i|loop{i=a[i];println!("{}",i)})(0usize)

Try it online!

Answer 12

CJam, 14 12 bytes

q~{_T=:Tp1}g

Input is taken from STDIN, 0-based, with format [1 2 4 0 6 1 3 1].

Output is printed to STDOUT, separated by newlines.

Try it online! Or verify test cases: 1, 2, 3, 4.

How it works

q               e# Read input as a string
 ~              e# Evaluate: gives the input as a list of numbers
  {       }g    e# Do...while, popping condition from the stack
         1      e# Push 1 at the end of each iteration, to produce an infinite loop
   _            e# Duplicate the input list
    T           e# Push variable T. This is initially 0
     =          e# Get entry at that index (0-based)
      :T        e# Assign the result to variable T
        p       e# Print with newline

Answer 13

Python 3.8 (pre-release), 37 34 bytes

def f(l,i=0):print(l[i]);f(l,l[i])

Try it online!

thanks user for helping save 3 bytes

slightly modified version of 31 bytes, but it prints an extra zero at the beginning

def f(l,i=0):print(i);f(l,l[i])

Try it online!

Answer 14

Julia 1.0, ²⁴ 21 bytes

>(a,i=1)=a>@show a[i]

Try it online!

1-indexed

Answer 15

PHP, 34 bytes

for($i=1;;)echo($i=$argv[$i])."
";

1-indexed, because $argv contains the script name at index 0, first argument is then $argv[1]. Too bad the new line takes a lots of bytes more, without it the brackets around $i=$argv[$i] are not necessary..

Try it online!

Answer 16

Java (JDK), 46 bytes

a->{for(int i=0;;)System.out.println(i=a[i]);}

Try it online!

Answer 17

C (gcc), 38 bytes

i;f(int*a){printf("%d ",i=a[i]);f(a);}

Try it online!

Answer 18

R, 31 bytes

Note that tests don't work, but print returns its input so we can recurse. Curiously this is different from cat and show which return NULL.

function(l,i=1)f(l,print(l[i]))

Try it online!

Answer 19

Bash, 51 50 bytes

f(){
A=($@)
I=0
while
I=${A[$I]}
do
echo $I
done
}

Try it online!

I was disappointed to find I could not use $@ as an array. I had to copy it to A.

The test code limits the output to 20 lines, and wraps it (or tries). Terminates only on signal, like SIGPIPE.

Edit: TIO seems to say I don't need the final newline. -1. Note that all my other newlines could become either spaces or semicolons, but I felt newlines had a better (weirder?) style in this case.

Answer 20

MATLAB and Octave, 20 bytes 32 bytes

(I've been informed that it is not allowed on this site to assume the input is an array, original answer below the line.)

@(x)eval('1,while 1,x(ans),end')

Thanks to Luis Mendo for this solution to make a function out of my original answer. It is two bytes shorter than the more obvious solution:

function f(x),1,while 1,x(ans),end

Try it online!

---

1,while 1,x(ans),end

1-indexed, the input is in matrix x. For example:

>> x = [1, 2, 4, 0, 6, 1, 3, 1] + 1;
>> 1,while 1,x(ans),end
ans =
     1
ans =
     2
ans =
     3
ans =
     5
ans =
     7
ans =
     4
ans =
     1
...

ans is the default variable expression results get assigned to. The code above is equivalent to:

ans = 1
while 1
   ans = x(ans)
end

The result of the assignment is shown to the command line because statements are not terminated with a semicolon.

Answer 21

Common Lisp, 44 bytes

(Function prints in the square bracket + comma style of most languages)

I used Common Lisp's format specifiers to handle all the control flow.

(defun f(l)(format t"[~{~a~:*~v@*~^, ~}]"l))

Example usage:

(defparameter *test* '(1 2 4 0 6 1 3 1))

(f *test*) ; Will print [1, 2, 4, 6, 3, 0, 1, ... and so forth forever.

Edit: Technically the ending square bracket would never be reached, so we may omit the closing square bracket in the format string to have a 43 byte solution.

Answer 22

Python 3, 49 37 bytes

Thanks to Jo King for -12 bytes!

def f(l,c=0):
 while 1:c=l[c];yield c

Try it online!

Original

def f(l):
    c=l[0]
    while 1:c = l[c];yield c

Try it online!

This code takes an input, sets c(which holds the index), then continuosly yields c after updating it to the new location. While this isn't the best answer on here, even for python, I don't think it can really be improved upon without using recursion. Clearly, I was wrong.

Answer 23

Batch, 94 bytes

@set n=0
:g
@call:c %*
@echo %n%
@goto g
:c
@for /l %%i in (1,1,%n%)do @shift
@set n=%1

Takes a 0-indexed list of command line arguments (change =0 to =1 and %1 to %0 for 1-indexing). The :c subroutine exists to shift a copy of the command line, thus avoiding destroying the command line. For short lists (up to 9 elements), the following 51-byte 1-indexed script suffices:

@set n=1
:g
@call set n=%%%n%
@echo %n%
@goto g

Answer 24

Perl 5 -a, 22 bytes

$_=$F[$_]while say$_*1

Try it online!

Input needs to be space separated.

Answer 25

Charcoal, 15 bytes

≔⁰ηＷ¹«≔§θηηＩηＤ⎚

Try it online! Link is to verbose version of code. 0-indexed. Charcoal rate-limits its output, so TIO will probably time out rather than fill its output buffer. Explanation:

≔⁰η

Start at index 0.

Ｗ¹«

Repeat forever.

≔§θηη

Update the index.

ＩηＤ⎚

Output the index, clearing the canvas for the next loop.

Answer 26

Retina 0.8.2, 39 bytes

(,)*(((?<-1>,)|\d+)+.*)
$3$*,$2,
}*`\G,

Try it online! 0-indexed. Explanation: The current index is encoded in unary as the number of leading ,s.

(,)*(((?<-1>,)|\d+)+.*)

Match the current index, then as many commas and integers as possible, but only matching as many commas as the current index. The last submatch is therefore the next index.

$3$*,$2,

Replace the current index with the submatch in unary, then append the original input and an extra comma to ensure that the buffer changes each time (since Retina 0.8.2 doesn't have truly infinite loops).

}`

Repeat until the buffer stops changing, which it won't because we append a comma to the end on each loop.

*`\G,

Convert the current index to decimal and print it.

Answer 27

k4, 17 13 bytes

{0W(0N!x@)/0}

Loops "infinitely" via 0W, outputting (0N!) the index in question. Begins with the first value in the input, i.e. x 0.

Answer 28

JQ, 37 bytes

[0,.]|recurse([.[1][.[0]],.[1]])|.[0]

Try it online!

Answer 29

Ruby, 27 23 bytes

Saved a whooping 4 bytes, thanks to Dingus!!

f=->a,i=0{f[a,p(a[i])]}

Try it online!

---

Ruby, 23 bytes

As suggested by Dingus, here is another way, and it prevents the "stack overflow" error!!

->a,i=0{loop{p i=a[i]}}

Try it online!

Answer 30

FALSE, 65 24 21 bytes

[c;[1_][ø$.32,c;\-]#]

Try it online! Assumes that array is already pushed onto stack and len(array)-1 is stored in c.

-41 because Razetime pointed out that I could just submit a function instead.

-3 because of removed redundancy.

Explanation

[c; {Push len(array) on stack for index 0}
[1_] {Value for true}
[ø {Get value at current index}
$. {Dup and print int}
32, {Print space}
c;\- {Subtract c by this new value to get new index}
]#] {Do lambda 2 while lambda 1 outputs true (forever)}