Une liste doublement liée est une structure de données dans laquelle chaque nœud a un valueainsi que des «liens» à la fois au previouset suivant nodesdans la liste. Par exemple, considérez les nœuds suivants avec les valeurs 12, 99 et 37:

Ici, les nœuds avec les valeurs 12 et 99 pointent vers leurs nextnœuds respectifs , avec les valeurs 99 et 37 . Le nœud avec la valeur 37 n'a pas de nextpointeur car c'est le dernier nœud de la liste. De même, les nœuds avec les valeurs 99 et 37 pointent vers leurs previousnœuds respectifs , 12 et 99 , mais 12 n'a pas de previouspointeur car c'est le premier nœud de la liste.

La mise en place

En pratique, les "liens" d'un nœud sont implémentés en tant que pointeurs vers les emplacements du nœud précédent et suivant en mémoire. Pour nos besoins, la "mémoire" sera un tableau de nœuds et l'emplacement d'un nœud sera son index dans le tableau. Un nœud peut être considéré comme un triplet de la forme ( prev value next ). L'exemple ci-dessus pourrait alors ressembler à ceci:

Mais cela pourrait plutôt ressembler à ceci:

À partir de n'importe quel nœud, vous pouvez suivre les previousliens (indiqués comme les origines des flèches rouges) pour accéder aux nœuds qui le précèdent et les nextliens (flèches vertes) pour trouver les nœuds suivants afin d'obtenir toutes les valeurs des nœuds dans l'ordre: [12, 99, 37].

Le premier diagramme ci-dessus pourrait être représenté dans un tableau sous la forme [[null, 12, 1], [0, 99, 2], [1, 37, null]]. Le second serait donc [[2, 99, 1], [0, 37, null], [null, 12, 0]].

Le défi

Écrivez un programme qui prend en entrée un tableau de nœuds et l'index d'un nœud et renvoie, dans l'ordre des listes, les valeurs des nœuds dans la même liste doublement liée.

Une complication

La "mémoire" ne contiendra pas toujours les nœuds d'une seule liste. Il peut contenir plusieurs listes:

Le tableau ci-dessus contient trois listes doublement liées, codées par couleur pour votre commodité:

1. Les noeuds à index 7, 10, 1, 4, 3, 12(ne montrant que des nextliens pour réduire l' encombrement, cliquez pour agrandir):

   

   Étant donné ce tableau et l'un de ces index, votre programme doit retourner, dans l'ordre, les valeurs [0, 1, 1, 2, 3, 5, 8].

2. Le nœud à l'index 9:

   

   Compte tenu de l'index 9, votre programme devrait revenir [99].

3. Les noeuds à index 11, 8, 0, 6, 2:

   

   Étant donné l'un de ces index, il devrait revenir [2, 3, 5, 7, 11].

Règles

Contribution

Votre programme recevra en entrée:

1. Une liste de 𝒏 nœuds (3-tuples comme décrit ci-dessus), où 1 ≤ 𝒏 ≤ 1000, dans n'importe quel format pratique, par exemple un tableau de tableaux, un tableau "plat" d'entiers de longueur 3𝒏, etc.

   Les éléments de 3-uplets peuvent être dans un ordre quelconque: ( prev value next ), ( next prev value ), etc. Pour chaque noeud, prevet nextsera null(ou une autre valeur appropriée, par exemple -1), ce qui indique le premier ou le dernier noeud dans une liste doublement lié, ou un indice valide de la liste, soit 0 ou 1 comme il est commode. valuesera un entier 32 bits signé ou le plus grand type d'entier pris en charge par votre langue, le plus petit des deux.

2. L'index 𝒑 d'un nœud dans la liste (1). Le nœud indiqué peut être le premier nœud d'une liste à double liaison, le dernier nœud, un nœud intermédiaire ou même le seul nœud.

La liste d'entrée (1) peut contenir des données pathologiques (par exemple des cycles, des nœuds pointés par plusieurs autres nœuds, etc.), mais l'index d'entrée (2) pointera toujours vers un nœud à partir duquel une sortie unique et bien formée peut être déduit.

Production

Votre programme devrait sortir les valeurs des nœuds de la liste doublement liée dont le nœud à l'index 𝒑 est membre, dans l'ordre des listes. La sortie peut être dans n'importe quel format pratique, mais ses données doivent inclure uniquement les nœuds value.

Gagnant

C'est du code-golf . La réponse la plus courte en octets l'emporte. Des échappatoires standard s'appliquent.

Cas de test

Ci-dessous, chaque cas de test est de la forme:

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

... où Xest une lettre pour identifier le cas de test, la deuxième ligne est la liste d'entrée, la troisième ligne est l'index d'entrée basé sur 0 et la quatrième ligne est la sortie.

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 octets

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

Essayez-le en ligne!

Explication

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

-6 octets grâce à Brute Force .

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

Définit une fonction #qui accepte une liste de listes d'entiers, où nullest représenté par -1, et renvoie une liste de valeurs de nœuds.

Essayez-le en ligne!

Explication

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

Définissez la fonction !qui parcourt les nœuds à partir du nœud iet renvoie une liste des index visités. Il accepte le deuxième argument dqui spécifie quel index du "tuple" utiliser comme index du nœud suivant ( d==2pour itérer en avant, d==0pour itérer en arrière).

(i!0)

Itérer en arrière à partir de l'index donné et renvoyer les index visités.

last(i!0)

Prenez le dernier index visité, qui est le début de la liste.

last(i!0)!2

Répéter depuis le début de la liste.

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

Remplacez chaque index visité par la valeur du nœud.

Python 2 , 60 octets

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

Essayez-le en ligne!

C'est à peu près la réponse de Chas Brown, moins ces golfs:

• Je réutilise n, sauvegarde une affectation
• Je stocke le dernier n valide en m, ce qui me permet de
• placer l'impression après l'affectation à la ligne 3, en me gardant l'impression finale
• J'utilise seulement ~ n au lieu de - ~ n, car les valeurs négatives sont tout aussi véridiques que positives, ce qui me fait gagner 2 caractères.

Nettoyer , 94 90 88 octets

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

Essayez-le en ligne!

MATL , 39 octets

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

Essayez-le en ligne!

Presque un port direct de ma réponse Octave, mais cette version trouve la fin en premier, puis fonctionne en arrière, plutôt que dans l'autre sens, ce qui a permis d'économiser un octet.

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 octets

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

Essayez-le en ligne!

Entrée est prise en tant que chaîne de requête x[]=-1&x[]=1&x[]=1...(tous les noeuds dans un réseau plat), dans l'ordre de next, prevpuis valuepour chaque noeud avec -1 utilisée pour mettre fin à des noeuds.

Python 2 , 81 77 octets

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

Essayez-le en ligne!

EDIT: Thx à M. Xcoder pour 4 octets ...

Prend une liste de tuples [u, v, w] où u et w sont -1 pour représenter le début / la fin du segment de liste liée.

Octave , 81 78 76 octets

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

Essayez-le en ligne!

Version plutôt simple. L'explication est laissée au lecteur comme exercice. Une version beaucoup plus amusante est présentée ci-dessous:

Octave , 142 99 92 octets

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

Essayez-le en ligne!

Yo, j'ai entendu dire que vous aimiez les fonctions anonymes ...

Prend un nx3tableau, avec la première colonne le prédécesseur, la deuxième colonne la valeur et la troisième valeur les nœuds successeurs. Tous les indices de nœuds sont basés sur 1, ce qui est la valeur par défaut dans 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)

Kotlin , 85 octets

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

Embellie

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

Tester

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 octets

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

Cas de test:

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