Apakah konsep dan struktur senarai terpaut dalam struktur data Java?

1. Konsep senarai terpaut

Konsep: Senarai terpaut ialah struktur storan fizikal yang tidak berterusan dan tidak berurutan Susunan logik elemen data direalisasikan melalui pautan susunan penunjuk dalam senarai terpaut

1 Senarai terpaut terdiri daripada satu siri nod (setiap elemen dalam senarai terpaut dipanggil nod).

2. Nod boleh dijana secara dinamik (mallok) pada masa jalan.

3. Setiap nod merangkumi dua bahagian: satu ialah medan data yang menyimpan elemen data, dan satu lagi ialah medan penunjuk yang menyimpan alamat nod seterusnya (lihat bahagian 1.2 Nod untuk butiran).

4 Berbanding dengan struktur jujukan senarai linear, operasi senarai terpaut adalah rumit. Walau bagaimanapun, oleh kerana ia tidak perlu disimpan mengikut urutan, senarai terpaut boleh mencapai kerumitan O(1) apabila memasukkan, yang jauh lebih pantas daripada senarai berjujukan walau bagaimanapun, mencari nod atau mengakses nod dengan nombor tertentu memerlukan Masa O(n), dan Senarai jujukan hanya memerlukan O(1)

2 Nod

Senarai terpaut terdiri daripada nod, dan setiap nod adalah dalam bentuk struktur. Pembolehubah pertama dalam struktur diberikan mengikut keperluan Pembolehubah terakhir ialah penunjuk jenis struktur ini, digunakan untuk menyimpan alamat pertama nod seterusnya‘

Nod senarai terpaut dibahagikan kepada dua medan
medan data : Simpan pelbagai data sebenar
Medan penunjuk: Simpan alamat nod seterusnya

(Gambar menunjukkan senarai terpaut dengan nod pengepala sentinel)

3. Senario penggunaan senarai terpaut

Jadual linear sesuai untuk menggunakan struktur storan terpaut apabila elemen data perlu kerap dimasukkan atau dipadamkan .

Oleh kerana untuk senarai terpaut, memasukkan atau memadam data hanya memerlukan mencipta nod, memasukkan data dan mengubah suai penunjuk untuk menyambungkan nod ke kedudukan tertentu dalam senarai terpaut manakala untuk senarai berjujukan, memasukkan a Data mungkin perlu dialihkan ke data lain, yang sangat kompleks.

4. Klasifikasi senarai terpaut dan struktur yang biasa digunakan

Walaupun terdapat 8 jenis senarai terpaut untuk dipilih dalam gabungan, Dalam amalan, yang paling biasa digunakan ialah senarai terpaut Sehala tanpa kitaran dan senarai terpaut kitaran dua hala tanpa kepala.

1. Senarai terpaut sehala bukan kitaran tanpa kepala: biasanya dikenali sebagai "senarai pautan tunggal". Strukturnya mudah dan biasanya tidak digunakan untuk menyimpan data sahaja. Malah, ia lebih kepada substruktur struktur data lain (seperti baldi cincang, senarai bersebelahan graf, struktur rantai tindanan, dsb.)

2. Senarai terpaut pekeliling dwiarah berkepala: struktur paling kompleks, secara amnya digunakan Simpan data secara berasingan. Kebanyakan senarai terpaut yang sebenarnya digunakan ialah senarai terpaut pekeliling dua hala. Walaupun strukturnya paling kompleks, struktur ini membawa banyak kelebihan.

5. Perbandingan dengan senarai berjujukan

Senarai terpaut: Senarai terpaut memautkan data diskret ke dalam jadual melalui nod, dan memasukkan serta memadam nod melalui operasi Untuk mencapai akses kepada data.

Jadual jujukan: Jadual jujukan menyimpan data dengan membuka memori berterusan (secara langsung menggunakan tatasusunan atau malloc dan kemudian pengembangan realloc).

Walau bagaimanapun, disebabkan pengembangan realloc terbahagi kepada pengembangan in-situ dan pengembangan luar tapak yang lebih murah, manakala yang kedua memerlukan bukan sahaja menyalin data, tetapi juga mengeluarkan yang lama ruang apabila mengembang. Tambahan pula, apabila mengembangkan, ia biasanya akan dikembangkan kepada 2 kali ganda kapasiti asal Pengembangan terlalu banyak kali akan menyebabkan pembaziran ruang dengan mudah

Setiap ahli jadual jujukan sepadan dengan nod yang dipautkan. senarai; ahli dan nod Jenis data boleh menjadi jenis C standard atau jenis struktur yang ditentukan pengguna.

Atas ialah kandungan terperinci Apakah konsep dan struktur senarai terpaut dalam struktur data Java?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!