Daftar tertaut ganda memiliki overhead minimal (hanya pointer lain per sel), dan memungkinkan Anda untuk menambahkan ke kedua ujung dan bolak-balik dan umumnya bersenang-senang.

Nah, jika Anda melihat sedikit lebih dalam, keduanya sebenarnya termasuk array dalam bahasa dasar juga:

• Laporan Skema ke-5 yang direvisi (R5RS) mencakup jenis vektor , yang merupakan kumpulan indeks-bilangan bulat ukuran tetap dengan lebih baik daripada waktu linier untuk akses acak.
• The Haskell 98 Report juga memiliki tipe array .

Instruksi pemrograman fungsional, bagaimanapun, telah lama menekankan daftar single-linked over array atau double-linked list. Bahkan agaknya terlalu ditekankan. Namun, ada beberapa alasan untuk itu.

Yang pertama adalah bahwa daftar yang ditautkan tunggal adalah salah satu tipe data rekursif paling sederhana namun paling berguna. Setara yang ditentukan pengguna dari jenis daftar Haskell dapat didefinisikan seperti ini:

data List a           -- A list with element type `a`...
  = Empty             -- is either the empty list...
  | Cell a (List a)   -- or a pair with an `a` and the rest of the list. 

Fakta bahwa daftar adalah tipe data rekursif berarti bahwa fungsi yang bekerja pada daftar umumnya menggunakan rekursi struktural . Dalam istilah Haskell: Anda mencocokkan pola pada konstruktor daftar, dan Anda mengulang pada sub bagian dari daftar. Dalam dua definisi fungsi dasar ini, saya menggunakan variabel asuntuk merujuk ke ujung daftar. Jadi perhatikan bahwa panggilan rekursif "turun" ke bawah daftar:

map :: (a -> b) -> List a -> List b
map f Empty = Empty
map f (Cell a as) = Cell (f a) (map f as)

filter :: (a -> Bool) -> List a -> List a
filter p Empty = Empty
filter p (Cell a as)
    | p a = Cell a (filter p as)
    | otherwise = filter p as

Teknik ini menjamin bahwa fungsi Anda akan berakhir untuk semua daftar yang terbatas, dan juga merupakan teknik pemecahan masalah yang baik — ia cenderung membagi masalah secara alami menjadi sub-bagian yang lebih sederhana dan lebih dapat dipertahankan.

Jadi daftar yang terhubung tunggal mungkin adalah tipe data terbaik untuk memperkenalkan siswa pada teknik ini, yang sangat penting dalam pemrograman fungsional.

Alasan kedua adalah kurang dari alasan "mengapa daftar tunggal-link", tetapi lebih dari alasan "mengapa tidak daftar-ganda atau array" mengapa: tipe data yang terakhir sering panggilan untuk mutasi (variabel yang dapat dimodifikasi), yang pemrograman fungsional sangat sering menjauh dari. Jadi seperti yang terjadi:

• Dalam bahasa yang bersemangat seperti Skema, Anda tidak dapat membuat daftar ditautkan ganda tanpa menggunakan mutasi.
• Dalam bahasa malas seperti Haskell, Anda dapat membuat daftar tautan ganda tanpa menggunakan mutasi. Tetapi setiap kali Anda membuat daftar baru berdasarkan yang itu, Anda dipaksa untuk menyalin sebagian besar jika tidak semua struktur aslinya. Sedangkan dengan daftar yang ditautkan tunggal, Anda dapat menulis fungsi yang menggunakan "berbagi struktur" —daftar baru dapat menggunakan kembali sel daftar lama jika diperlukan.
• Secara tradisional, jika Anda menggunakan array dengan cara yang tidak berubah itu berarti setiap kali Anda ingin memodifikasi array Anda harus menyalin semuanya. (Perpustakaan Haskell terbaru seperti vector, bagaimanapun, telah menemukan teknik yang sangat memperbaiki masalah ini).

