Pertanyaan Apakah layak membuat LinkedList di Java Script


Saat ini saya sedang mengerjakan proyek yang mengharuskan saya untuk mengulang melalui daftar nilai dan menambahkan nilai baru di antara setiap nilai yang sudah ada dalam daftar. Ini akan terjadi untuk setiap iterasi sehingga daftar akan tumbuh secara eksponensial. Saya memutuskan bahwa menerapkan daftar sebagai Daftar Tertaut akan menjadi ide yang bagus. Sekarang, JS tidak memiliki struktur data Daftar Tertaut default, dan saya tidak punya masalah dalam membuat satu.

Tapi pertanyaan saya adalah, apakah pantas untuk membuat Daftar Tertaut sederhana dari awal, atau akan lebih baik untuk membuat array dan menggunakan sambatan () untuk menyisipkan setiap elemen? Apakah itu, pada kenyataannya, menjadi kurang efisien karena overhead?


7
2018-03-09 08:58


asal


Jawaban:


Gunakan daftar yang ditautkan, pada kenyataannya sebagian besar implementasi kustom dilakukan dengan baik di javascript pengguna akan mengalahkan implementasi bawaan karena kerumitan spesifikasi dan JITting yang layak. Misalnya lihat https://github.com/petkaantonov/deque

Apa yang dikatakan george secara harfiah 100% salah pada setiap poin, kecuali Anda menggunakan mesin waktu hingga 10 tahun yang lalu.


Untuk implementasi, jangan membuat daftar tertaut eksternal yang berisi nilai tetapi buatlah nilai-nilai yang secara alami terkait dengan daftar node. Anda sebaliknya akan menggunakan terlalu banyak memori.


5
2018-03-09 10:50



Memasukkan setiap elemen dengan splice() akan menjadi lebih lambat memang (memasukkan n elemen membutuhkan waktu O (n²)). Tetapi sederhananya membangun sebuah array baru (menambahkan nilai-nilai baru dan menambahkan nilai-nilai dari yang lama dalam berbaris) dan membuang yang lama mengambil waktu linier, dan kemungkinan besar memiliki faktor-faktor konstan yang lebih baik daripada memanipulasi daftar tertaut. Bahkan mungkin membutuhkan lebih sedikit memori (node ​​daftar terhubung dapat memiliki overhead luar angkasa yang sangat besar, terutama jika mereka tidak mengganggu).


3
2018-03-09 14:48



Javascript adalah bahasa yang ditafsirkan. Jika Anda ingin menerapkan daftar tertaut maka Anda akan berulang banyak! Interpreter akan tampil perlahan-lahan. Fungsi built-in yang disediakan oleh intrepreter dioptimalkan dan dikompilasi dengan interpreter sehingga mereka akan berjalan lebih cepat. Saya akan memilih untuk mengiris array dan kemudian menggabungkan semuanya lagi, itu harus lebih cepat kemudian menerapkan struktur data Anda sendiri.

Begitu juga javascript melewati nilai bukan oleh pointer / referensi jadi bagaimana Anda akan menerapkan daftar tertaut?


-1
2018-03-09 09:29