Umgekehrt verknüpfte Liste in Java

Eine Datenstruktur, die aus Knoten besteht, in denen in jedem Knoten Daten und ein Zeiger vorhanden sind und der Zeiger auf den nächsten Knoten zeigt, wird als verknüpfte Liste bezeichnet, die sich von einem Array unterscheidet, und wenn eine solche verknüpfte Liste umgekehrt wird, ist sie es auch sogenannte umgekehrte verknüpfte Liste. Dabei ist die Liste in zwei Teile unterteilt, den ersten Knoten der Liste und den Rest der verknüpften Liste, wobei die Umkehrfunktion für den Rest der verknüpften Liste aufgerufen wird und der Rest der verknüpften Liste mit dem ersten Knoten verknüpft ist , und der Kopfzeiger ist fixiert. In diesem Thema lernen wir etwas über umgekehrt verknüpfte Listen in Java.

Starten Sie Ihren kostenlosen Softwareentwicklungskurs

Webentwicklung, Programmiersprachen, Softwaretests und andere

Funktionieren einer umgekehrt verknüpften Liste in Java

Eine verknüpfte Liste kann in Java mithilfe von zwei Algorithmen umgekehrt werden. Sie sind:

1. Iterativer Algorithmus

Die folgenden Schritte beschreiben, wie ein iterativer Algorithmus funktioniert:

• Es müssen drei Zeiger initialisiert werden, die ptrA, ptrB und ptrC heißen.
• Die ptrA weist in erster Linie darauf hin. Dies ist die Aufgabe von ptrA. ptrB verwendet ptrA als Referenz, um zurück zu verweisen. Da der letzte Knoten in der umgekehrten Liste null ist, ist dieser Zeiger zunächst ebenfalls null.
• Der ptrB weist auf den zweiten Platz hin. Dies ist der Haupthinweis. Der nächste von ptrB zeigt auf ptrA, und auf diese Weise wird die bestehende Verknüpfung der Zeiger umgekehrt.
• Der dritte Platz wird vom ptrC vergeben. Die Verwendung dieses Zeigers dient der Sicherung, um sicherzustellen, dass die Liste nicht vor ptrB verloren geht. Andernfalls kommt es zum Verlust von Referenzen vor ptrB.
• Das Umkehren der verknüpften Liste beginnt mit der Initialisierung von ptrA auf Null. Es muss auf Null gesetzt werden, da ptrA nach der Umkehrung der verknüpften Liste der Endknoten sein wird.
• Der nächste von ptrB ist mit ptrA verknüpft, da der ptrB, der auf den ersten Knoten zeigt, zum Endknoten in der umgekehrten Liste wird.
• Wenn die Liste, die nur aus einem Knoten besteht, umgekehrt werden muss, kann die Aufgabe durch Befolgen der beiden oben genannten Schritte abgeschlossen werden.
• Der Verweis auf die Liste vor ptrB geht verloren, wenn der nächste von ptrB auf ptrA verweist. Daher werden wir ptrC als Backup für die Ahead-Liste von ptrB verwenden, bevor wir ptrBs neben ptrA verweisen.
• Die obigen Schritte werden wiederholt, bis der ptrB auf Null zeigt, was bedeutet, dass alle ursprünglichen Listenknoten umgekehrt sind.

2. Rekursiver Algorithmus

Die folgenden Schritte beschreiben, wie ein rekursiver Algorithmus funktioniert:

• Der Algorithmus beginnt mit der Berücksichtigung des Knotenstroms ab dem Kopf.
• Wenn der Knotenstrom null ist, wird er zurückgegeben.
• Wenn das nächste Element des aktuellen Knotens null ist, bedeutet dies, dass es sich um den letzten Knoten in der Liste handelt. Der Kopf der umgekehrten Liste muss der letzte Knoten sein, und daher muss der letzte Knoten als Kopf erstellt und dann zurückgegeben werden.
• Die Liste wird rekursiv durchlaufen.
• Der Strom wird auf current.next.next gesetzt.
• Null wird auf current.next gesetzt.

Beispiele für umgekehrt verknüpfte Listen in Java

Hier sind die folgenden Beispiele aufgeführt

Beispiel #1

Java-Programm zum Umkehren einer einfach verknüpften Liste mithilfe eines iterativen Algorithmus

Code:

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);
}
}

Ausgabe:

Beispiel #2

Java-Programm zum Umkehren einer einfach verknüpften Liste mithilfe eines iterativen Algorithmus

Code:

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);
}
}

Ausgabe:

Fazit

In diesem Tutorial verstehen wir das Konzept der Umkehrung der verknüpften Liste durch Definition und erklären die Logik, nach der die verknüpfte Liste umgekehrt wird. Es werden die beiden Algorithmen zum Umkehren der verknüpften Liste erläutert, bei denen es sich um einen iterativen Algorithmus handelt, und der rekursive Algorithmus wird zusammen mit den Programmierbeispielen zur Implementierung der Algorithmen in Java erläutert.

Das obige ist der detaillierte Inhalt vonUmgekehrt verknüpfte Liste in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!