Penjelasan terperinci tentang fungsi dasar Java yang menerapkan daftar tertaut satu arah

1. Pendahuluan

Baru -baru ini, ketika meninjau struktur data dan algoritma, beberapa masalah algoritma menggunakan ide tumpukan, dan ketika datang ke tumpukan, kita harus berbicara tentang daftar yang ditautkan. Array dan Daftar Tertaut adalah dasar dari struktur penyimpanan linier, dan tumpukan dan antrian adalah aplikasi struktur penyimpanan linier ~

Artikel ini terutama menjelaskan titik-titik pengetahuan dasar dari daftar yang terkait tunggal, dan membuat pengantar sederhana. Jika ada kesalahan, harap perbaiki.

2. Ulasan dan Pengetahuan

Berbicara tentang daftar yang ditautkan, mari kita sebutkan array. Membandingkannya dengan array membuat Anda sangat memahami struktur penyimpanan daftar tertaut dengan sangat baik.

2.1 Tinjau array

Kami telah belajar array di C dan Java:

• Array adalah struktur linier penyimpanan kontinu, dengan jenis elemen yang sama dan ukuran yang sama

Keuntungan array:

• Kecepatan akses cepat

Kerugian array:

• Anda harus tahu panjang array terlebih dahulu
• Lambat untuk memasukkan dan menghapus elemen
• Ruang biasanya terbatas
• Membutuhkan blok memori kontinu yang besar
• Memasukkan dan menghapus elemen tidak efisien

2.2 Deskripsi Daftar Tautan

Setelah membaca array, kembali ke daftar tertaut kami:

• Daftar Tertaut adalah struktur linier penyimpanan diskrit

N node secara diskrretik dialokasikan dan terhubung satu sama lain melalui pointer. Setiap node hanya memiliki satu node pendahulu, masing -masing node hanya memiliki satu simpul berikutnya, simpul pertama tidak memiliki node pendahulu, dan simpul ekor tidak memiliki simpul berikutnya.

Keuntungan Daftar Tertaut:

• Tidak ada batasan ruang
• Memasukkan dan menghapus elemen dengan cepat

Kerugian Daftar Tertaut:

• Kecepatan akses sangat lambat

Saya akan menjelaskan istilah yang terkait dengan daftar yang ditautkan melalui gambar di atas:

Untuk menentukan daftar yang ditautkan, kami hanya perlu penunjuk kepala, dan seluruh daftar yang ditautkan dapat disimpulkan melalui pointer kepala ~

Ada beberapa kategori daftar tertaut:

1. Tabel tautan satu arah

• Satu node menunjuk ke simpul berikutnya

2. Tabel tautan dua arah

• Node memiliki dua bidang pointer

3. Daftar Tautan Daur Ulang

• Semua node lain dapat ditemukan melalui node apa pun, dan daftar tertaut kedua (dua arah/seireksional) ditunjuk ke simpul pertama untuk mewujudkan loop

Apa yang perlu Anda ingat saat mengoperasikan daftar yang ditautkan adalah:

Bidang pointer di simpul menunjuk ke node!

3. Daftar Tautan Implementasi Java

Algoritma:

• Traversal
• Menemukan
• Jernih
• menghancurkan
• Temukan panjangnya
• Menyortir
• Hapus node
• Masukkan simpul

Pertama, kami mendefinisikan kelas sebagai node

• Domain data
• Bidang pointer

