配列とは異なり、各ノードにデータとポインタが存在し、そのポインタが次のノードを指すノードからなるデータ構造を連結リストと呼び、この連結リストを反転すると、逆リンクリストと呼ばれます。リストは、リストの最初のノードとリンク リストの残りの部分と呼ばれる 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 サイトの他の関連記事を参照してください。

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

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

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

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

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


ホットAIツール

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

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

Undress AI Tool
脱衣画像を無料で

Clothoff.io
AI衣類リムーバー

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

人気の記事

ホットツール

SublimeText3 Linux 新バージョン
SublimeText3 Linux 最新バージョン

Dreamweaver Mac版
ビジュアル Web 開発ツール

ゼンドスタジオ 13.0.1
強力な PHP 統合開発環境

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

VSCode Windows 64 ビットのダウンロード
Microsoft によって発売された無料で強力な IDE エディター
