Eine doppelt verknüpfte Liste ist eine Datenstruktur, in der jeder Knoten sowohl eine valueals auch "Verknüpfungen" zu der previousund der nächsten nodesin der Liste aufweist. Betrachten Sie beispielsweise die folgenden Knoten mit den Werten 12, 99 und 37:

Hier zeigen die Knoten mit den Werten 12 und 99 auf ihre jeweiligen nextKnoten mit den Werten 99 und 37 . Der Knoten mit dem Wert 37 hat keinen nextZeiger, da er der letzte Knoten in der Liste ist. Ebenso zeigen die Knoten mit den Werten 99 und 37 auf ihre jeweiligen previousKnoten 12 und 99 , aber 12 hat keinen previousZeiger, da es der erste Knoten in der Liste ist.

Die Einrichtung

In der Praxis werden die "Links" eines Knotens als Zeiger auf die Positionen des vorherigen und des nächsten Knotens im Speicher implementiert. Für unsere Zwecke ist der "Speicher" ein Array von Knoten und der Ort eines Knotens ist sein Index im Array. Ein Knoten kann als 3-Tupel der Form betrachtet werden ( prev value next ). Das obige Beispiel könnte dann so aussehen:

Aber es könnte stattdessen so aussehen:

Sie können von jedem Knoten aus über previousLinks (angezeigt als Ursprung der roten Pfeile) zu den vorhergehenden Knoten und über nextLinks (grüne Pfeile) nach nachfolgenden Knoten suchen, um alle Werte der Knoten in der angegebenen Reihenfolge abzurufen: [12, 99, 37].

Das erste Diagramm oben könnte in einem Array als dargestellt werden [[null, 12, 1], [0, 99, 2], [1, 37, null]]. Der zweite wäre dann [[2, 99, 1], [0, 37, null], [null, 12, 0]].

Die Herausforderung

Schreiben Sie ein Programm, das ein Array von Knoten und den Index eines Knotens als Eingabe verwendet und in Listenreihenfolge die Werte der Knoten in derselben doppelt verknüpften Liste zurückgibt.

Eine Komplikation

Der "Speicher" enthält nicht immer die Knoten von nur einer Liste. Es kann mehrere Listen enthalten:

Das obige Array enthält drei doppelt verknüpfte Listen, die der Einfachheit halber farblich gekennzeichnet sind:

1. Die Knoten auf Indizes 7, 10, 1, 4, 3, 12(zeigt nur nextLinks Unordnung zu verringern; zum Vergrößern anklicken):

   

   Angesichts dieses Arrays und eines dieser Indizes sollte Ihr Programm die Werte in der angegebenen Reihenfolge zurückgeben [0, 1, 1, 2, 3, 5, 8].

2. Der Knoten am Index 9:

   

   In Anbetracht des Index 9sollte Ihr Programm zurückkehren [99].

3. Die Knoten auf Indizes 11, 8, 0, 6, 2:

   

   Bei einem dieser Indizes sollte er zurückgeben [2, 3, 5, 7, 11].

Regeln

Eingang

Ihr Programm wird als Eingabe erhalten:

1. Eine Liste von 𝒏 Knoten (3-Tupel wie oben beschrieben) mit 1 ≤ 𝒏 ≤ 1.000 in einem beliebigen geeigneten Format, z. B. einem Array von Arrays, einem "flachen" Array von Ganzzahlen mit der Länge 3𝒏 usw.

   Die 3-Tupel Elemente in beliebiger Reihenfolge sein: ( prev value next ), ( next prev value )usw. Für jeden Knoten, prevund nextwerden null(oder ein anderer geeigneter Wert, beispielsweise -1), die den ersten oder letzten Knoten in einer doppelt verknüpften Liste oder einen gültigen Index der Liste, wahlweise 0- oder 1-basiert. valueDies ist eine 32-Bit-Ganzzahl mit Vorzeichen oder der größte Ganzzahltyp, den Ihre Sprache unterstützt, je nachdem, welcher Wert kleiner ist.

2. Der Index 𝒑 eines Knotens in der Liste (1). Der angegebene Knoten kann der erste Knoten in einer doppelt verknüpften Liste, der letzte Knoten, ein mittlerer Knoten oder sogar der einzige Knoten sein.

