Disentangle doubly linked data

Question

A doubly linked list is a data structure in which each node has a value as well as "links" to both the previous and next nodes in the list. For example, consider the following nodes with values 12, 99, and 37:

Here, the nodes with values 12 and 99 point to their respective next nodes, with values 99 and 37. The node with value 37 has no next pointer because it's the last node in the list. Likewise, the nodes with values 99 and 37 point to their respective previous nodes, 12 and 99, but 12 has no previous pointer because it's the first node in the list.

The setup

In practice, a node's "links" are implemented as pointers to the previous and next node's locations in memory. For our purposes, the "memory" will be an array of nodes and a node's location will be its index in the array. A node can be thought of as a 3-tuple of the form ( prev value next ). The above example, then, might look like this:

But it might look like this, instead:

Starting at any node, you can follow previous links (shown as the origins of the red arrows) to get to the nodes that precede it and next links (green arrows) to find subsequent nodes in order to get all of the nodes' values in order: [12, 99, 37].

The first diagram above could be represented in an array as [[null, 12, 1], [0, 99, 2], [1, 37, null]]. The second, then, would be [[2, 99, 1], [0, 37, null], [null, 12, 0]].

The challenge

Write a program that takes as input an array of nodes and the index of a node and returns, in list order, the values of the nodes in the same doubly linked list.

A complication

The "memory" won't always contain the nodes of just one list. It might contain several lists:

The above array contains three doubly linked lists, color-coded for your convenience:

1. The nodes at indexes 7, 10, 1, 4, 3, 12 (showing only next links to reduce clutter; click to enlarge):

   

   Given this array and any of these indexes, your program should return, in order, the values [0, 1, 1, 2, 3, 5, 8].

2. The node at index 9:

   

   Given the index 9, your program should return [99].

3. The nodes at indexes 11, 8, 0, 6, 2:

   

   Given one of these indexes, it should return [2, 3, 5, 7, 11].

Rules

Input

Your program will receive as input:

1. A list of 𝒏 nodes (3-tuples as described above), where 1 ≤ 𝒏 ≤ 1,000, in any convenient format, e.g. an array of arrays, a "flat" array of integers with length 3𝒏, etc.

   The 3-tuples' elements may be in any order: ( prev value next ), ( next prev value ), etc. For each node, prev and next will be null (or another convenient value, e.g. -1), indicating the first or last node in a doubly linked list, or a valid index of the list, either 0- or 1-based as is convenient. value will be a signed 32-bit integer or the largest integer type your language supports, whichever is smaller.

2. The index 𝒑 of a node in the list (1). The indicated node may be the first node in a doubly linked list, the last node, a middle node, or even the only node.

The input list (1) may contain pathological data (e.g. cycles, nodes pointed to by multiple other nodes, etc.), but the input index (2) will always point to a node from which a single, well-formed output can be deduced.

Output

Your program should output the values of the nodes of the doubly linked list of which the node at index 𝒑 is a member, in list order. Output can be in any convenient format, but its data must include only the node values.

Winning

This is code-golf. Shortest answer in bytes wins. Standard loopholes apply.

Test cases

Below, each test case is of the form:

X)
prev value next, prev value next, ...
index
value value value ...

...where X is a letter to identify the test case, the second line is the input list, the third line is the 0-based input index, and the fourth line is the output.

A) null 12 1, 0 99 2, 1 37 null
   1
   12 99 37

B) 2 99 1, 0 37 null, null 12 0
   1
   12 99 37

C) 8 5 6, 10 1 4, 6 11 null, 4 3 12, 1 2 3, 12 8 null, 0 7 2, null 0 10, 11 3 0, null 99 null, 7 1 1, null 2 8, 3 5 5
   4
   0 1 1 2 3 5 8

D) 8 5 6, 10 1 4, 6 11 null, 4 3 12, 1 2 3, 12 8 null, 0 7 2, null 0 10, 11 3 0, null 99 null, 7 1 1, null 2 8, 3 5 5
   0
   2 3 5 7 11

E) 8 5 6, 10 1 4, 6 11 null, 4 3 12, 1 2 3, 12 8 null, 0 7 2, null 0 10, 11 3 0, null 99 null, 7 1 1, null 2 8, 3 5 5
   9
   99

