Daftar tertaut ganda adalah struktur data di mana setiap node memiliki valueserta "tautan" ke kedua previousdan berikutnya nodesdalam daftar. Misalnya, pertimbangkan simpul berikut dengan nilai 12, 99, dan 37:

Di sini, node dengan nilai 12 dan 99 menunjuk ke masing-masing nextnode, dengan nilai 99 dan 37 . Node dengan nilai 37 tidak memiliki nextpointer karena ini adalah node terakhir dalam daftar. Demikian juga, node dengan nilai 99 dan 37 menunjuk ke masing-masing previousnode, 12 dan 99 , tetapi 12 tidak memiliki previouspointer karena itu adalah simpul pertama dalam daftar.

Pengaturan

Dalam praktiknya, "tautan" simpul diimplementasikan sebagai petunjuk ke lokasi simpul sebelumnya dan berikutnya dalam memori. Untuk keperluan kita, "memori" akan menjadi array node dan lokasi node akan menjadi indeksnya dalam array. Node dapat dianggap sebagai 3-tupel dari formulir ( prev value next ). Contoh di atas, maka, mungkin terlihat seperti ini:

Tapi ini mungkin terlihat seperti ini:

Mulai dari sembarang simpul, Anda dapat mengikuti previoustautan (ditampilkan sebagai asal dari panah merah) untuk sampai ke simpul yang mendahuluinya dan nexttautan (panah hijau) untuk menemukan simpul berikutnya untuk mendapatkan semua nilai simpul secara berurutan: [12, 99, 37].

Diagram pertama di atas dapat direpresentasikan dalam array sebagai [[null, 12, 1], [0, 99, 2], [1, 37, null]]. Maka, yang kedua adalah [[2, 99, 1], [0, 37, null], [null, 12, 0]].

Tantangan

Tulis sebuah program yang mengambil input array node dan indeks node dan mengembalikan, dalam urutan daftar, nilai-nilai node dalam daftar yang ditautkan dua kali lipat.

Komplikasi

"Memori" tidak akan selalu berisi node hanya dari satu daftar. Mungkin berisi beberapa daftar:

Array di atas berisi tiga daftar tertaut ganda, kode warna untuk kenyamanan Anda:

1. Node di indeks 7, 10, 1, 4, 3, 12(hanya menampilkan nextlink untuk mengurangi kekacauan; klik untuk memperbesar):

   

   Dengan array ini dan salah satu dari indeks ini, program Anda harus mengembalikan, sesuai urutan, nilainya [0, 1, 1, 2, 3, 5, 8].

2. Node pada indeks 9:

   

   Diberikan indeks 9, program Anda harus kembali [99].

3. Node di indeks 11, 8, 0, 6, 2:

   

   Mengingat salah satu dari indeks ini, itu harus kembali [2, 3, 5, 7, 11].

Aturan

Memasukkan

Program Anda akan menerima sebagai masukan:

1. Daftar 𝒏 simpul (3-tupel seperti dijelaskan di atas), di mana 1 ≤ 𝒏 ≤ 1.000, dalam format apa pun yang mudah digunakan, misalnya array array, array "flat" bilangan bulat dengan panjang 3𝒏, dll.

   Elemen 3-tupel mungkin dalam urutan apa pun: ( prev value next ),, ( next prev value )dll. Untuk setiap node, prevdan nextakan menjadi null(atau nilai lain yang nyaman, misalnya -1), menunjukkan node pertama atau terakhir dalam daftar yang ditautkan ganda, atau indeks yang valid dari daftar, baik berbasis 0 atau 1 sesuai nyaman. valueakan menjadi bilangan bulat 32-bit yang ditandatangani atau jenis bilangan bulat terbesar yang didukung bahasa Anda, mana yang lebih kecil.

2. Indeks 𝒑 dari sebuah simpul dalam daftar (1). Node yang ditunjukkan mungkin merupakan simpul pertama dalam daftar yang tertaut ganda, simpul terakhir, simpul tengah, atau bahkan satu-satunya simpul.