Alasan ketiga dan terakhir berlaku untuk bahasa-bahasa malas seperti Haskell terutama: daftar-daftar tunggal-malas, dalam praktiknya, sering lebih mirip dengan iterator daripada daftar dalam-memori yang tepat. Jika kode Anda menggunakan elemen daftar secara berurutan dan membuangnya saat Anda pergi, kode objek hanya akan mematerialisasi sel daftar dan kontennya saat Anda melangkah maju melalui daftar.

Ini berarti bahwa seluruh daftar tidak perlu ada dalam memori sekaligus, hanya sel saat ini. Sel sebelum yang sekarang dapat berupa sampah yang dikumpulkan (yang tidak mungkin dilakukan dengan daftar yang ditautkan ganda); sel lebih lambat dari yang sekarang tidak perlu dihitung sampai Anda tiba di sana.

Bahkan lebih jauh dari itu. Ada teknik yang digunakan di beberapa perpustakaan Haskell populer, yang disebut fusion , di mana kompiler menganalisis kode pemrosesan daftar Anda dan melihat daftar perantara yang sedang dihasilkan dan dikonsumsi secara berurutan dan kemudian "dibuang." Dengan pengetahuan ini maka kompiler dapat sepenuhnya menghilangkan alokasi memori sel daftar tersebut. Ini berarti bahwa daftar yang ditautkan tunggal dalam program sumber Haskell, setelah dikompilasi, mungkin benar-benar berubah menjadi loop alih-alih struktur data.

Fusion juga merupakan teknik yang digunakan oleh vectorperpustakaan tersebut untuk menghasilkan kode yang efisien untuk array yang tidak berubah. Sama berlaku untuk sangat populer bytestring(byte array) dan text(Unicode string) perpustakaan, yang dibangun sebagai pengganti asli tidak-sangat-besar Haskell Stringjenis (yang sama dengan [Char], daftar tunggal-linked karakter). Jadi di Haskell modern ada tren di mana tipe array yang tidak berubah dengan dukungan fusi menjadi sangat umum.

Daftar fusi difasilitasi oleh fakta bahwa dalam daftar yang terhubung tunggal Anda dapat maju tetapi tidak pernah mundur . Ini memunculkan tema yang sangat penting dalam pemrograman fungsional: menggunakan "bentuk" dari tipe data untuk menurunkan "bentuk" dari suatu perhitungan. Jika Anda ingin memproses elemen secara berurutan, daftar yang ditautkan tunggal adalah tipe data yang, ketika Anda mengkonsumsinya dengan rekursi struktural, memberi Anda pola akses tersebut dengan sangat alami. Jika Anda ingin menggunakan strategi "membagi dan menaklukkan" untuk menyerang masalah, maka struktur data pohon cenderung mendukungnya dengan sangat baik.

Banyak orang keluar dari gerobak pemrograman fungsional sejak awal, sehingga mereka mendapatkan eksposur ke daftar-tautan tunggal tetapi tidak dengan ide-ide mendasar yang lebih maju.

Karena mereka bekerja dengan baik dengan kekekalan. Misalkan Anda memiliki dua daftar yang tidak berubah, [1, 2, 3]dan [10, 2, 3]. Diwakili sebagai daftar yang ditautkan sendiri di mana setiap item dalam daftar adalah simpul yang berisi item dan penunjuk ke seluruh daftar, mereka akan terlihat seperti ini:

node -> node -> node -> empty
 1       2       3

node -> node -> node -> empty
 10       2       3

Lihat bagaimana [2, 3]porsinya identik? Dengan struktur data yang bisa berubah, mereka adalah dua daftar yang berbeda karena kode yang menulis data baru ke salah satu dari mereka tidak perlu memengaruhi kode menggunakan yang lain. Dengan berubah Data Namun, kita tahu bahwa isi dari daftar tidak akan pernah berubah dan kode tidak bisa menulis data baru. Jadi kita dapat menggunakan kembali ekornya dan meminta dua daftar berbagi bagian dari strukturnya:

node -> node -> node -> empty
 1      ^ 2       3
        |
node ---+
 10

Karena kode yang menggunakan kedua daftar tidak akan pernah bermutasi, kami tidak perlu khawatir tentang perubahan pada satu daftar yang memengaruhi yang lain. Ini juga berarti bahwa ketika menambahkan item ke bagian depan daftar, Anda tidak perlu menyalin dan membuat daftar yang sama sekali baru.

