doubly linked list java implementation code examples
このチュートリアルでは、Javaの二重リンクリストについて、二重リンクリストの実装、循環二重リンクリストのJavaコードと例とともに説明します。
リンクリストは、要素の順次表現です。リンクリストの各要素は「ノード」と呼ばれます。リンクリストの一種は「単一リンクリスト」と呼ばれます。
この場合、各ノードには、実際のデータを格納するデータ部分と、リスト内の次のノードへのポインターを格納する2番目の部分が含まれます。以前のチュートリアルで、単一リンクリストの詳細をすでに学習しました。
=> ここですべてのJavaチュートリアルを確認してください。
学習内容：
Javaの二重リンクリスト
リンクリストには、「二重リンクリスト」と呼ばれる別のバリエーションがあります。二重リンクリストには、データ部分とは別のノードに前のポインターと呼ばれる追加のポインターがあり、単一リンクリストのように次のポインターがあります。
二重リンクリストのノードは次のようになります。
リンクリストを表示c ++
ここで、「Prev」と「Next」は、それぞれノードの前の要素と次の要素へのポインタです。 「データ」は、ノードに保存されている実際の要素です。
次の図は、二重にリンクされたリストを示しています。
上の図は、二重にリンクされたリストを示しています。このリストには4つのノードがあります。ご覧のとおり、最初のノードの前のポインターと最後のノードの次のポインターはnullに設定されています。 nullに設定された前のポインターは、これが二重リンクリストの最初のノードであることを示し、nullに設定された次のポインターは、ノードが最後のノードであることを示します。
利点
- 各ノードには前のノードと次のノードを指すポインタがあるため、二重にリンクされたリストは、順方向と逆方向に簡単に移動できます。
- ポインタを変更するだけで、新しいノードをすばやく追加できます。
- 同様に、前のポインタと次のポインタがあるため、削除操作の場合、削除は簡単であり、単一リンクリストの場合のように、リスト全体をトラバースして前のノードを見つける必要はありません。
短所
- 二重リンクリストに追加のポインタ、つまり前のポインタがあるため、このポインタを次のポインタおよびデータ項目と一緒に格納するには、追加のメモリスペースが必要です。
- 追加、削除などのすべての操作では、前のポインターと次のポインターの両方を操作する必要があるため、操作上のオーバーヘッドが発生します。
Javaでの実装
Javaでの二重リンクリストの実装は、二重リンクリストクラス、ノードクラスの作成、および二重リンクリストへのノードの追加で構成されます。
新しいノードの追加は通常、リストの最後で行われます。次の図は、二重リンクリストの最後に新しいノードが追加されたことを示しています。
上の図に示すように、リストの最後に新しいノードを追加するために、最後のノードの次のポインターがnullではなく新しいノードを指すようになりました。新しいノードの前のポインターは、最後のノードを指します。また、新しいノードの次のポインタはnullを指しているため、新しい最後のノードになります。
以下のプログラムは、リストの最後に新しいノードが追加された、二重リンクリストのJava実装を示しています。
class DoublyLinkedList { //A node class for doubly linked list class Node{ int item; Node previous; Node next; public Node(int item) { this.item = item; } } //Initially, heade and tail is set to null Node head, tail = null; //add a node to the list public void addNode(int item) { //Create a new node Node newNode = new Node(item); //if list is empty, head and tail points to newNode if(head == null) { head = tail = newNode; //head's previous will be null head.previous = null; //tail's next will be null tail.next = null; } else { //add newNode to the end of list. tail->next set to newNode tail.next = newNode; //newNode->previous set to tail newNode.previous = tail; //newNode becomes new tail tail = newNode; //tail's next point to null tail.next = null; } } //print all the nodes of doubly linked list public void printNodes() { //Node current will point to head Node current = head; if(head == null) { System.out.println('Doubly linked list is empty'); return; } System.out.println('Nodes of doubly linked list: '); while(current != null) { //Print each node and then go to next. System.out.print(current.item + ' '); current = current.next; } } } class Main{ public static void main(String() args) { //create a DoublyLinkedList object DoublyLinkedList dl_List = new DoublyLinkedList(); //Add nodes to the list dl_List.addNode(10); dl_List.addNode(20); dl_List.addNode(30); dl_List.addNode(40); dl_List.addNode(50); //print the nodes of DoublyLinkedList dl_List.printNodes(); } } 出力：
二重リンクリストのノード：
10 20 30 40 50
リストの最後に新しいノードを追加する以外に、リストの最初またはリストの間に新しいノードを追加することもできます。読者が操作をよりよく理解できるように、この実装は読者に任せます。
Javaの循環二重リンクリスト
循環二重リンクリストは、複雑な構造の1つです。このリストでは、二重リンクリストの最後のノードに最初のノードのアドレスが含まれ、最初のノードに最後のノードのアドレスが含まれます。したがって、循環二重リンクリストでは、サイクルがあり、ノードポインタはいずれもnullに設定されません。
次の図は、循環二重リンクリストを示しています。
上の図に示すように、最後のノードの次のポインターは最初のノードを指します。最初のノードの前のポインターは、最後のノードを指します。
循環二重リンクリストは、ソフトウェア業界で幅広い用途があります。そのようなアプリケーションの1つは、プレイリストを持つ音楽アプリです。プレイリストでは、すべての曲の再生が終了すると、最後の曲の終わりに、自動的に最初の曲に戻ります。これは、循環リストを使用して行われます。
循環二重リンクリストの利点：
- 循環二重リンクリストは、頭から尾へ、または尾から頭へとトラバースできます。
- 頭から尻尾または尻尾から頭への移動は効率的で、一定の時間O（1）しかかかりません。
- フィボナッチヒープを含む高度なデータ構造を実装するために使用できます。
短所：
- 各ノードは前のポインタ用のスペースを作る必要があるため、追加のメモリが必要です。
- 循環二重リンクリストで操作を実行している間、多くのポインタを処理する必要があります。ポインタが適切に処理されない場合、実装が機能しなくなる可能性があります。
以下のJavaプログラムは、Circular二重リンクリストの実装を示しています。
import java.util.*; class Main{ static Node head; // Doubly linked list node definition static class Node{ int data; Node next; Node prev; }; // Function to insert node in the list static void addNode(int value) { // List is empty so create a single node furst if (head == null) { Node new_node = new Node(); new_node.data = value; new_node.next = new_node.prev = new_node; head = new_node; return; } // find last node in the list if list is not empty Node last = (head).prev; //previous of head is the last node // create a new node Node new_node = new Node(); new_node.data = value; // next of new_node will point to head since list is circular new_node.next = head; // similarly previous of head will be new_node (head).prev = new_node; // change new_node=>prev to last new_node.prev = last; // Make new node next of old last last.next = new_node; } static void printNodes() { Node temp = head; //traverse in forward direction starting from head to print the list while (temp.next != head) { System.out.printf('%d ', temp.data); temp = temp.next; } System.out.printf('%d ', temp.data); //traverse in backward direction starting from last node System.out.printf('
Circular doubly linked list travesed backward:
'); Node last = head.prev; temp = last; while (temp.prev != last) { System.out.printf('%d ', temp.data); temp = temp.prev; } System.out.printf('%d ', temp.data); } public static void main(String() args) { //the empty list Node l_list = null; // add nodes to the list addNode(40); addNode(50); addNode(60); addNode(70); addNode(80); //print the list System.out.printf('Circular doubly linked list: '); printNodes(); } } 出力：
循環二重リンクリスト：40 50 60 70 80
後方に移動した循環二重リンクリスト：
80 70 60 50 40
上記のプログラムでは、リストの最後にノードを追加しました。リストは循環しているため、新しいノードが追加されると、新しいノードの次のポインターは最初のノードを指し、最初のノードの前のポインターは新しいノードを指します。
同様に、新しいノードの前のポインターは、現在最後から2番目のノードになる現在の最後のノードを指します。リストの先頭とノード間の間に新しいノードを追加する実装は、リーダーに任せます。
よくある質問
Q＃1）二重リンクリストを循環させることはできますか？
回答： はい。これは、より複雑なデータ構造です。循環二重リンクリストでは、最初のノードの前のポインタには最後のノードのアドレスが含まれ、最後のノードの次のポインタには最初のノードのアドレスが含まれます。
Q＃2）二重循環リンクリストをどのように作成しますか？
回答： 二重循環リンクリストのクラスを作成できます。このクラス内には、ノードを表す静的クラスがあります。各ノードには、前と次の2つのポインターとデータ項目が含まれます。次に、ノードをリストに追加したり、リストをトラバースしたりする操作を行うことができます。
Q＃3）二重リンクリストは線形ですか、それとも循環ですか？
回答： 二重リンクリストは線形構造ですが、尾が頭を指し、頭が尾を指す円形の二重リンクリストです。したがって、それは循環リストです。
Q＃4）二重リンクリストと循環リンクリストの違いは何ですか？
回答： 二重リンクリストには、前のポインタと次のポインタをそれぞれ使用して、前のノードと次のノードに関する情報を保持するノードがあります。また、二重リンクリストでは、最初のノードの前のポインタと最後のノードの次のポインタがnullに設定されます。
循環リンクリストには、開始ノードまたは終了ノードはなく、ノードはサイクルを形成します。また、循環リンクリストでは、どのポインタもnullに設定されていません。
Q＃5）二重リンクリストの利点は何ですか？
回答： 二重リンクリストの利点は次のとおりです。
機能要件の例は_________です。
- 前方および後方に移動できます。
- 前の要素を見つけるためにリスト全体をトラバースする必要がないため、挿入操作は簡単です。
- 前のノードと次のノード、および操作が簡単であることがわかっているため、削除は効率的です。
結論
このチュートリアルでは、Javaの二重リンクリストについて詳しく説明しました。二重リンクリストは複雑な構造であり、各ノードには前のノードと次のノードへのポインタが含まれています。これらのリンクの管理は難しい場合があり、適切に処理されないとコードの故障につながる可能性があります。
全体として、二重にリンクされたリストの操作は、前のポインターと次のポインターの両方を取得しているため、リストをトラバースする時間を節約できるため、より効率的です。
循環二重リンクリストはより複雑であり、最初のノードの前のポインターが最後のノードを指し、最後のノードの次のポインターが最初のノードを指す円形パターンを形成します。この場合も、操作が効率的です。
これで、Javaのリンクリストが完成しました。 Javaでの検索とソートのテクニックに関するさらに多くのチュートリアルをお楽しみに。
=> 独占的なJavaトレーニングチュートリアルシリーズについては、こちらをご覧ください。