Daftar input (1) dapat berisi data patologis (mis. Siklus, simpul yang ditunjuk oleh banyak simpul lain, dll.), Tetapi indeks input (2) akan selalu menunjuk ke suatu simpul dari mana satu output tunggal yang terbentuk dapat disimpulkan.

Keluaran

Program Anda harus menampilkan nilai-nilai node dari daftar yang ditautkan ganda di mana simpul pada indeks 𝒑 adalah anggota, dalam urutan daftar. Output dapat dalam format apa pun yang nyaman, tetapi datanya harus hanya menyertakan node values.

Kemenangan

Ini adalah kode-golf . Jawaban terpendek dalam byte menang. Celah standar berlaku.

Uji kasus

Di bawah ini, setiap test case berbentuk:

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

... di mana Xadalah huruf untuk mengidentifikasi kasus uji, baris kedua adalah daftar input, baris ketiga adalah indeks input berbasis 0, dan baris keempat adalah 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

05AB1E , 25 byte

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

Cobalah online!

Penjelasan

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

-6 byte berkat Brute Force .

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

Menentukan fungsi #yang menerima daftar daftar bilangan bulat, nullyang direpresentasikan sebagai -1, dan mengembalikan daftar nilai simpul.

Cobalah online!

Penjelasan

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

Tentukan fungsi !yang berulang melalui node mulai dari node idan mengembalikan daftar indeks yang dikunjungi. Ia menerima argumen kedua dyang menentukan indeks mana dari "tuple" yang digunakan sebagai indeks dari node berikutnya ( d==2untuk beralih ke depan, d==0untuk beralih ke belakang).

(i!0)

Iterate mundur mulai dari indeks yang diberikan dan kembali indeks yang dikunjungi.

last(i!0)

Ambil indeks yang terakhir dikunjungi, yang merupakan awal daftar.

last(i!0)!2

Iterate dari awal daftar.

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

Ganti setiap indeks yang dikunjungi dengan nilai node.

Python 2 , 60 byte

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

Cobalah online!

Ini adalah jawaban Chas Brown, minus golf ini:

• Saya menggunakan kembali n, menyimpan tugas
• Saya menyimpan n terakhir yang valid dalam m, memungkinkan saya untuk
• letakkan cetakan setelah penugasan di baris 3, simpan saya cetakan terakhir
• Saya hanya menggunakan ~ n bukannya - ~ n, karena nilai negatif sama jujurnya dengan yang positif, menyelamatkan saya 2 karakter.

Bersih , 94 90 88 byte

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

Cobalah online!

MATL , 39 byte

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

Cobalah online!

Hampir merupakan port langsung dari jawaban Oktaf saya, tetapi versi ini menemukan akhir terlebih dahulu, dan kemudian bekerja kembali, daripada sebaliknya, yang menghemat satu 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.

PHP, 132 byte

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

Cobalah online!

Input diambil sebagai QueryString x[]=-1&x[]=1&x[]=1...(semua node dalam array datar), di urutan next, prevmaka valueuntuk setiap node dengan -1 digunakan untuk mengakhiri node.

Python 2 , 81 77 byte

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

Cobalah online!

EDIT: Thx to Mr. Xcoder untuk 4 byte ...

Mengambil daftar tupel [u, v, w] di mana u dan w adalah -1 untuk mewakili awal / akhir segmen daftar tertaut.

Oktaf , 81 78 76 byte

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

Cobalah online!

Versi yang agak mudah. Penjelasan dibiarkan sebagai latihan untuk pembaca. Versi yang jauh lebih menyenangkan disajikan di bawah ini:

Oktaf , 142 99 92 byte

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

Cobalah online!

Yo, saya dengar Anda menyukai fungsi anonim ...

Mengambil nx3array, dengan kolom pertama pendahulunya, kolom kedua nilai, dan nilai ketiga node penerus. Semua indeks node berbasis 1, yang merupakan standar dalam Oktaf.

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

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

Yg diperindahkan

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

Uji

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

Kasus cobaan:

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