F) 13 80 18, 18 71 null, 5 10 19, 12 1 8, 19 21 null, 31 6 2, 17 5 26, 26 0 30, 3 -1 25, null 1 23, 27 6 17, 14 1 24, 28 -1 3, null 80 0, 20 4 11, 33 6 29, 24 9 33, 10 7 6, 0 67 1, 2 15 4, 32 1 14, null 1 31, 29 3 null, 9 -1 28, 11 5 16, 8 1 null, 6 3 7, null 8 10, 23 1 12, 15 5 22, 7 9 null, 21 3 5, null 3 20, 16 2 15
   18
   80 80 67 71

G) 13 80 18, 18 71 null, 5 10 19, 12 1 8, 19 21 null, 31 6 2, 17 5 26, 26 0 30, 3 -1 25, null 1 23, 27 6 17, 14 1 24, 28 -1 3, null 80 0, 20 4 11, 33 6 29, 24 9 33, 10 7 6, 0 67 1, 2 15 4, 32 1 14, null 1 31, 29 3 null, 9 -1 28, 11 5 16, 8 1 null, 6 3 7, null 8 10, 23 1 12, 15 5 22, 7 9 null, 21 3 5, null 3 20, 16 2 15
   8
   1 -1 1 -1 1 -1 1

H) 13 80 18, 18 71 null, 5 10 19, 12 1 8, 19 21 null, 31 6 2, 17 5 26, 26 0 30, 3 -1 25, null 1 23, 27 6 17, 14 1 24, 28 -1 3, null 80 0, 20 4 11, 33 6 29, 24 9 33, 10 7 6, 0 67 1, 2 15 4, 32 1 14, null 1 31, 29 3 null, 9 -1 28, 11 5 16, 8 1 null, 6 3 7, null 8 10, 23 1 12, 15 5 22, 7 9 null, 21 3 5, null 3 20, 16 2 15
   4
   1 3 6 10 15 21

I) 13 80 18, 18 71 null, 5 10 19, 12 1 8, 19 21 null, 31 6 2, 17 5 26, 26 0 30, 3 -1 25, null 1 23, 27 6 17, 14 1 24, 28 -1 3, null 80 0, 20 4 11, 33 6 29, 24 9 33, 10 7 6, 0 67 1, 2 15 4, 32 1 14, null 1 31, 29 3 null, 9 -1 28, 11 5 16, 8 1 null, 6 3 7, null 8 10, 23 1 12, 15 5 22, 7 9 null, 21 3 5, null 3 20, 16 2 15
   14
   3 1 4 1 5 9 2 6 5 3

J) 13 80 18, 18 71 null, 5 10 19, 12 1 8, 19 21 null, 31 6 2, 17 5 26, 26 0 30, 3 -1 25, null 1 23, 27 6 17, 14 1 24, 28 -1 3, null 80 0, 20 4 11, 33 6 29, 24 9 33, 10 7 6, 0 67 1, 2 15 4, 32 1 14, null 1 31, 29 3 null, 9 -1 28, 11 5 16, 8 1 null, 6 3 7, null 8 10, 23 1 12, 15 5 22, 7 9 null, 21 3 5, null 3 20, 16 2 15
   17
   8 6 7 5 3 0 9

K) 4 11 0, null 22 3, null 33 3, 1 44 4, 3 55 null, 7 66 7, 6 77 6
   3
   22 44 55

L) null -123 null
   0
   -123

Answer 1

Haskell, 79 65 59 55 bytes

-6 bytes thanks to Brute Force.

x#i|let-1!d=[];i!d=i:x!!i!!d!d=[x!!i!!1|i<-last(i!0)!2]

Defines function # that accepts a list of lists of integers, where null is represented as -1, and returns list of node values.

Try it online!

Explanation

let-1!d=[];i!d=i:x!!i!!d!d

Define function ! that iterates through the nodes starting at node i and returns a list visited indexes. It accepts the second argument d that specifies which index of the "tuple" use as the index of the next node (d==2 to iterate forwards, d==0 to iterate backwards).

(i!0)

Iterate backwards starting from the given index and return visited indexes.

last(i!0)

Take last visited index, which is the beginning of the list.

last(i!0)!2

Iterate from the beginning of the list.

[x!!i!!1|i<-last(i!0)!2]

Replace each visited index with the value of the node.

Answer 2

Python 2, 60 bytes