Die Eingabeliste (1) kann pathologische Daten enthalten (z. B. Zyklen, Knoten, auf die von mehreren anderen Knoten verwiesen wird usw.), der Eingabeindex (2) zeigt jedoch immer auf einen Knoten, von dem aus eine einzige, wohlgeformte Ausgabe erfolgen kann abgeleitet.

Ausgabe

Ihr Programm sollte die Werte der Knoten der doppelt verknüpften Liste, zu der der Knoten bei Index 𝒑 gehört, in Listenreihenfolge ausgeben. Die Ausgabe kann in einem beliebigen Format erfolgen, die Daten dürfen jedoch nur die Knoten enthalten value.

Gewinnen

Das ist Code-Golf . Kürzeste Antwort in Bytes gewinnt. Es gelten Standardlücken.

Testfälle

Im Folgenden hat jeder Testfall die Form:

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

... wobei Xein Buchstabe den Testfall kennzeichnet, die zweite Zeile die Eingabeliste ist, die dritte Zeile den 0-basierten Eingabeindex und die vierte Zeile die Ausgabe ist.

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

05AB1E , 25 Bytes

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

Probieren Sie es online!

Erläuterung

è[¬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

Haskell , 79 65 59 55 Bytes

-6 Bytes dank Brute Force .

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

Definiert eine Funktion #, die eine Liste mit ganzen Zahlen akzeptiert, wobei nulldargestellt wird als -1und eine Liste mit Knotenwerten zurückgibt.

Probieren Sie es online!

Erläuterung

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

Definieren Sie eine Funktion !, die die Knoten ab Knoten durchläuft iund eine Liste der besuchten Indizes zurückgibt. Es akzeptiert das zweite Argument d, das angibt, welcher Index des "Tupels" als Index des nächsten Knotens verwendet wird ( d==2vorwärts d==0iterieren, rückwärts iterieren).

(i!0)

Ab dem angegebenen Index rückwärts iterieren und besuchte Indizes zurückgeben.

last(i!0)

Nimm den zuletzt besuchten Index, der der Anfang der Liste ist.

last(i!0)!2

Iterieren Sie ab dem Anfang der Liste.

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

Ersetzen Sie jeden besuchten Index durch den Wert des Knotens.

Python 2 , 60 Bytes

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

Probieren Sie es online!

Dies ist so ziemlich die Antwort von Chas Brown, abzüglich dieser Golfplätze:

• Ich verwende n wieder und speichere eine Zuordnung
• Ich speichere das letzte gültige n in m und erlaube es mir
• Platzieren Sie den Ausdruck nach der Zuweisung in Zeile 3 und speichern Sie den endgültigen Ausdruck
• Ich verwende nur ~ n anstelle von - ~ n, weil negative Werte genauso wahr sind wie positive und mir 2 Zeichen ersparen.

Sauber , 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

Probieren Sie es online!

MATL , 39 Bytes

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

Probieren Sie es online!

Fast ein direkter Port meiner Octave-Antwort, aber diese Version findet das Ende zuerst und arbeitet es dann wieder zurück und nicht umgekehrt, wodurch ein Byte gespart wurde.

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.

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

Probieren Sie es online!

Die Eingabe wird als Querystring x[]=-1&x[]=1&x[]=1...(alle Knoten in einem flachen Array) in der Reihenfolge next, prevund dann valuefür jeden Knoten mit -1 zum Beenden von Knoten verwendet.

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

Probieren Sie es online!

EDIT: Danke an Mr. Xcoder für 4 Bytes ...

Nimmt eine Liste von Tupeln [u, v, w], wobei u und w -1 sind, um den Anfang / das Ende des verknüpften Listensegments darzustellen.

Oktave , 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

Probieren Sie es online!

Eher unkomplizierte Version. Die Erklärung bleibt als Übung dem Leser überlassen. Eine viel spaßigere Version wird nachfolgend vorgestellt:

Oktave , 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)]

Probieren Sie es online!

Yo, ich habe gehört, du mochtest anonyme Funktionen ...

Nimmt ein nx3Array, wobei die erste Spalte der Vorgänger, die zweite Spalte der Wert und der dritte Wert die Nachfolgeknoten sind. Alle Knotenindizes basieren auf 1, was in Octave der Standard ist.

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

Kotlin , 85 Bytes

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

Verschönert

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

Prüfung

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

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

Testfall:

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