Apa aturan konkret untuk menggunakan daftar tertaut dan bukan array?

18

Daftar tertaut dapat digunakan saat Anda menginginkan penyisipan dan penghapusan elemen yang murah dan ketika tidak masalah bahwa elemen tersebut tidak bersebelahan dalam memori.

Ini sangat abstrak dan saya ingin penjelasan konkret mengapa daftar tertaut harus digunakan daripada array. Saya tidak terlalu berpengalaman dengan pemrograman, jadi saya tidak punya banyak (jika ada) pengalaman di dunia nyata.

data-structures linked-list sayap kanan
sumber
3
Jujur, saya tidak berpikir contoh akan sangat berarti bagi Anda sampai Anda memiliki pengalaman menulis sesuatu, dan kemudian melihat efek perubahan struktur data pada kode Anda. Cobalah menulis sesuatu yang Anda minati, dan cari tahu struktur data dan wadah mana yang paling cocok, atau lihat beberapa kode yang ada dan pikirkan mengapa masing-masing wadah dipilih, dan apa dampak mengubahnya.
berguna
Saya hanya tidak berpikir itu mungkin berguna untuk mengkomunikasikan trade-off dan efek samping dari pemilihan struktur data ke OP (tidak berpengalaman) tanpa contoh yang jauh lebih baik dari contoh di sini. Contoh-contoh yang diberikan sebagai jawaban baik-baik saja, dan menjawab pertanyaan seperti yang diminta, tetapi tidak (apa yang saya baca) permintaan tersirat untuk pemahaman yang sebenarnya.
berguna

Jawaban:

37

Berikut adalah sesuatu yang merupakan bagian dari contoh dan analogi. Anda memiliki beberapa tugas yang harus dilakukan, sehingga Anda mengambil selembar kertas dan menulis:

  • bank
  • bahan makanan
  • jatuhkan drycleaning

Maka Anda ingat bahwa Anda juga perlu membeli perangko. Karena letak geografis kota Anda, Anda perlu melakukannya setelah bank. Anda dapat menyalin seluruh daftar Anda ke selembar kertas baru:

  • bank
  • perangko
  • bahan makanan
  • jatuhkan drycleaning

atau Anda dapat mencoret-coret yang Anda miliki:

  • bank ....... STAMPS
  • bahan makanan
  • jatuhkan drycleaning

Ketika Anda memikirkan tugas lain, Anda dapat menuliskannya di bagian bawah daftar, tetapi dengan panah yang mengingatkan diri sendiri bagaimana cara melakukannya. Ini adalah daftar yang ditautkan. Lebih cepat dan lebih mudah daripada menyalin seluruh daftar setiap kali Anda menambahkan sesuatu.

Kemudian ponsel Anda berdering saat Anda berada di bank "hei, saya dapatkan perangkonya, jangan ambil lagi". Anda cukup mencoret STAMPS dari daftar, Anda tidak menulis ulang yang baru tanpa STAMPS di dalamnya.

Sekarang Anda benar-benar dapat menerapkan daftar tugas dalam kode (mungkin aplikasi yang mengatur tugas berdasarkan geografi Anda) dan ada kemungkinan Anda akan menggunakan daftar tautan untuk itu dalam kode. Anda ingin menambah dan menghapus banyak item, memesan barang, tetapi Anda tidak ingin menyalin kembali seluruh daftar setelah setiap penyisipan atau penghapusan.

Kate Gregory
sumber
3
Menurut Bjarne Stroustrup, LL mungkin tidak secepat dan mudah untuk menyalin seluruh daftar seperti yang Anda pikirkan .
Dennis
@ Dennis ya, saya tahu, terima kasih untuk memindahkan semantik. Namun ini tidak benar untuk semua bahasa, jadi contohnya adalah.
Kate Gregory
1
@KateGregory cukup adil, tetapi masih bagus untuk menunjukkan bahwa struktur data "dasar" seringkali lebih baik daripada struktur data keren yang kita pelajari di sekolah (atau di tempat lain). Saya tidak ingin lulusan baru menggunakan LLs di mana saja karena secara teoritis sesuai sementara mungkin menjadi pilihan yang buruk secara realistis. Penting untuk menggunakan struktur data yang tepat, dan terkadang orang terlalu rumit. Sedikit terkait adalah pembicaraan oleh Jonathan Blow (pencipta "Braid") tentang struktur data .
Dennis
1
@ Ray: Daftar tertaut dapat mengungguli struktur pohon jika Anda mengharapkan ada di urutan 4 elemen dan perbandingan relatif murah. Saya tidak tahu persis di mana cut-off adalah di mana ini tidak terjadi. Selain itu, struktur pohon mengharuskan data Anda dapat disortir, sedangkan struktur daftar memungkinkan Anda mempertahankan urutan penyisipan (atau urutan sewenang-wenang).
David Stone
2
Saya tidak berpikir analogi ini sangat akurat. Sebagai manusia, kita dapat (setidaknya untuk daftar pendek seperti itu) menemukan elemen dalam O (1). Tetapi jika Anda ingin melakukan penyisipan acak dalam daftar yang ditautkan, Anda harus menelusuri setengah elemen secara rata-rata yang biayanya Anda O (n) hanya untuk menemukan posisi di mana Anda ingin menyisipkan. Sisipan yang sebenarnya hanya biaya O (1) tetapi dengan sebuah array, biaya Anda juga "hanya" O (n). Jadi alasannya bukan hanya karena memindahkan semantik tetapi juga algoritmik. Faktor konstan yang disembunyikan oleh big-O jauh lebih besar untuk daftar yang disukai, karena akses memori yang tidak berdekatan.
5gon12eder
18
  • Tabel hash yang menggunakan rantai untuk menyelesaikan tabrakan hash biasanya memiliki satu daftar tertaut per ember untuk elemen dalam ember itu.
  • Pengalokasi memori sederhana menggunakan daftar bebas wilayah memori yang tidak digunakan, pada dasarnya daftar tertaut dengan daftar pointer di dalam memori bebas itu sendiri
  • Dalam sistem file FAT , metadata file besar diatur sebagai daftar entri FAT yang tertaut.