Untuk kenyamanan operasi, saya secara langsung mendefinisikannya sebagai publik.

 Node kelas publik {// Data Domain Data Int Publik; // domain pointer, menunjuk ke simpul node publik berikutnya selanjutnya; node publik () {} node publik (data int) {this.data = data; } node publik (data int, node selanjutnya) {this.data = data; this.next = next; }}

3.1 Buat daftar tertaut (tambahkan node)

Masukkan data ke dalam daftar tertaut:

• Temukan simpul ekor untuk dimasukkan
• Bahkan jika node head.next adalah nol dan tidak melalui loop whene, itu akan menghubungkan simpul kepala ke simpul baru (saya telah menginisialisasi simpul kepala, jadi tidak perlu menentukan apakah node kepala nol) ~

 /*** Tambahkan data ke daftar tertaut** @param Nilai data yang akan ditambahkan*/public static void addData (nilai int) {// inisialisasi node yang akan ditambahkan newNode = node baru (nilai); // simpul simpul sementara Temp = head; // Temukan node ekor while (temp.next! = Null) {temp = temp.next; } // Kasus di mana head node.next adalah null telah dimasukkan ~ temp.next = newNode; }

3.2 Melintasi Daftar Tertaut

Kami telah menulis metode penambahan di atas, dan sekarang kami akan melewatinya untuk melihat apakah itu benar ~~~

Mulai dari simpul pertama dan terus mencari di belakang sampai tidak ada data pada node berikutnya:

 / *** Melintasi daftar tertaut** @param head head node*/ public static void traverse (head simpul) {// simpul sementara, mulai dari simpul node pertama temp = head.next; while (temp! = null) {System.out.println ("Ikuti akun resmi java3y:" + temp.data); // lanjutkan dengan temp = temp.next berikutnya; }}

hasil:

3.3 Masukkan simpul

• Masukkan node ke dalam daftar tertaut, Anda harus terlebih dahulu menentukan apakah posisi ini legal sebelum memasukkannya ~
• Temukan saja simpul sebelumnya di mana Anda ingin memasukkan ~

 /** * Insert node* * @param head head pointer* @param index position to be inserted* @param value value to be inserted*/ public static void insertNode(Node head, int index, int value) { //First of all, you need to determine whether the specified position is legal, if (index < 1 || index > linkListLength(head) + 1) { System.out.println("Insert position is ilegal. "); kembali; } // simpul sementara, mulailah dari simpul awal node temp = head; // Klik posisi saat ini dari traversal int currentpos = 0; // inisialisasi node yang akan dimasukkan node insertNode = node new (nilai); while (temp.next! = null) {// Lokasi simpul sebelumnya ditemukan jika ((indeks - 1) == currentpos) {// temp mewakili simpul sebelumnya // poin pointer asli dari node sebelumnya ke simpul yang disisipkan ke insertNode.next = temp.next; // Tunjuk bidang pointer dari simpul sebelumnya ke node yang akan dimasukkan temp .next = insertNode; kembali; } currentpos ++; temp = temp.next; }}

3.4 Dapatkan panjang daftar yang ditautkan

Sangat mudah untuk mendapatkan panjang daftar yang ditautkan. Ini dapat dilakukan dengan melintasi dan mendapatkan +1 untuk setiap node ~

 / *** Dapatkan panjang daftar yang ditautkan* @param head pointer*/ public static int linkListLength (head simpul) {int length = 0; // simpul sementara, mulailah dari simpul node pertama temp = head.next; // Temukan simpul ekor while (temp! = Null) {length ++; temp = temp.next; } panjang pengembalian; }

3.5 Hapus node

Menghapus node di lokasi tertentu sebenarnya sangat mirip dengan simpul penyisipan, dan Anda juga perlu menemukan node sebelumnya. Ubah bidang pointer dari simpul sebelumnya dan Anda dapat menghapusnya ~

 /** * Hapus node Menurut lokasi * * @param head pointer head * @param indeks lokasi yang akan dihapus */public static void deletenode (node head, int index) {// pertama -tama, Anda perlu menentukan apakah lokasi yang ditentukan, jika (indeks <1 || index> linklistlistLength (head) + 1) {outl. kembali; } // simpul sementara, mulailah dari simpul awal node temp = head; // Lokasi saat ini dari traversal catatan adalah int currentpos = 0; while (temp.next! = null) {// Lokasi simpul sebelumnya ditemukan jika ((indeks - 1) == currentpos) {// temp mewakili simpul sebelumnya // temp.next mewakili simpul yang ingin Anda hapus // penyimpanan simpul yang ingin Anda hapus simpul deletenode = temp.next; // Node berikutnya yang ingin Anda hapus node diserahkan ke simpul sebelumnya untuk mengontrol temp.next = deleteNode.next; // Java akan mendaur ulangnya, dan seharusnya tidak masuk akal untuk mengaturnya ke null (saya pribadi berpikir, jika tidak benar, tolong tunjukkan ~) deletenode = null; kembali; } currentpos ++; temp = temp.next; }}

3.6 Urutkan daftar yang ditautkan

Saya sudah berbicara tentang 8 algoritma penyortiran [ringkasan delapan algoritma penyortiran]. Saya akan memilih penyortiran gelembung sederhana kali ini (sebenarnya, saya ingin menulis semacam cepat, tetapi rasanya agak sulit untuk mencobanya ...)

 / ** * Urutkan daftar yang ditautkan * * @param head * */ public static void sortLinkList (node head) {node currentNode; Node nextNode; untuk (currentNode = head.next; currentNode.next! = null; currentNode = currentNode.next) {for (nextNode = head.next; nextNode.next! = null; nextNode = nextNode.next) {if (nextNode.data> nextNode.next.data) {if nextNode.data> nextNode.next.next.data) {if nextNode.data> nextNode.NEXA) {if nextNode> nextNode. nextNode.data = nextNode.next.data; nextNode.next.data = temp; }}}}

3.7 Temukan simpul K-last di daftar tertaut

Algoritma ini cukup menarik: atur dua pointer P1 dan P2 untuk membuat node P2 K lebih cepat dari P1, dan melintasi ke belakang pada saat yang sama. Saat P2 kosong, P1 adalah Node terakhir K-th

 / *** Temukan K-th sampai simpul terakhir dalam daftar tertaut (set dua pointer P1 dan P2, buat P2 K lebih cepat dari P1, dan lintasan ke belakang pada saat yang sama. Ketika p2 kosong, P1 adalah K-th (KET NODE KED (KEP NODE, KIP (KE) KE-KE (KE) KE-KE (NODE KE (NODE KE (NODE, KIP NODE, NODE, KIP KE-KE (NODE KE (KIPKK KE) KIP KE-KE (NODE KE (NODE PUTAS POUTER, NODE, NODE, NODE, NODE, NODE, KIPK (NODE POMP NODE, NODE (NODE POMP NODE, NODE, NODE, NODE, NODE, KIPK (KE. LinkListLength (head)) NULL; mengembalikan p1;}

3.8 Hapus Data Duplikat di Daftar Tertaut

Ini mirip dengan jenis gelembung, asalkan sama, itu bisa dihapus ~

 / ** * Hapus data duplikat pada daftar tertaut (mirip dengan menggelegak, itu setara dengan penghapusan) * * @param head head node */ public static void deleteduplecate (node head) {// node sementara, (mulai dari simpul pertama-> simpul dengan data nyata) node temp = head.next; // node berikutnya dari simpul saat ini (node pertama) node nextNode = temp.next; while (temp.next! = null) {while (nextNode.next! = null) {if (nextNode.next.data == nextNode.data) {// hapus node berikutnya (node saat ini ke simpul berikutnya) nextNode.next = nextNode.next.next; } else {// lanjutkan dengan nextNode berikutnya = nextNode.next; }} // Babak berikutnya dari perbandingan temp = temp.next; }}

3.9 Kueri Node perantara dari daftar tertaut

Algoritma ini juga cukup menarik: pointer yang mengambil 1 langkah setiap kali, pointer yang mengambil 2 langkah setiap kali, dan kemudian mengambil satu langkah, yaitu node perantara

 / *** Permintaan simpul perantara dari satu daftar tertaut*/ Public Static Node SearchMID (node head) {node p1 = head; Node p2 = head; // Ambil satu langkah dan satu langkah dua langkah sampai nol. Simpul tengah yang Anda jangkau (p2! = Null && p2.next! = Null && p2.next.next! = Null) {p1 = p1.next; p2 = p2.next.next; } return p1; }

3.10 Output Tabel Single-Linked Secara Rekursif

 / *** output daftar tertaut tunggal dari ekor ke kepala oleh rekursif** @param head node*/ public static void printListreversely (node head) {if (head! = Null) {printListreversely (head.next); System.out.println (head.data); }}

3.11 Daftar Tautan Terbalik

 / *** Menerapkan inversi daftar tertaut** @param node node head dari daftar tertaut*/ node statis public reverselinklist (simpul simpul) {node prev; if (node == null || node.next == null) {prev = node; } else {node tmp = reverseLinkList (node.next); node.next.next = node; node.next = null; prev = tmp; } return prev; }

Referensi ke daftar tautan terbalik dari: //www.vevb.com/article/136185.htm

4. Akhirnya

Tidak sulit untuk memahami daftar yang ditautkan itu sendiri, tetapi dapat menyebabkan sakit kepala saat melakukan operasi terkait. head.next berikutnya berikutnya ... (Saya masih lemah dalam algoritma ... Saya tidak punya cukup otak ...) Saya menulis hal kecil ini setelah dua hari ...

Anda dapat melakukan apa pun dengan hanya mengetahui penunjuk kepalanya saat mengoperasikan daftar yang ditautkan.

1. Tambahkan data ke daftar yang ditautkan

• Traversal dan temukan simpul ekor, masukkan (hanya sementara (temp.next! = Null), dan keluar dari loop dan temukan simpul ekor)

2. Melintasi daftar yang ditautkan

• Mulai dari simpul pertama (node yang valid), asalkan bukan nol, output

3. Masukkan node ke dalam daftar tertaut di lokasi tertentu

• Pertama, tentukan apakah posisinya valid (dalam kisaran panjang daftar yang ditautkan)
• Temukan simpul sebelumnya di mana Anda ingin memasukkan, dan pointer asli dari simpul sebelumnya ditransfer dari simpul yang dimasukkan untuk menunjuk ke titik simpul sebelumnya ke simpul yang ingin Anda masukkan.

4. Dapatkan panjang daftar yang ditautkan

• Setiap kali simpul diakses, operasi variabel ++ dapat digunakan.

5. Hapus simpul di lokasi yang diberikan

• Pertama, tentukan apakah posisinya valid (dalam kisaran panjang daftar yang ditautkan)
• Temukan simpul sebelumnya di mana Anda ingin memasukkannya dan arahkan dari simpul sebelumnya ke simpul berikutnya.

6. Urutkan daftar yang ditautkan

• Urutkan mereka menggunakan algoritma gelembung

7. Temukan simpul K-last di daftar tertaut

• Atur dua pointer P1 dan P2 untuk membuat node P2 K lebih cepat dari P1, dan melintasi ke belakang secara bersamaan. Saat P2 kosong, P1 adalah Node terakhir K-th

8. Hapus data duplikat pada daftar tertaut

• Operasi ini mirip dengan jenis gelembung, asalkan sama, dapat dihapus ~

9. Permintaan node perantara dari daftar tertaut

• Algoritma ini juga cukup menarik: pointer yang mengambil 1 langkah setiap kali, pointer yang mengambil 2 langkah setiap kali, dan kemudian mengambil satu langkah, yaitu node perantara

10. Tabel Single-Linked Single Secara Rekursif

• Selama masih ada data di bawah ini, lihat ke bawah, dan rekursi adalah untuk membalik ke depan dari akhir.

11. Daftar tautan terbalik

• Ada dua cara rekursi dan non-rekursi, yang menurut saya cukup sulit. Anda dapat memeriksanya di tautan yang saya berikan ~

PS: Implementasi setiap orang akan berbeda, jadi beberapa detail kecil pasti akan berubah, dan tidak ada cara yang tetap untuk menulisnya, sehingga Anda dapat mewujudkan fungsi yang sesuai ~

Meringkaskan

Di atas adalah seluruh konten artikel ini. Saya berharap konten artikel ini memiliki nilai referensi tertentu untuk studi atau pekerjaan semua orang. Jika Anda memiliki pertanyaan, Anda dapat meninggalkan pesan untuk berkomunikasi. Terima kasih atas dukungan Anda ke wulin.com.

Referensi:

• http://www.cnblogs.com/whgk/p/6589920.html
• https://www.cnblogs.com/bywallance/p/6726251.html