リンクリストは複雑なデータ構造です。データ間の関係により、リンクリストは、単一のリンクリスト、回覧リンクリスト、双方向リンクリストの3つのタイプに分割されます。以下は1つずつ導入されます。リンクされたリストは、データ構造の基本的および重要な知識ポイントです。ここでは、Javaのリンクリストの実装について説明します。
Javaリンクリスト操作:単一リンクリストとダブルリンクリスト
いくつかのポイントが主に話します:
1。リンクリストの紹介
2。リンクされたリストの実装の原則と必需品
3。一本鎖の例
4。ダブルリンクの例
1。リンクリストの紹介
リンクリストは、比較的一般的なデータ構造です。リンクされたリストは保存するのがより複雑ですが、クエリをするときはより便利です。それに応じて複数のコンピューター言語で使用されます。リンクされたリストには多くのカテゴリがあります。記事は、単一リンクリストと二重リンクリストについて分析されます。リンクリストのデータは、チェーンで一緒に接続されているようなもので、データに簡単にアクセスできます。
2。リンクされたリストの実装の原則と必需品
ここでは、単一リンクリストと二重リンクリストのみが分析されます。リンクされたリストの実装プロセスは少し複雑ですが、多くの利点をもたらします。たとえば、オンラインショッピングが到着すると、商人は通常、商品を箱に詰めて、箱に住所情報を書きます。 Express Companyは、ボックス上の情報を通じて買い手を見つけることができ、商品はそのまま到着します。箱の保護がなければ、製品は途中で損傷している可能性があります。リンクリストは、アドレス情報が書かれたボックスのようなもので、製品情報を保護するだけでなく、物流情報も書き込みます。リンクリストには、「機関車」と同様のヘッドノードがあります。対応するヘッドノードが見つかっている限り、リンクリストで動作できます。この分析では、ヘッドノードはデータヘッダーとしてのみ機能し、有効なデータを保存しません。
単一のリンクリストの実装原則を図に示します。
ダブルリンクリストの実装原則:
3。一本鎖の例
icommoperate <t>インターフェイス操作クラス:
パッケージlinklisttest; import java.util.map; public interface icommoperate <t> {public boolean insertnode(t node); public boolean insertsoposnode(int pos、t node); public boolean deleteNode(int pos、map <string、object> map); public void printlink();}シングルリンクリストノード:
パッケージlinklisttest; //シングル接続テーブルノードパブリッククラスsnode {private string data;プライベートスノードNextNode; public snode(){} public snode(string data){this.data = data; this.nextnode = new Snode(); } public string getData(){return data; } public void setData(string data){this.data = data; } public Snode getNextNode(){return nextNode; } public void setNextNode(snode nextNode){this.nextNode = nextNode; } @Override public String toString(){return "snode [data =" + data + "]"; }}シングルリンク操作クラス:
パッケージlinklisttest; import java.util.hashmap; import java.util.map; public class singlelinklistを実装<snode> {private snode head = new Snode( "head"); //公開ヘッダーポインター、宣言後に変更されていないプライベートint size = 0; public int getSize(){return this.size; } / * *リンクリストを挿入し、毎回端に挿入します * / @Override public boolean insertnode(snode node){boolean flag = false; Snode Current = this.head; if(this.size == 0){//空のリンクリストthis.head.setNextNode(node); node.setNextNode(null); } else {//リンクリストのnode while(current.getNextNode()!= null){current = current.getNextNode(); } current.setNextNode(node); node.setNextNode(null); } this.size ++; flag = true;フラグを返します。 } / * *リンクリストにPOSの指定された位置を挿入し、1から開始し、POSはサイズより大きくなり、リンクリストの端を挿入します * * / @Override public boolean insertsoposnode(int pos、snode node){boolean flag = true; snode current = this.head.getNextNode(); if(this.size == 0){//空のリンクリストthis.head.setNextNode(node); node.setNextNode(null); this.size ++; } else if(this.size <pos){// pos位置は、リンクリストの長さ、insertnode(node); } else if(pos> 0 && pos <= this.size){//リンクリストのノード// 1。 Snode Prenode = this.head; //フロントノードSnode CurrentNode = current; //現在のノードwhile(<pos-1 && currentNode.getNextNode()!= null){prenode = current; //フロントノードは後方に移動しますcurrentNode = currentNode.getNextNode(); //現在のノードは逆方向に移動します++; } // System.out.println(prenode); // System.out.println(currentNode); //2。NodePrenode.setNextNode(ノード)を挿入します。 node.setNextNode(currentNode); this.size ++; System.out.println( "ノードがリンクリストに挿入されました"); } else {system.out.println( "Position Information error"); flag = false; } flagを返します。 } / * *リンクリストのノードPOを指定し、対応するノードを削除します。方法:フロントとリアのノードを見つけて削除して削除します。 1 * */ @Override public boolean deleteNode(int pos){boolean flag = false;からsnode current = this.head.getNextNode(); if(pos <= 0 || pos> this.size || current == null){system.out.println( "リンクリストの情報のエラーまたは情報なし"); } else {// 1。フロントノードとバックノードを検索してint int = 0;を削除します。 Snode Prenode = this.head; //フロントノードスノードNextNode = current.getNextNode(); //バックノードwhile(<pos-1 && nextnode.getNextNode()!= null){prenode = current; //フロントノードが[NextNode = nextNode.getNextNode(); //バックノードが移動されますfind ++; } // System.out.println(prenode); // System.out.println(nextnode); //2。NodePrenode.SetNextNode(NextNode)を削除します。 System.gc(); this.size--; flag = true; } flagを返します。 } / * *リンクリストのノードPOを指定し、対応するノードを変更します。 1 * */ @Override public boolean updatenode(int pos、map <string、object> map){boolean flag = false; snode node = getNode(pos、map); //対応する位置でノードを取得するif(node!= null){string data =(string)map.get( "data"); node.setdata(data); flag = true; } flagを返します。 } / * * 1 * / @Override public Snode getNode(int pos、map <string、object> map){snode current = this.head.getNextnode(); if(pos <= 0 || pos> this.size || current == null){system.out.println( "位置情報が正しくないか、リンクリストが存在しない"); nullを返します。 } int find = 0; while(find <pos-1 && current!= null){current = current.getNextNode(); ++を見つけます; } return current; } / * *リンクリストを印刷 * * / @Override public void printlink(){int length = this.size; if(length == 0){system.out.println( "リンクリストは空です!");戻る ; } snode current = this.head.getNextNode(); int find = 0; system.out.println( "ノードの総数:" + length + "one"); while(current!= null){system.out.println( "th" ++(++ find) + "nodes:" + current); current = current.getNextNode(); }} public static void main(string [] args){singlelinkList sll = new SingleLinkList(); snode node1 = new Snode( "node1"); snode node2 = new Snode( "node2"); snode node3 = new Snode( "node3"); snode node4 = new Snode( "node4"); snode node5 = new Snode( "node5"); snode node6 = new Snode( "指定位置を挿入"); sll.insertposnode(sll.getsize()+1、node1); sll.insertposnode(sll.getsize()+1、node2); sll.insertposnode(sll.getsize()+1、node3); sll.insertposnode(sll.getsize()+1、node4); sll.insertposnode(sll.getsize()+1、node5); // sll.insertnode(node1); // sll.insertnode(node2); // sll.insertnode(node3); // sll.insertnode(node4); // sll.insertnode(node5); System.out.println( "******************************"); sll.printlink(); System.out.println( "*******************************"); int pos = 2; System.out.println( ""+pos+"リンクリストの位置データを取得します:"+sll.getNode(pos、null)); System.out.Println( "****************************リンクされたリストの指定された位置にノードを挿入************************************); int pos1 = 2; system.out.println( "データを"+pos1+"" nodes: "); sll.insertposnode(pos1、node6); sll.printlink(); system.out.println(" ************************************ delete delete quatifed node of the linked liked figt ******************************** int pos2 = 2;リスト*************************************** "); int pos3 = 2; system.out.println(" "+pos3+" nodes: "); map <string、object> map = new hashmap <>(); map.put(" data "、"これはテストです ")4。ダブルリンクの例
icommoperate <t>インターフェイス操作クラス:
パッケージlinklisttest; import java.util.map; public interface icommoperate <t> {public boolean insertnode(t node); public boolean insertsoposnode(int pos、t node); public boolean deleteNode(int pos、map <string、object> map); public void printlink();}ダブルリンクリストノード:
パッケージlinklisttest; // dual-contiguousテーブルノードパブリッククラスdnode {private dnode priornode;プライベート文字列データ。プライベートDNODE NEXTNODE; public dnode(){} public dnode(string data){this.priornode = new dnode(); this.data = data; this.nextnode = new dnode(); } public dnode getPriorNode(){return priornode; } public void setPriorNode(dnode priornode){this.priornode = priornode; } public string getData(){return data; } public void setData(string data){this.data = data; } public dnode getNextNode(){return nextNode; } public void setNextNode(dnode nextNode){this.nextNode = nextNode; } @Override public String toString(){return "dnode [data =" + data + "]"; }}ダブルリンクリスト実装クラス:
パッケージlinklisttest; import java.util.hashmap; import java.util.map; public class doublelinklistを実装<dnode> {private dnode head = new dnode( "head");プライベートINTサイズ= 0; public int getSize(){return this.size; } / * *リンクされたリストを挿入し、毎回最後に挿入 * dnode current = this.head; if(this.size == 0){//空のリンクリストthis.head.setNextNode(node); node.setPriorNode(this.head); node.setNextNode(null); } else {//リンクリストのnode while(current.getNextNode()!= null){current = current.getNextNode(); } current.setNextNode(node); node.setNextNode(null); node.setPriorNode(current); } this.size ++; flag = true;フラグを返します。 } / * *リンクリストのPOSの指定された位置を挿入します。1からは、POSはサイズより大きくなり、リンクリストの端を挿入します * * / @Override public boolean insertposNode(int pos、dnodeノード){boolean flag = true; dnode current = this.head.getNextNode(); if(this.size == 0){//リンクリストは空です。 node.setNextNode(null); node.setPriorNode(this.head); this.size ++; } else if(pos> this.size){// pos位置はリンクリストの長さよりも大きく、end insertnode(node)を挿入します。 } else if(pos> 0 && pos <= this.size){//リンクリストのノード// while(find <pos-1 && current.getNextNode()!= null){current = current.getNextNode(); ++を見つけます; } // 2。node if(current.getNextNode()== null){// tail node node.setpriorNode(current); node.setNextNode(null); current.setNextNode(node); } else if(current.getNextNode()!= null){//中間node node.setpriorNode(current.getPriorNode()); node.setNextNode(current); current.getPriorNode()。setNextNode(node); current.setPriorNode(ノード); } this.size ++; } else {system.out.println( "Position Information error"); flag = false; } flagを返します。 } / * *リンクリストのノードPOSを指定し、1 * / @Override public boolean deleteNode(int pos){boolean flag = false;から始まる対応するノードを削除します。 dnode current = this.head.getNextNode(); if(pos <= 0 || pos> this.size || current == null){system.out.println( "位置情報が正しくないか、リンクリストが存在しない"); } else {// 1。削除される場所を見つけるpos node int find = 0; while(find <pos-1 && current.getNextNode()!= null){current = current.getNextNode(); ++を見つけます; } // 2。node node if(current.getNextNode()== null){// tail node current.getPriorNode()。setNextNode(null); } else if(current.getNextNode()!= null){//中間node current.getPriorNode()。setNextNode(current.getNextNode()); current.getNextNode()。setPriorNode(current.getPriorNode()); } system.gc(); this.size--; flag = true; } flagを返します。 } / * *リンクリストのノードPOを指定し、対応するノードを変更します。 1 * */ @Override public boolean updatenode(int pos、map <string、object> map){boolean flag = false; dnode node = getNode(pos、map); if(node!= null){string data =(string)map.get( "data"); node.setdata(data); flag = true; } flagを返します。 } / * *指定されたリンクリストのノードPOSを見つけ、1 * * / @Override public dnode getNode(int pos、map <string、object> map){dnode current = this.head.getNextNode(); if(pos <= 0 || pos> this.size || current == null){system.out.println( "位置情報が正しくないか、リンクリストが存在しない"); nullを返します。 } int find = 0; while(find <pos-1 && current!= null){current = current.getNextNode(); ++を見つけます; } return current; } / * *リンクリストを印刷 * * / @Override public void printlink(){int length = this.size; if(length == 0){system.out.println( "リンクリストは空です!");戻る ; } dnode current = this.head.getNextNode(); int find = 0; system.out.println( "ノードの総数:" + length + "one"); while(current!= null){system.out.println( "th" ++(++ find) + "nodes:" + current); current = current.getNextNode(); }} public static void main(string [] args){doubleLelinkList dll = new DoubleLinkList(); dnode node1 = new dnode( "node1"); dnode node2 = new dnode( "node2"); dnode node3 = new dnode( "node3"); dnode node4 = new dnode( "node4"); dnode node5 = new dnode( "node5"); dnode node6 = new dnode( "指定された位置を挿入"); dll.insertposnode(10、node1); dll.insertposnode(10、node2); dll.insertposnode(10、node3); dll.insertposnode(10、node4); dll.insertposnode(10、node5); // dll.insertnode(node1); // dll.insertnode(node2); // dll.insertnode(node3); // dll.insertnode(node4); // dll.insertnode(node5); System.out.println( "******************************"); dll.printlink(); System.out.println( "****************************************); int pos = 2; system.out.println( ""+pos+"リンクリストの位置データを取得:"+dll.getNode(pos、null)); System.out.Println( "****************************リンクされたリストの指定された位置にノードを挿入************************************); int pos1 = 2; system.out.println( "データを"+pos1+"nodes:"); dll.insertposnode(pos1、node6); dll.printlink(); System.out.println( "*******************************リンクリストで指定されたノードを削除*************************************"); int pos2 = 7; System.out.println( "delete"+pos2+"nodes:"); dll.deletenode(pos2); dll.printlink(); System.out.println( "***********************************リンクリストで指定されたノードを変更****************************************************); int pos3 = 2; system.out.println( ""+pos3+"nodes:"); map <string、object> map = new Hashmap <>(); map.put( "data"、 "これはテストです"); dll.updatenode(POS3、MAP); dll.printlink(); }}読んでくれてありがとう、私はそれがあなたを助けることができることを願っています。このサイトへのご支援ありがとうございます!