Michael Borgwardt
sumber
12

"Tumpukan panggilan" dalam bahasa C diimplementasikan sebagai daftar tertaut dalam API biner x86 (dan sebagian besar lainnya).

Yaitu, pemanggilan prosedur C-language mengikuti disiplin pertama, terakhir keluar. Hasil dari mengeksekusi (mungkin rekursif) panggilan fungsi akan disebut sebagai "tumpukan panggilan", atau kadang-kadang bahkan hanya "tumpukan".

The CALLinstruksi x86 berakhir implmenting linked list dengan menggunakan "panggilan stack". Sebuah CALLinstruksi mendorong isi% EIP register, alamat instruksi setelah itu CALLke memori stack. Prolog yang dipanggil berfungsi mendorong konten dari register% EBP, alamat terendah variabel lokal dalam fungsi panggilan, ke memori stack. Kemudian prolog fungsi yang dipanggil menetapkan% EBP ke basis tumpukan fungsi saat ini.

Itu berarti bahwa% EBP adalah penunjuk ke lokasi memori yang menyimpan alamat dari nilai% EBP fungsi panggilan. Itu tidak lebih dari daftar tertaut, diimplementasikan sebagian dalam perangkat keras melalui CALL.

Sejauh ini bagus, x86 CPU menerapkan panggilan fungsi, khususnya panggilan fungsi di mana fungsi memiliki salinan argumennya sendiri, dan variabel lokal ke fungsi tersebut. Setiap panggilan fungsi mendorong beberapa informasi pada "tumpukan panggilan" yang memungkinkan CPU mengambil tempat yang sebelumnya tidak digunakan dalam fungsi panggilan, tanpa gangguan dari fungsi yang dipanggil atau fungsi panggilan.

Bruce Ediger
sumber
3

Daftar tertaut dapat digunakan untuk mengimplementasikan antrian pesan.

Antrian pesan adalah struktur tempat kami menyimpan informasi tentang acara untuk diproses nanti. Misalnya, ketika pengguna menekan tombol atau menggerakkan mouse, ini adalah suatu peristiwa. Suatu aplikasi mungkin sibuk pada saat peristiwa itu terjadi, sehingga tidak dapat diharapkan untuk memproses peristiwa itu pada saat yang tepat ketika itu terjadi. Jadi, acara tersebut ditempatkan dalam antrian pesan, (informasi tentang tombol mana yang ditekan, atau di mana mouse telah dipindahkan,) dan ketika aplikasi memiliki waktu luang, ia memeriksa antrian pesannya, mengambil peristiwa dari itu, dan memprosesnya mereka. (Ini terjadi dalam jangka waktu milidetik, sehingga tidak terlihat.)

Dari skenario penggunaan yang baru saja saya jelaskan, seharusnya jelas bahwa kita tidak pernah peduli untuk memiliki akses acak ke acara yang disimpan dalam antrian pesan; kami hanya peduli untuk dapat menyimpan pesan di dalamnya, dan mengambilnya. Jadi, masuk akal untuk menggunakan daftar tertaut, yang memberikan waktu penyisipan / penghapusan yang optimal.

(Tolong jangan mendukung untuk menunjukkan bahwa antrian pesan kemungkinan, atau lebih mungkin, atau hampir sama mungkin, diimplementasikan menggunakan daftar array melingkar; itu adalah detail teknis, dan memiliki batasan: Anda hanya dapat menyimpan sejumlah pesan di dalamnya.)

Mike Nakis
sumber