Haruskah Linked Linked selalu memiliki penunjuk ekor?

Pemahaman saya...

Keuntungan:

• Memasukkan pada akhirnya adalah O (1) bukan O (N).
• Jika daftar adalah Daftar Tertaut Ganda, maka menghapus dari ujung juga O (1) bukan O (N).

Kerugian:

• Memakai memori ekstra yang sepele: 4-8 byte .
• Pelaksana harus melacak ekornya.

Melihat kelebihan dan kekurangan ini, saya tidak bisa melihat mengapa Daftar Linked akan pernah menghindari menggunakan pointer ekor. Apakah ada sesuatu yang saya lewatkan?

Anda benar, penunjuk ekor tidak pernah sakit dan hanya bisa membantu. Namun, ada situasi di mana seseorang tidak perlu penunjuk ekor sama sekali.

Jika seseorang menggunakan daftar tertaut untuk mengimplementasikan tumpukan, tidak perlu penunjuk ekor karena orang dapat menjamin bahwa semua akses, penyisipan, dan pemindahan terjadi di kepala. Yang sedang dikatakan orang mungkin menggunakan daftar yang ditautkan dua kali lipat dengan pointer ekor karena itu adalah implementasi standar di perpustakaan atau platform dan memori murah, tetapi orang tidak membutuhkannya .

Daftar tertaut sangat umum bertahan dan tidak dapat diubah. Bahkan, dalam bahasa pemrograman fungsional, penggunaan ini ada di mana-mana. Pointer merusak kedua properti tersebut. Namun, jika Anda tidak peduli tentang kekekalan atau kegigihan, ada sedikit kelemahan untuk memasukkan penunjuk ekor.

Saya jarang menggunakan pointer ekor untuk daftar yang ditautkan dan cenderung menggunakan daftar yang terhubung sendiri lebih sering di mana pola push / pop stack-seperti penyisipan dan penghapusan (atau hanya penghapusan linear-waktu dari tengah) cukup. Itu karena dalam kasus penggunaan umum saya, penunjuk ekor sebenarnya mahal, sama seperti membuat daftar yang ditautkan sendiri ke daftar yang ditautkan dua kali lipat itu mahal.

Seringkali penggunaan kasus umum saya untuk daftar yang terhubung sendiri dapat menyimpan ratusan ribu daftar tertaut yang masing-masing hanya berisi beberapa node daftar. Saya juga umumnya tidak menggunakan pointer untuk daftar tertaut. Saya menggunakan indeks ke dalam array sebagai gantinya karena indeks bisa 32-bit, misalnya, mengambil setengah ruang dari pointer 64-bit. Saya juga umumnya tidak mengalokasikan daftar node satu per satu dan sebagai gantinya, sekali lagi, cukup gunakan array besar untuk menyimpan semua node dan kemudian gunakan indeks 32-bit untuk menghubungkan node bersama.

Sebagai contoh, bayangkan sebuah gim video menggunakan kisi 400x400 untuk mempartisi sejuta partikel yang bergerak dan saling memantul untuk mempercepat deteksi tabrakan. Dalam hal itu, cara yang cukup efisien untuk menyimpannya adalah dengan menyimpan 160.000 daftar yang terhubung sendiri, yang berarti 160.000 bilangan bulat 32-bit dalam kasus saya (~ 640 kilobyte) dan satu overhead bilangan bulat 32-bit per partikel. Sekarang ketika partikel bergerak di layar, yang harus kita lakukan adalah memperbarui beberapa bilangan bulat 32-bit untuk memindahkan partikel dari satu sel ke sel lainnya, seperti:

... dengan nextindeks ("pointer") dari simpul partikel yang berfungsi sebagai indeks untuk partikel berikutnya dalam sel atau partikel bebas berikutnya untuk mengklaim kembali jika partikel tersebut telah mati (pada dasarnya implementasi pengalokasian daftar gratis menggunakan indeks):