Namun, jika Anda mencoba dan mewakili [1, 2, 3]dan [10, 2, 3]sebagai daftar tertaut ganda :

node <-> node <-> node <-> empty
 1       2       3

node <-> node <-> node <-> empty
 10       2       3

Sekarang ekornya tidak identik lagi. Yang pertama [2, 3]memiliki pointer ke 1kepala, tetapi yang kedua memiliki pointer ke 10. Selain itu, jika Anda ingin menambahkan item baru ke kepala daftar Anda harus mengubah kepala sebelumnya dari daftar untuk membuatnya menunjuk ke kepala yang baru.

Masalah beberapa kepala berpotensi diperbaiki dengan meminta setiap simpul menyimpan daftar kepala yang diketahui dan membuat daftar baru memodifikasi itu, tetapi kemudian Anda harus bekerja dalam mempertahankan daftar itu ke siklus pengumpulan sampah ketika versi daftar dengan kepala yang berbeda memiliki masa hidup yang berbeda karena digunakan dalam bagian kode yang berbeda. Ini menambah kompleksitas dan overhead, dan sebagian besar waktu itu tidak sepadan.

Jawaban @ sacundim sebagian besar benar, tetapi ada juga beberapa wawasan penting lainnya tentang pertukaran desain bahasa dan persyaratan praktis.

Objek dan referensi

Bahasa-bahasa ini biasanya memberi mandat (atau mengasumsikan) objek yang memiliki luasan dinamis tak terikat (atau dalam bahasa C, seumur hidup , meskipun tidak sama persis karena perbedaan makna objek di antara bahasa-bahasa ini, lihat di bawah) secara default, menghindari referensi kelas satu ( misalnya penunjuk objek dalam C) dan perilaku tak terduga dalam aturan semantik (misalnya perilaku tidak terdefinisi ISO C yang terkait dengan semantik).

Lebih jauh lagi, gagasan objek (kelas satu) dalam bahasa-bahasa tersebut secara konservatif terbatas: tidak ada properti "locative" yang ditentukan dan dijamin secara default. Ini sangat berbeda dalam beberapa bahasa mirip ALGOL yang objeknya tanpa luasan dinamis yang tidak terikat (misalnya dalam C dan C ++), di mana objek pada dasarnya berarti semacam "penyimpanan yang diketik", biasanya digabungkan dengan lokasi memori.

Untuk menyandikan penyimpanan di dalam objek memiliki beberapa manfaat tambahan seperti bisa melampirkan efek komputasi deterministik sepanjang hidup mereka, tetapi itu adalah topik lain.

Masalah simulasi struktur data

Tanpa referensi kelas satu, daftar yang terhubung sendiri tidak dapat mensimulasikan banyak struktur data tradisional (bersemangat / tidak bisa berubah) secara efektif dan mudah dibawa, karena sifat representasi struktur data ini dan operasi primitif terbatas dalam bahasa-bahasa ini. (Sebaliknya, dalam C, Anda dapat memperoleh daftar tertaut dengan cukup mudah bahkan dalam program yang sangat ketat .) Dan struktur data alternatif seperti array / vektor memang memiliki beberapa sifat yang unggul dibandingkan dengan daftar yang terhubung secara tunggal dalam praktik. Itu sebabnya R ⁵ RS memperkenalkan operasi primitif baru.

