Apa itu struktur data yang ditautkan?

Struktur data yang ditautkan adalah kumpulan data yang diatur dalam format seperti daftar. Setiap bagian dari datum dalam daftar disebut sebagai node. Setiap node terhubung ke yang berikutnya diDaftar dengan referensi ke alamat memori dari simpul berikutnya. Struktur data yang tertaut digunakan sebagai pengganti array ketika jumlah node pada daftar tidak diketahui atau mungkin tumbuh atau menyusut selama perjalananEksekusi program. Jenis yang paling umum dari struktur data tertaut disebut daftar tertaut.

Sebuah simpul dari struktur data terkait umumnya berisi dua bagian informasi mdash;referensi ke data aktual yang disimpan dan referensi ke node berikutnya pada daftar. Daftar tertaut dilintasi, atau dicari, dengan melangkah melalui masing -masing node data, dimulai dari yang pertama,atau kepala daftar. Tidak ada cara untuk menemukan informasi dalam daftar tertaut tanpa bergerak secara berurutan melalui node dari awal hingga akhir.

Struktur data yang paling terkait akan menggunakan memori sesedikit mungkin selama programEksekusi. Jika daftar tertaut dibuat dengan hanya satu node dan tidak ada node lain yang ditambahkan, daftar itu akan mengambil memori yang hanya diperlukan untuk satu node. Ini ada di StarkKontras dengan struktur data array di mana ukuran seluruh array harus dinyatakan dan dialokasikan pada awal program dan tidak dapat diubah.

Daftar Tertaut Membayar untuk penggunaan sumber daya memori yang efisien dengan membutuhkannyalebih banyak daya komputasi. Menemukan bagian D tertentuATA dalam daftar yang ditautkan membutuhkan pengulangan melalui seluruh daftar setiap saat, sehingga dapat lebih lambat untuk mengakses informasi di tengah daftar. Menghapus atau memesan ulang data dalam daftar yang ditautkan juga dapat lebih intensif secara komputasi daripada mengelola danArray di mana elemen dapat ditukar dengan mudah.

Struktur data yang ditautkan tidak diperlukan untuk hanya memiliki satu referensi ke simpul berikutnya;Ini dapat memiliki beberapa. Beberapa daftar tertaut memiliki dua referensi node, satu ke simpul berikutnya dalam daftar dan satu ke simpul sebelumnya. Ini dikenal sebagai daftar ditautkan ganda. Ini dapat membuat bergerak melalui aDaftar di kedua arah jauh lebih cepat, meskipun dengan mengorbankan peningkatan penggunaan memori untuk struktur data.

Dimungkinkan untuk daftar yang ditautkan memiliki tiga atau lebih referensi ke node lain dalam daftar. Ini menciptakan struktur yang serupake pohon dengan seluruh cabang node yang melahirkan dari yang tunggal. Jenis -jenis struktur data ini disebut daftar ditautkan multiply. Daftar yang terhubung multipel sangat berguna untuk algoritma penyortiran kompleks yang digunakan untuk menyusun data.Pohon pencarian dimungkinkan sebagian besar karena penggunaan struktur data terkait untuk membuat beberapa cabang panjang variabel.