Penghapusan linear-waktu dari sel sebenarnya bukan overhead karena kami sedang memproses logika partikel dengan melakukan iterasi melalui partikel di dalam sel, jadi daftar yang saling terhubung hanya akan menambah overhead dari jenis yang tidak menguntungkan di semua dalam kasus saya sama seperti ekor tidak akan menguntungkan saya sama sekali.

Pointer ekor akan menggandakan penggunaan memori grid serta meningkatkan jumlah cache misses. Ini juga membutuhkan penyisipan untuk memerlukan cabang untuk memeriksa apakah daftar itu kosong dan bukannya tanpa cabang. Membuatnya daftar yang terhubung dua kali lipat akan menggandakan daftar di atas kepala setiap partikel. 90% dari waktu saya menggunakan daftar tertaut, itu untuk kasus-kasus seperti ini, dan jadi pointer ekor sebenarnya akan relatif cukup mahal untuk disimpan.

Jadi 4-8 byte sebenarnya tidak sepele di sebagian besar konteks di mana saya menggunakan daftar tertaut di tempat pertama. Hanya ingin chip di sana karena jika Anda menggunakan struktur data untuk menyimpan muatan elemen, maka 4-8 byte mungkin tidak selalu dapat diabaikan. Saya benar-benar menggunakan daftar tertaut untuk mengurangi alokasi memori jumlah dan jumlah memori yang diperlukan sebagai lawan, katakanlah, menyimpan 160.000 array dinamis yang tumbuh untuk grid yang akan memiliki penggunaan memori yang eksplosif (biasanya satu pointer ditambah dua bilangan bulat setidaknya per sel jaringan) bersama dengan alokasi heap per sel grid dibandingkan dengan hanya satu integer dan nol alokasi heap per sel).

Saya sering menemukan banyak orang meraih daftar tertaut karena kompleksitas waktu-konstan mereka yang terkait dengan penghapusan depan / tengah dan pemasangan depan / tengah ketika LL sering merupakan pilihan yang buruk dalam kasus-kasus tersebut karena kurangnya kedekatan secara umum. Di mana LL indah bagi saya dari sudut pandang kinerja adalah kemampuan untuk hanya memindahkan satu elemen dari satu daftar ke yang lain dengan hanya memanipulasi beberapa petunjuk, dan mampu mencapai struktur data berukuran variabel tanpa pengatur memori berukuran variabel (karena setiap node memiliki ukuran yang seragam, kita dapat menggunakan daftar gratis, misalnya). Jika setiap node daftar dialokasikan secara individual terhadap pengalokasi tujuan umum, itu biasanya ketika daftar terkait tarif jauh lebih buruk dibandingkan dengan alternatif, dan itu

Sebagai gantinya saya menyarankan bahwa untuk sebagian besar kasus di mana daftar tertaut berfungsi sebagai optimasi yang sangat efektif atas alternatif langsung, formulir yang paling berguna umumnya terhubung sendiri-sendiri, hanya memerlukan penunjuk kepala, dan tidak memerlukan alokasi memori untuk keperluan umum per simpul dan sebagai gantinya bisa sering menyatukan memori yang sudah dialokasikan per node (dari array besar yang sudah dialokasikan sebelumnya, misalnya). Juga masing-masing SLL umumnya akan menyimpan sejumlah kecil elemen dalam kasus-kasus itu, seperti tepi yang terhubung ke simpul grafik (banyak daftar kecil yang bertautan dengan satu daftar besar yang terhubung).

Perlu juga diingat bahwa saat ini kami memiliki DRAM yang banyak, tetapi itu adalah jenis memori paling lambat kedua yang tersedia. Kami masih pada sesuatu seperti 64 KB per inti ketika datang ke cache L1 dengan garis cache 64-byte. Akibatnya, penghematan byte kecil itu dapat benar-benar penting dalam area kinerja-kritis seperti sim partikel di atas ketika dikalikan jutaan kali lipat jika itu berarti perbedaan antara menyimpan dua kali lebih banyak node ke dalam garis cache atau tidak, misalnya