Senarai Pautan Terbalik di Java

Struktur data yang terdiri daripada nod di mana data dan penuding hadir dalam setiap nod dan penuding menghala ke nod seterusnya dipanggil Senarai Terpaut yang berbeza daripada tatasusunan, dan apabila senarai terpaut sedemikian diterbalikkan, ia adalah dipanggil senarai pautan terbalik. Di mana senarai itu dibahagikan kepada dua bahagian yang dipanggil nod pertama senarai dan selebihnya senarai terpaut, antaranya fungsi terbalik dipanggil untuk senarai terpaut yang lain dan senarai terpaut selebihnya dipautkan ke nod pertama. , dan penunjuk kepala ditetapkan. Dalam topik ini, kita akan belajar tentang Senarai Terpaut Songsang dalam Java.

Mulakan Kursus Pembangunan Perisian Percuma Anda

Pembangunan web, bahasa pengaturcaraan, ujian perisian & lain-lain

Menggunakan senarai terpaut terbalik dalam Java

Senarai terpaut boleh diterbalikkan dalam java menggunakan dua algoritma. Mereka ialah:

1. Algoritma Lelaran

Langkah di bawah menerangkan cara algoritma lelaran berfungsi:

• Tiga mata mesti dimulakan, yang dipanggil ptrA, ptrB dan ptrC.
• PtrA menunjuk di tempat pertama. Ini adalah tugas ptrA. ptrB menggunakan ptrA sebagai rujukan untuk menunjuk ke belakang. Memandangkan nod terakhir dalam senarai terbalik adalah null, pada mulanya, penunjuk ini juga akan menjadi null.
• PtrB menunjuk ke tempat kedua. Ini adalah petunjuk utama. PtrB seterusnya dihalakan ke ptrA, dan ini adalah cara pautan penuding sedia ada diterbalikkan.
• Tempat ketiga ditunjuk oleh ptrC. Menggunakan penunjuk ini adalah untuk sandaran untuk memastikan senarai tidak hilang sebelum ptrB; jika tidak, ia menyebabkan kehilangan rujukan lebih awal daripada ptrB.
• Pembalikan senarai terpaut bermula dengan memulakan ptrA kepada Null. Ia mesti ditetapkan kepada null kerana ptrA akan menjadi nod ekor selepas membalikkan senarai terpaut.
• PtrB seterusnya dipautkan kepada ptrA kerana ptrB, yang menghala ke nod pertama, menjadi nod ekor dalam senarai terbalik.
• Jika senarai yang mengandungi hanya satu nod perlu diterbalikkan, maka mengikut dua langkah di atas boleh menyelesaikan tugasan.
• Rujukan kepada senarai di hadapan ptrB akan hilang apabila ptrB seterusnya dibuat untuk menunjuk kepada ptrA. Jadi kami akan menggunakan ptrC sebagai sandaran ke senarai hadapan ptrB sebelum menunjuk ptrB di sebelah ptrA.
• Langkah di atas diulang sehingga ptrB menghala ke null, yang bermaksud semua nod senarai asal diterbalikkan.

2. Algoritma Rekursif

Langkah di bawah menerangkan cara algoritma rekursif berfungsi:

• Algoritma bermula dengan mempertimbangkan arus nod sebagai kepala.
• Jika arus nod adalah nol, maka ia dikembalikan.
• Jika elemen seterusnya nod semasa adalah nol, ia menunjukkan ia adalah nod terakhir dalam senarai. Ketua senarai terbalik mestilah nod terakhir, dan oleh itu nod terakhir mesti dibuat sebagai kepala dan kemudian kembali.
• Senarai dilalui secara rekursif.
• Arus ditetapkan kepada semasa.seterusnya.seterusnya.
• Null ditetapkan kepada current.next.

Contoh Senarai Terpaut Songsang dalam Java

Berikut ialah contoh berikut yang disebut di bawah

Contoh #1

Atur cara Java untuk membalikkan senarai pautan tunggal menggunakan algoritma lelaran

Kod:

class List
{
static Node head1;
static class Node
{
int data1;
Node nex;
Node(int d1)
{
data1 = d1;
nex = null;
}
}
//The linked list is reversed using this function
Node reverselist(Node node1)
{
Node previous = null;
Node curr = node1;
Node nex = null;
while (curr != null)
{
nex = curr.nex;
curr.nex = previous;
previous = curr;
curr = nex;
}
node1 = previous;
return node1;
}
// The contents of linked list are printed
void printL(Node node1)
{
while (node1 != null)
{
System.out.print(node1.data1 + " ");
node1 = node1.nex;
}
}
public static void main(String[] args)
{
//The values to be inserted in the list before reversing are given here
List l = new List();
l.head1 = new Node(30);
l.head1.nex = new Node(40);
l.head1.nex.nex = new Node(50);
l.head1.nex.nex.nex = new Node(60);
System.out.println("The items in the linked list that needs to be reversed are");
l.printL(head1);
//Function to reverse the list is called here
head1 = l.reverselist(head1);
System.out.println("");
System.out.println("The items in the reversed linked list are");
l.printL(head1);
}
}

Output:

Contoh #2

Atur cara Java untuk membalikkan senarai pautan tunggal menggunakan algoritma lelaran

Kod:

class List {
static Node head1;
static class Node {
int data1;
Node nex;
Node(int d1)
{
data1 = d1;
nex = null;
}
}
// A recursive function to reverse the linked list
Node reverse(Node current, Node previous)
{
//Last node is marked as head
if (current.nex == null) {
head1 = current;
//previous node is updated with next
current.nex = previous;
return head1;
}
//current.nex node is saved for the recursive call
Node nex1 = current.nex;
//nex is updated
current.nex = previous;
reverse(nex1, current);
return head1;
}
// Content of the reversed linked list are printed
void printL(Node node)
{
while (node != null) {
System.out.print(node.data1 + " ");
node = node.nex;
}
}
//Main method is called which prints the reversed linked list by calling the function
public static void main(String[] args)
{
//The values to be inserted in the list before reversing are given here
List list = new List();
list.head1 = new Node(20);
list.head1.nex = new Node(30);
list.head1.nex.nex = new Node(40);
list.head1.nex.nex.nex = new Node(50);
System.out.println("The items in the linked list that needs to be reversed are");
list.printL(head1);
//Function to reverse the list is called here
Node result = list.reverse(head1, null);
System.out.println("");
System.out.println("");
System.out.println("The items in the reversed linked list are");
list.printL(result);
}
}

Output:

Kesimpulan

Dalam tutorial ini, kami memahami konsep menterbalikkan senarai terpaut melalui definisi, logik di mana senarai terpaut diterbalikkan dijelaskan. Kedua-dua algoritma untuk membalikkan senarai terpaut diterangkan, yang merupakan algoritma berulang dan algoritma rekursif diterangkan bersama-sama dengan contoh pengaturcaraan untuk melaksanakan algoritma dalam java.

Atas ialah kandungan terperinci Senarai Pautan Terbalik di Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!