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.

比较对象	顺序表	链表
存储空间	连续	不连续
插入或删除数据	可能要搬移数据，复杂度O(n)	只需修改指针
push	动态顺序表：空间不够了需要扩容	没有“容量”的概念，push时直接malloc新的结点
应用	需要频繁访问	需要频繁插入、删除数据

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!