Tetapi memang ada perbedaan tipe vektor / array vs daftar yang terhubung ganda. Array sering diasumsikan dengan O (1) kompleksitas waktu akses dan lebih sedikit ruang overhead, yang merupakan properti yang sangat baik yang tidak dibagi oleh daftar. (Meskipun secara tegas, tidak ada yang dijamin oleh ISO C, tetapi pengguna hampir selalu mengharapkannya dan tidak ada implementasi praktis yang akan melanggar jaminan implisit ini terlalu jelas.) OTOH, daftar yang ditautkan dua kali lipat sering membuat kedua properti lebih buruk daripada daftar yang terhubung sendiri-sendiri , sementara iterasi mundur / maju juga didukung oleh array atau vektor (bersama dengan indeks integer) dengan overhead yang lebih sedikit. Dengan demikian, daftar tertaut ganda tidak berkinerja lebih baik secara umum. Lebih buruk lagi, kinerja tentang efisiensi cache dan latensi pada alokasi memori dinamis dari daftar secara katastropik lebih buruk daripada kinerja untuk array / vektor ketika menggunakan pengalokasi standar yang disediakan oleh lingkungan implementasi yang mendasarinya (misalnya libc). Jadi tanpa runtime yang sangat spesifik dan "pintar" sangat mengoptimalkan kreasi objek tersebut, tipe array / vektor sering lebih disukai daripada daftar yang ditautkan. (Misalnya, menggunakan ISO C ++, ada peringatan itustd::vectorharus lebih disukai std::listsecara default.) Dengan demikian, memperkenalkan primitif baru untuk secara khusus mendukung (dua kali lipat) daftar terkait jelas tidak begitu bermanfaat untuk mendukung struktur data array / vektor dalam praktiknya.

Agar adil, daftar masih memiliki beberapa properti spesifik yang lebih baik daripada array / vektor:

• Daftar berbasis node. Menghapus elemen dari daftar tidak membatalkan referensi ke elemen lain di node lain. (Ini juga berlaku untuk beberapa struktur data pohon atau grafik.) OTOH, array / vektor dapat membuat referensi ke posisi trailing menjadi tidak valid (dengan realokasi besar-besaran dalam beberapa kasus).
• Daftar dapat terpecah dalam O (1) waktu. Rekonstruksi array / vektor baru dengan yang sekarang jauh lebih mahal.

Namun, properti ini tidak terlalu penting untuk bahasa dengan dukungan daftar yang terhubung sendiri secara built-in, yang sudah dapat digunakan. Meskipun masih ada perbedaan, dalam bahasa dengan luasan dinamis yang diamanatkan dari objek (yang biasanya berarti ada pengumpul sampah yang menjauhkan referensi yang menggantung), pembatalan dapat juga kurang penting, tergantung pada tujuannya. Jadi, satu-satunya kasus di mana daftar yang ditautkan ganda menang adalah:

• Diperlukan jaminan non-realokasi dan persyaratan iterasi dua arah. (Jika kinerja akses elemen penting dan kumpulan data cukup besar, saya akan memilih pohon pencarian biner atau tabel hash sebagai gantinya.)
• Operasi sambungan dua arah yang efisien diperlukan. Ini sangat jarang. (Saya hanya memenuhi persyaratan hanya untuk mengimplementasikan sesuatu seperti catatan riwayat linier di browser.)

Kekekalan dan aliasing

Dalam bahasa murni seperti Haskell, objek tidak berubah. Objek skema sering digunakan tanpa mutasi. Fakta seperti itu memungkinkan untuk secara efektif meningkatkan efisiensi memori dengan objek interning - berbagi implisit dari beberapa objek dengan nilai yang sama dengan cepat.

Ini adalah strategi optimasi tingkat tinggi yang agresif dalam desain bahasa. Namun, ini memang melibatkan masalah implementasi. Ini sebenarnya memperkenalkan alias implisit ke sel penyimpanan yang mendasarinya. Itu membuat analisis aliasing lebih sulit. Akibatnya, ada kemungkinan lebih sedikit kemungkinan untuk menghilangkan overhead dari referensi non-kelas, bahkan pengguna tidak pernah menyentuh mereka sama sekali. Dalam bahasa seperti Skema, begitu mutasi tidak sepenuhnya dikesampingkan, ini juga mengganggu paralelisme. Mungkin OK dalam bahasa malas (yang sudah memiliki masalah kinerja yang disebabkan oleh thunks).

Untuk pemrograman dengan tujuan umum, pilihan desain bahasa seperti itu mungkin bermasalah. Tetapi dengan beberapa pola pengkodean fungsional yang umum, bahasa-bahasa tersebut tampaknya masih berfungsi dengan baik.