l,n=input()
while~n:m=n;n=l[n][0]
while~m:p,v,m=l[m];print v

Try it online!

This is pretty much Chas Brown's answer, minus these golfs:

• I reuse n, saving an assignment
• I store the last valid n in m, allowing me to
• place the print after the assignment in line 3, saving me the final print
• I use only ~n instead of -~n, because negative values are just as truthy as positive ones, saving me 2 characters.

Answer 3

Clean, 94 90 88 bytes

import StdEnv
$l[_,u,v]|v<0=[u]=[u: $l(l!!v)]
?l= $l o until((>)0o hd)((!!)l o hd)o(!!)l

Try it online!

Answer 4

MATL, 39 bytes

XHx`HwI3$)t]x6Mt`Hwl3$)tbhwt]x4L)Hw2I$)

Try it online!

Almost a direct port of my Octave answer, but this version finds the end first, and then works it way back, rather than the other way round, which saved one byte.

XHx           % Store array in H.
`HwI3$)t]     % Work to the end of the array
x6Mt          % Delete the end of array delimiter, and push the array end index twice
`Hwl3$)    t] % Work to the beginning of the array
       tbhw   % Append all indices found.
Hw2I$)        % Index into original array.

Answer 5

05AB1E, 25 bytes

è[¬D0‹#Isè]\[`sˆD0‹#Isè]¯

Try it online!

Explanation

è[¬D0‹#Isè]\[`sˆD0‹#Isè]¯   # Arguments n, a
è                           # Get element at index n in a
 [¬D0‹#Isè]                 # Find the first element in the list
 [                          # While true, do
  ¬                         #   Head (get index of previous element)
   D0‹#                     #   Break if lower than 0
       Isè                  #   Get the element at that index
          ]                 # End loop
           \                # Delete top element of stack
            [`sˆD0‹#Isè]    # Iterate through list
            [               # While true, do
             `sˆ            #   Add value to global array and keep next index on stack
                D0‹#Isè     #   Same as above
                       ]    # End loop
                        ¯   # Push global array

Answer 6

PHP, 132 bytes

<?list(,$x,$y)=$argv;parse_str($x);while(($q=$x[$y*3+1])>=0)$y=$q;do{$n[]=$x[$y*3+2];$y=$x[$y*3];}while($x[$y*3]);echo join(' ',$n);

Try it online!

Input is taken as a querystring x[]=-1&x[]=1&x[]=1... (all nodes in a flat array), in the order of next, prev, then value for each node with -1 used for ending nodes.

Answer 7

Python 2, 81 77 bytes

a,n=input()
u=a[n][0]
while-~u:u,v,w=a[u]
while-~w:print v;u,v,w=a[w]
print v

Try it online!

EDIT: Thx to Mr. Xcoder for 4 bytes...

Takes a list of tuples [u,v,w] where u and w are -1 to represent the beginning/end of the linked list segment.

Answer 8

Octave, 81 78 76 bytes

function o=f(a,n)while q=a(n,1)o=a(n=q,2);end
while n=a(n,3)o=[o a(n,2)];end

Try it online!

Rather straightforward version. Explanation is left as an exercise to the reader. A much more fun version is presented below:

Octave, 142 99 92 bytes

@(a,n)[(p=@(b,c,z){q=a(z,2),@()[b(b,c,a(z,c)),q]}{2-~a(z,c)}())(p,1,n),p(p,3,n)(end-1:-1:1)]

Try it online!

Yo, I heard you liked anonymous functions...

Takes a nx3 array, with the first column the predecessor, second column the value, and third value the successor nodes. All the node indices are 1-based, which is the default in Octave.

% Create an anonymous function, taking an array a and first node n
@(a,n)
% Returns an array containing the predecessor and sucessor nodes
      [                                                                     ,                     ]
% Defines an recursive anonymous function (by supplying itself to the local namespace)
% which looks at the first column (c=1) or last column (c=3) of the input array to get the next nodes
       (p=@(p,c,z)                                                   )(p,1,n)
% Create a cell array, either containing the end node,
                    {q=a(z,2),                       
% ...or an array with all next  next nodes and the current node
% (note the use of an anonymous function taking no parameters to defer array access, in case of the last node)                
                              @()[p(p,c,a(z,c)),q]}
% depending whether the next node number is nonzero (followed by () to execute the deferred array access)
                                                    {2-~a(z,c)}()
% Do the same with c=3, reverse (function p builds the array right-to-left) and drop the current node to prevent a duplicate.                                                                             
                                                                             p(p,3,n)(end-1:-1:1)

Answer 9

Kotlin, 85 bytes

{g,S->generateSequence(generateSequence(S){g[it][0]}.last()){g[it][2]}.map{g[it][1]}}

Beautified

{g,S->
    generateSequence(generateSequence(S){g[it][0]}.last()){ g[it][2]}.map { g[it][1] }
}

Test

typealias Node=Triple<Int?,Int?,Int?>
data class Test(val input: List<Node>, val start:Int, val result: List<Int>)
val TEST = listOf<Test>(
Test(
listOf(Node(null, 12, 1), Node(0, 99, 2), Node(1, 37, null)),
1,
listOf(12, 99, 37)
),
Test(listOf(
Node(2, 99, 1), Node(0, 37, null), Node(null, 12, 0)),
1,
listOf(12, 99, 37)
),
Test(
listOf(Node(8, 5, 6), Node(10, 1, 4), Node(6, 11, null), Node(4, 3, 12), Node(1, 2, 3), Node(12, 8, null), Node(0, 7, 2), Node(null, 0, 10), Node(11, 3, 0), Node(null, 99, null), Node(7, 1, 1), Node(null, 2, 8), Node(3, 5, 5)),
4,
listOf(0, 1, 1, 2, 3, 5, 8)
),
Test(
listOf(Node(8, 5, 6), Node(10, 1, 4), Node(6, 11, null), Node(4, 3, 12), Node(1, 2, 3), Node(12, 8, null), Node(0, 7, 2), Node(null, 0, 10), Node(11, 3, 0), Node(null, 99, null), Node(7, 1, 1), Node(null, 2, 8), Node(3, 5, 5)),
0,
listOf(2, 3, 5, 7, 11)
),
Test(
listOf(Node(8, 5, 6), Node(10, 1, 4), Node(6, 11, null), Node(4, 3, 12), Node(1, 2, 3), Node(12, 8, null), Node(0, 7, 2), Node(null, 0, 10), Node(11, 3, 0), Node(null, 99, null), Node(7, 1, 1), Node(null, 2, 8), Node(3, 5, 5)),
9,
listOf(99)
),
Test(
listOf(Node(13, 80, 18), Node(18, 71, null), Node(5, 10, 19), Node(12, 1, 8), Node(19, 21, null), Node(31, 6, 2), Node(17, 5, 26), Node(26, 0, 30), Node(3, -1, 25), Node(null, 1, 23), Node(27, 6, 17), Node(14, 1, 24), Node(28, -1, 3), Node(null, 80, 0), Node(20, 4, 11), Node(33, 6, 29), Node(24, 9, 33), Node(10, 7, 6), Node(0, 67, 1), Node(2, 15, 4), Node(32, 1, 14), Node(null, 1, 31), Node(29, 3, null), Node(9, -1, 28), Node(11, 5, 16), Node(8, 1, null), Node(6, 3, 7), Node(null, 8, 10), Node(23, 1, 12), Node(15, 5, 22), Node(7, 9, null), Node(21, 3, 5), Node(null, 3, 20), Node(16, 2, 15)),
18,
listOf(80, 80, 67, 71)
),
Test(
listOf(Node(13, 80, 18), Node(18, 71, null), Node(5, 10, 19), Node(12, 1, 8), Node(19, 21, null), Node(31, 6, 2), Node(17, 5, 26), Node(26, 0, 30), Node(3, -1, 25), Node(null, 1, 23), Node(27, 6, 17), Node(14, 1, 24), Node(28, -1, 3), Node(null, 80, 0), Node(20, 4, 11), Node(33, 6, 29), Node(24, 9, 33), Node(10, 7, 6), Node(0, 67, 1), Node(2, 15, 4), Node(32, 1, 14), Node(null, 1, 31), Node(29, 3, null), Node(9, -1, 28), Node(11, 5, 16), Node(8, 1, null), Node(6, 3, 7), Node(null, 8, 10), Node(23, 1, 12), Node(15, 5, 22), Node(7, 9, null), Node(21, 3, 5), Node(null, 3, 20), Node(16, 2, 15)),
8,
listOf(1, -1, 1, -1, 1, -1, 1)
),
Test(
listOf(Node(13, 80, 18), Node(18, 71, null), Node(5, 10, 19), Node(12, 1, 8), Node(19, 21, null), Node(31, 6, 2), Node(17, 5, 26), Node(26, 0, 30), Node(3, -1, 25), Node(null, 1, 23), Node(27, 6, 17), Node(14, 1, 24), Node(28, -1, 3), Node(null, 80, 0), Node(20, 4, 11), Node(33, 6, 29), Node(24, 9, 33), Node(10, 7, 6), Node(0, 67, 1), Node(2, 15, 4), Node(32, 1, 14), Node(null, 1, 31), Node(29, 3, null), Node(9, -1, 28), Node(11, 5, 16), Node(8, 1, null), Node(6, 3, 7), Node(null, 8, 10), Node(23, 1, 12), Node(15, 5, 22), Node(7, 9, null), Node(21, 3, 5), Node(null, 3, 20), Node(16, 2, 15)),
4,
listOf(1, 3, 6, 10, 15, 21)
),
Test(
listOf(Node(13, 80, 18), Node(18, 71, null), Node(5, 10, 19), Node(12, 1, 8), Node(19, 21, null), Node(31, 6, 2), Node(17, 5, 26), Node(26, 0, 30), Node(3, -1, 25), Node(null, 1, 23), Node(27, 6, 17), Node(14, 1, 24), Node(28, -1, 3), Node(null, 80, 0), Node(20, 4, 11), Node(33, 6, 29), Node(24, 9, 33), Node(10, 7, 6), Node(0, 67, 1), Node(2, 15, 4), Node(32, 1, 14), Node(null, 1, 31), Node(29, 3, null), Node(9, -1, 28), Node(11, 5, 16), Node(8, 1, null), Node(6, 3, 7), Node(null, 8, 10), Node(23, 1, 12), Node(15, 5, 22), Node(7, 9, null), Node(21, 3, 5), Node(null, 3, 20), Node(16, 2, 15)),
14,
listOf(3, 1, 4, 1, 5, 9, 2, 6, 5, 3)
),
Test(
listOf(Node(13, 80, 18), Node(18, 71, null), Node(5, 10, 19), Node(12, 1, 8), Node(19, 21, null), Node(31, 6, 2), Node(17, 5, 26), Node(26, 0, 30), Node(3, -1, 25), Node(null, 1, 23), Node(27, 6, 17), Node(14, 1, 24), Node(28, -1, 3), Node(null, 80, 0), Node(20, 4, 11), Node(33, 6, 29), Node(24, 9, 33), Node(10, 7, 6), Node(0, 67, 1), Node(2, 15, 4), Node(32, 1, 14), Node(null, 1, 31), Node(29, 3, null), Node(9, -1, 28), Node(11, 5, 16), Node(8, 1, null), Node(6, 3, 7), Node(null, 8, 10), Node(23, 1, 12), Node(15, 5, 22), Node(7, 9, null), Node(21, 3, 5), Node(null, 3, 20), Node(16, 2, 15)),
17,
listOf(8, 6, 7, 5, 3, 0, 9)
),
Test(
listOf(Node(4, 11, 0), Node(null, 22, 3), Node(null, 33, 3), Node(1, 44, 4), Node(3, 55, null), Node(7, 66, 7), Node(6, 77, 6)),
3,
listOf(22, 44, 55)
),
Test(
listOf(Node(null, -123, null)),
0,
listOf(-123)
)
)

var f:(List<List<Int?>>,Int)-> Sequence<Int?> =
{g,S->generateSequence(generateSequence(S){g[it][0]}.last()){g[it][2]}.map{g[it][1]}}

fun main(args: Array<String>) {
    for ((input, start, result) in TEST) {
        val out = f(input.map { it.toList() }, start).toList()
        if (out != result) {
            throw AssertionError("$input $start $result $out")
        }
    }
}

TIO

TryItOnline

Answer 10

JavaScript ES6, 70 63 Bytes

(x,i,a)=>(h=_=>i&&h(a(x[i].v),i=x[i].n))(x.map(_=>i=x[i].p||i))

Test case:

F([undefined,{p:0,v:12,n:2},{p:1,v:99,n:3},{p:2,v:37,n:0}],1,alert)