Java の逆方向リンクリスト

配列とは異なり、各ノードにデータとポインタが存在し、そのポインタが次のノードを指すノードからなるデータ構造を連結リストと呼び、この連結リストを反転すると、逆リンクリストと呼ばれます。リストは、リストの最初のノードとリンク リストの残りの部分と呼ばれる 2 つの部分に分割されます。そのうち、リンク リストの残りの部分に対してリバース関数が呼び出され、リンク リストの残りの部分が最初のノードにリンクされます。 、ヘッドポインタが固定されます。このトピックでは、Java の逆リンク リストについて学習します。

無料ソフトウェア開発コースを始めましょう

Web 開発、プログラミング言語、ソフトウェア テスト、その他

Java における逆リンクリストの仕組み

Java では 2 つのアルゴリズムを使用してリンク リストを反転できます。それらは次のとおりです:

1.反復アルゴリズム

以下の手順では、反復アルゴリズムがどのように機能するかを説明します。

• ptrA、ptrB、ptrC と呼ばれる 3 ポインタを初期化する必要があります。
• ptrA が最初に指しています。これは ptrA のタスクです。 ptrB は、ptrA を参照としてバックポイントとして使用します。逆リストの最後のノードは null なので、最初はこのポインタも null になります。
• ptrB は 2 位を指しています。これが主なポインタです。次の ptrB は ptrA を指しています。これにより、ポインタの既存のリンクが反転されます。
• 3 位は ptrC が指しています。このポインタは、リストが ptrB より先に失われないようにするためのバックアップのために使用されます。そうしないと、ptrB より前の参照が失われます。
• リンクされたリストの反転は、ptrA を Null に初期化することで始まります。 ptrA はリンク リストを反転した後の末尾ノードになるため、null に設定する必要があります。
• 最初のノードを指す ptrB が反転リストの末尾ノードになるため、ptrB の次は ptrA にリンクされます。
• 1 つのノードだけで構成されるリストを逆にする必要がある場合は、上記の 2 つの手順に従うことでタスクを完了できます。
• ptrB の次のリストが ptrA を指すようにすると、ptrB より前のリストへの参照が失われます。したがって、ptrA の隣に ptrB を指定する前に、ptrB の前のリストへのバックアップとして ptrC を使用します。
• 上記の手順は、ptrB が null を指すまで繰り返されます。つまり、元のリスト ノードがすべて反転されます。

2.再帰的アルゴリズム

以下の手順では、再帰的アルゴリズムがどのように機能するかを説明します。

• アルゴリズムは、先頭の時点でのノードの現在のノードを考慮することから始まります。
• 現在のノードが null の場合、それが返されます。
• 現在のノードの次の要素が null の場合、それがリストの最後のノードであることを示します。反転リストの先頭は最後のノードである必要があるため、最後のノードを先頭にして戻さなければなりません。
• リストは再帰的に走査されます。
• 電流は current.next.next に設定されます。
• current.next には Null が設定されます。

Java の逆方向リンクリストの例

以下に挙げる例は次のとおりです

例 #1

反復アルゴリズムを使用して単一リンクリストを反転する Java プログラム

コード:

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

出力:

例 #2

反復アルゴリズムを使用して単一リンクリストを反転する Java プログラム

コード:

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

出力:

結論

このチュートリアルでは、定義を通じてリンク リストを反転する概念を理解し、リンク リストを反転するロジックについて説明します。リンク リストを逆にする 2 つのアルゴリズム (反復アルゴリズム) と再帰アルゴリズムについて、Java でアルゴリズムを実装するためのプログラミング例とともに説明します。

以上がJava の逆方向リンクリストの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。