検索
ホームページJava&#&チュートリアルJava の逆方向リンクリスト

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

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

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

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

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

Java の逆方向リンクリスト

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

出力:

Java の逆方向リンクリスト

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

出力:

Java の逆方向リンクリスト

結論

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

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

声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
高度なJavaプロジェクト管理、自動化の構築、依存関係の解像度にMavenまたはGradleを使用するにはどうすればよいですか?高度なJavaプロジェクト管理、自動化の構築、依存関係の解像度にMavenまたはGradleを使用するにはどうすればよいですか?Mar 17, 2025 pm 05:46 PM

この記事では、Javaプロジェクト管理、自動化の構築、依存関係の解像度にMavenとGradleを使用して、アプローチと最適化戦略を比較して説明します。

適切なバージョン化と依存関係管理を備えたカスタムJavaライブラリ(JARファイル)を作成および使用するにはどうすればよいですか?適切なバージョン化と依存関係管理を備えたカスタムJavaライブラリ(JARファイル)を作成および使用するにはどうすればよいですか?Mar 17, 2025 pm 05:45 PM

この記事では、MavenやGradleなどのツールを使用して、適切なバージョン化と依存関係管理を使用して、カスタムJavaライブラリ(JARファイル)の作成と使用について説明します。

カフェインやグアバキャッシュなどのライブラリを使用して、Javaアプリケーションにマルチレベルキャッシュを実装するにはどうすればよいですか?カフェインやグアバキャッシュなどのライブラリを使用して、Javaアプリケーションにマルチレベルキャッシュを実装するにはどうすればよいですか?Mar 17, 2025 pm 05:44 PM

この記事では、カフェインとグアバキャッシュを使用してJavaでマルチレベルキャッシュを実装してアプリケーションのパフォーマンスを向上させています。セットアップ、統合、パフォーマンスの利点をカバーし、構成と立ち退きポリシー管理Best Pra

キャッシュや怠zyなロードなどの高度な機能を備えたオブジェクトリレーショナルマッピングにJPA(Java Persistence API)を使用するにはどうすればよいですか?キャッシュや怠zyなロードなどの高度な機能を備えたオブジェクトリレーショナルマッピングにJPA(Java Persistence API)を使用するにはどうすればよいですか?Mar 17, 2025 pm 05:43 PM

この記事では、キャッシュや怠zyなロードなどの高度な機能を備えたオブジェクトリレーショナルマッピングにJPAを使用することについて説明します。潜在的な落とし穴を強調しながら、パフォーマンスを最適化するためのセットアップ、エンティティマッピング、およびベストプラクティスをカバーしています。[159文字]

Javaのクラスロードメカニズムは、さまざまなクラスローダーやその委任モデルを含むどのように機能しますか?Javaのクラスロードメカニズムは、さまざまなクラスローダーやその委任モデルを含むどのように機能しますか?Mar 17, 2025 pm 05:35 PM

Javaのクラスロードには、ブートストラップ、拡張機能、およびアプリケーションクラスローダーを備えた階層システムを使用して、クラスの読み込み、リンク、および初期化が含まれます。親の委任モデルは、コアクラスが最初にロードされ、カスタムクラスのLOAに影響を与えることを保証します

See all articles

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

SublimeText3 Linux 新バージョン

SublimeText3 Linux 新バージョン

SublimeText3 Linux 最新バージョン

Dreamweaver Mac版

Dreamweaver Mac版

ビジュアル Web 開発ツール

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

mPDF

mPDF

mPDF は、UTF-8 でエンコードされた HTML から PDF ファイルを生成できる PHP ライブラリです。オリジナルの作者である Ian Back は、Web サイトから「オンザフライ」で PDF ファイルを出力し、さまざまな言語を処理するために mPDF を作成しました。 HTML2FPDF などのオリジナルのスクリプトよりも遅く、Unicode フォントを使用すると生成されるファイルが大きくなりますが、CSS スタイルなどをサポートし、多くの機能強化が施されています。 RTL (アラビア語とヘブライ語) や CJK (中国語、日本語、韓国語) を含むほぼすべての言語をサポートします。ネストされたブロックレベル要素 (P、DIV など) をサポートします。

VSCode Windows 64 ビットのダウンロード

VSCode Windows 64 ビットのダウンロード

Microsoft によって発売された無料で強力な IDE エディター