シミュレートされたシングルリンクテーブル
線形テーブル:
線形テーブル(シーケンシャルテーブルとも呼ばれます)は、最も基本的で、最も単純で、最も一般的に使用されるデータ構造です。
線形テーブルのデータ要素間の関係は、1対1の関係です。つまり、最初と最後のデータ要素を除き、他のデータ要素が最後に接続されています。
線形テーブルの論理構造はシンプルで、実装して動作しやすいです。
実際のアプリケーションでは、線形テーブルは、スタック、キュー、文字列などの特別な線形テーブルの形で使用されます。
線形構造の基本的な特性は次のとおりです。
1.コレクションには一意の「最初の要素」が必要です。
2。コレクションには一意の「最後の要素」が必要です。
3。最後の要素を除いて、ユニークな後継者(最新のアイテム)があります。
4.最初の要素を除いて、ユニークなフロントドライブ(フロントピース)があります。
リンクリスト:リンクリスト
リンクされたリストは、物理的なストレージユニットの非連続的で非シーケンシャルストレージ構造です。データ要素の論理的順序は、リンクリストのポインターリンク順序を介して実装された各データ項目が「リンクポイント」に含まれていることです。
リンクはクラスのオブジェクトであり、このタイプはリンクと呼ばれます。リンクリストには多くの同様のリンクがあり、各リンクには次のリンクを参照するフィールドが含まれています。
リンクされたリストオブジェクト自体は、最初のリンクノードへの参照を保持します。 (最初にない場合、それは見つけることができません)
リンクされたリストは、配列などのデータ項目に直接アクセスすることはできません(サブスクリプトを使用)。つまり、データ間の関係に配置する必要があります。つまり、リンクノードで参照される次のリンクにアクセスし、次のリンクにアクセスし、必要なデータにアクセスし、ヘッドで必要なデータを挿入および削除する時間の複雑さはO(1)です。これらの操作には、リンクリスト内のノードの半分を検索するのが必要であり、O(n)の効率が必要です。
単一のリンクリスト:
線形テーブルは「ノードのシーケンス」で表され、線形リンクリスト(単一のリンクリスト)と呼ばれます
これは、任意のアドレスを備えた一連のストレージユニットを使用して、データ要素を線形テーブルに保存するチェーンアクセスデータ構造です。 (この一連のメモリセルは、連続的または不連続にすることができます)
リンクノードの構造:
ノード値を保存するデータフィールドデータ。次にノードリファレンスを保存するポインターフィールド(チェーンフィールド)
リンクされたリストは、各ノードのリンクドメインを介して、線形テーブルのnノードを論理的順序でリンクします。
ノードごとに1つのリンクフィールドのみを持つリンクリストは、単一のリンクリストと呼ばれます。一方向には、後続の結節への言及のみがあります。
/***シングルリンクリスト:ヘッダー挿入方法と最初の出口*リンクリストの左側はチェーンヘッドと呼ばれ、右側はチェーンテールと呼ばれます。 *単一のリンクリストを作成するヘッダー挿入方法は、リンクリストの右端を固定として表示することにより取得され、リンクされたリストは左に拡張され続けます。 *ヘッダー挿入方法から最初に来るのは、テールノード * @Author Stone */ public class singlelinkedlist <t> {private link <t> first; //最初のノードpublic singlelinkedlist(){} public boolean isempty(){return first == null; } public void insertFirst(t data){//チェーンリンクのヘッドに挿入<t> newlink = new link <t>(data); newlink.next = first; //新しいノードの次のポイント前のノードfirst = newLink; } public link <t> deleteFirst(){//チェーンヘッダーリンク<t> temp = first;を削除します。 first = first.next; //最初のノードを変更して温度を返します。 } public link <t> find(t t){link <t> find = first; while(find!= null){if(!find.data.equals(t)){find = find.next; } else {break; }} return find; } public link <t> delete(t t){if(isempty()){return null; } else {if(first.data.equals(t)){link <t> temp = first; first = first.next; //最初のノードを次のノードに戻すTEMPに変更します。 }} link <t> p = first; link <t> q = first; while(!p.data.equals(t)){if(p.next == null){//チェーンの最後までサインアップしますが、return nullが見つかりません。 } else {q = p; p = p.next; }} q.next = p.next; pを返します。 } public void displaylist(){// transip system.out.println( "list(first-> last):"); link <t> current = first; while(current!= null){current.displaylink(); current = current.next; }} public void displaylistreverse(){//逆トラバーサルリンク<t> p = first、q = first.next、t; (q!= null){//ポインターが逆になっている場合、トラバースされたデータ順序は後方t = q.nextです。 // no3 if(p == first){//元のヘッダーである場合、ヘッドの.nextは空のp.next = null; } q.next = p; // no3-> no1 pointer Reverse p = q; // startは逆ですq = t; // no3 start} //上記のループの場合、first.nextは空で、qがnullでループを実行しない場合、pは元のほとんどのデータ項目です。反転後、pはfirst first = pに割り当てられます。 displaylist(); } class link <t> {// link point t data; //データフィールドリンク<t> next; //後続のポインター、ノードチェーンドメインリンク(tデータ){this.data = data; } void displaylink(){system.out.println( "データは" + data.toString()); }} public static void main(string [] args){singlelinkedlist <integer> list = new singlelinkedlist <integer>(); list.insertfirst(33); list.insertfirst(78); list.insertfirst(24); list.insertfirst(22); list.insertfirst(56); list.displaylist(); list.deletefirst(); list.displaylist(); system.out.println( "find:" + list.find(56)); system.out.println( "find:" + list.find(33)); system.out.println( "delete find:" + list.delete(99)); system.out.println( "delete find:" + list.delete(24)); list.displaylist(); system.out.println( "--- reverse ----"); list.displaylistreverse(); }}印刷
list(first-> last):データは56です。データは22です。データは24です。データは78です。データは33リスト(最初 - > last):データは22です。 Find:linked_list.singlelinkedlist$link@17dfafd1リスト(最初 - > last):データは22です。データは78です。
シングルリンクリスト:テール挿入方法、最初に戻る - リンクリストの左端が固定されている場合、リンクリストが右に拡張され続けます。このリンクリストを確立するこの方法は、テール挿入方法と呼ばれます。
テール挿入方法でリンクリストを作成する場合、ヘッドポインターが固定されているため、リンクリストの右に伸びるためにテールポインターを設定する必要があります。
テール挿入方法から最初に来るのは、ヘッドノードです。
Public Class SingLeLinkedList2 <T> {private link <t> head; //最初のノードpublic singlelinkedlist2(){} public boolean isempty(){return head == null; } public void insertlast(t data){// insert link <t> newlink = new link <t>(data); if(head!= null){link <t> nextp = head.next; if(nextp == null){head.next = newLink; } else {link <t> rece = null; while(nextp!= null){rece = nextp; nextp = nextp.next; } rece.next = newLink; }} else {head = newLink; }} public link <t> deletelast(){//チェーンリンクのテールを削除<t> p = head; link <t> q = head; (p.next!= null){// pの次のノードは空ではありません、qは現在のpに等しくなります(つまり、qは前のもの、pは次のものです)。ループが終了すると、qはチェーンの最後から2番目の端に等しくなりますq = p。 p = p.next; } //削除q.next = null; pを返します。 } public link <t> find(t t){link <t> find = head; while(find!= null){if(!find.data.equals(t)){find = find.next; } else {break; }} return find; } public link <t> delete(t t){if(isempty()){return null; } else {if(head.data.equals(t)){link <t> temp = head; head = head.next; //最初のノードを変更して温度を返します。 }} link <t> p = head; link <t> q = head; while(!p.data.equals(t)){if(p.next == null){//は、チェーンの最後にnullが見つかっていないことを意味します。 } else {q = p; p = p.next; }} q.next = p.next; pを返します。 } public void displaylist(){// Travel System.out.println( "list(head-> last):"); link <t> current = head; while(current!= null){current.displaylink(); current = current.next; }} public void displaylistreverse(){//逆トラバーサルリンク<t> p = head、q = head.next、t; while(q!= null){//ポインターが逆になり、トラバースされたデータ順序は後方t = q.nextです。 // no3 if(p == head){//元のヘッダーである場合、ヘッドの.nextは空のp.next = nullである必要があります。 } q.next = p; // no3-> no1 pointer Reverse p = q; // startは逆ですq = t; // no3 start} //上記のループの場合、head.nextは空で、qがnullでループを実行しない場合、pは元のほとんどのデータ項目です。反転後、Pはヘッドヘッド= Pに割り当てられます。 displaylist(); } class link <t> {// link point t data; //データドメインリンク<t> next; //連続ポインター、ノードチェーンドメインリンク(Tデータ){this.data = data; } void displaylink(){system.out.println( "データは" + data.toString()); }} public static void main(string [] args){singlelinkedlist2 <integer> list = new singlelinkedlist2 <integer>(); list.insertlast(33); list.insertlast(78); list.insertlast(24); list.insertlast(22); list.insertlast(56); list.displaylist(); list.deletelast(); list.displaylist(); system.out.println( "find:" + list.find(56)); system.out.println( "find:" + list.find(33)); system.out.println( "delete find:" + list.delete(99)); system.out.println( "delete find:" + list.delete(78)); list.displaylist(); system.out.println( "---- reverse -----"); list.displaylistreverse(); }}印刷
リスト(head-> last):データは33です。データは78です。データは24です。データは22です。検索:linked_list.singlelinkedlist2$link@17dfafd1リスト(head-> last):データは33です。データは22です。
リンクされたリストでスタックとキューを実装するために、両端のリンクリストをシミュレートする
両端のリンクリスト:
両端のリンクリストは、従来のリンクリストに非常に似ています。新しい属性のみが追加されています。つまり、最後のリンクへの参照は背面です。
このようにして、チェーンの最後に挿入することは非常に簡単になります。後部の次のノードを新しいノードに変更することなく、最後のノードを検索することなく変更するだけで、InsertFirstとInsertLastがあります
チェーンヘッダーを削除するときは、基準点を変更するだけです。チェーンテールを削除するときは、最後から2番目のノードの次のノードを空にする必要があります。
参照がポイントしないため、操作を読むためにループが必要です
/ ***両端のリンクリスト* @Author Stone*/ public class twoendpointlist <t> {private link <t> head; //最初のノードプライベートリンク<T>リア; // tail pointer public twoendpointlist(){} public t peekhead(){if(head!= null){return head.data; } nullを返します。 } public boolean isempty(){return head == null; } public void insertFirst(t data){//チェーンリンクのヘッドに挿入<t> newlink = new link <t>(data); newlink.next = head; //新しいノードの次のポイントは、前のノードhead = newLinkを指します。 } public void insertlast(t data){// insert link <t> newlink = new link <t>(data); if(head == null){rece = null; } if(rece!= null){recor.next = newLink; } else {head = newLink; head.next = Lear; } rece = newLink; //次に挿入するときは、後部から挿入} public t deletehead(){//チェーンヘッダーを削除if(isempty())return null; link <t> temp = head; head = head.next; //最初のノードを次のノードに変更するif(head == null){<span style = "white-space:pre"> </span> rece = head; } temp.dataを返します。 } public t find(t t){if(isempty()){return null; } link <t> find = head; while(find!= null){if(!find.data.equals(t)){find = find.next; } else {break; }} if(find == null){return null; } return find.data; } public t delete(t t){if(isempty()){return null; } else {if(head.data.equals(t)){link <t> temp = head; head = head.next; //最初のノードを次のノードに変更しますtemp.dataを返します。 }} link <t> p = head; link <t> q = head; while(!p.data.equals(t)){if(p.next == null){//チェーンの最後にnullが見つかっていないことを示します。 } else {q = p; p = p.next; }} q.next = p.next; p.dataを返します。 } public void displaylist(){// Travel System.out.println( "list(head-> last):"); link <t> current = head; while(current!= null){current.displaylink(); current = current.next; }} public void displaylistreverse(){//逆トラバーサルif(isempty()){return; } link <t> p = head、q = head.next、t; while(q!= null){//ポインターが逆になり、トラバースされたデータ順序は後方t = q.nextです。 // no3 if(p == head){//元のヘッドである場合、ヘッドの.nextは空のp.next = null; } q.next = p; // no3-> no1 pointer Reverse p = q; // startは逆ですq = t; // no3 start} //上記のループの場合、head.nextは空で、qがnullでループを実行しない場合、pは元のほとんどのデータ項目です。反転後、Pはヘッドヘッド= Pに割り当てられます。 displaylist(); } class link <t> {// link node t data; //データドメインリンク<t> next; //連続ポインター、ノードチェーンドメインリンク(Tデータ){this.data = data; } void displaylink(){system.out.println( "データは" + data.toString()); }} public static void main(string [] args){twoendpointlist <integer> list = new TwoEndpointList <Integer>(); list.insertlast(1); list.insertfirst(2); list.insertlast(3); list.insertfirst(4); list.insertlast(5); list.displaylist(); list.deletehead(); list.displaylist(); system.out.println( "find:" + list.find(6)); system.out.println( "find:" + list.find(3)); system.out.println( "delete find:" + list.delete(6)); system.out.println( "delete find:" + list.delete(5)); list.displaylist(); system.out.println( "--- reverse ----"); list.displaylistreverse(); }}印刷
リスト(head-> last):データは4データです。データは2です。データは3です。データは5です。データは5リストです(head-> last):データは2です。データは3です。データは5です5は5です
リンクリストを使用してスタックを実装し、挿入する前に単一のリンクリストを使用します。
このクラスは、二重端のリンクリストを使用して実装しています。
public class linkstack <t> {private twoendpointlist <t> datas; public linkstack(){datas = new TwoEndpointList <t>(); } //スタックパブリックボイドプッシュ(t data){datas.insertfirst(data); } //スタックpublic t pop(){return datas.deletehead(); } //スタックの上部を確認しますpublic teek(){return datas.peekhead(); } //スタックが空であるかどうかのpublic boolean isempty(){return datas.isempty(); } public static void main(string [] args){linkstack <integer> stack = new linkstack <integer>(); for(int i = 0; i <5; i ++){stack.push(i); } for(int i = 0; i <5; i ++){integer peek = stack.peek(); System.out.println( "Peek:" + Peek); } for(int i = 0; i <6; i ++){integer pop = stack.pop(); System.out.println( "pop:" + pop); } system.out.println( "----"); for(int i = 5; i> 0; i--){stack.push(i); } for(int i = 5; i> 0; i--){integer peek = stack.peek(); System.out.println( "Peek:" + Peek); } for(int i = 5; i> 0; i--){integer pop = stack.pop(); System.out.println( "pop:" + pop); }}}印刷
ピーク:4ピーク:4ピーク:4ピーク:4ピーク:4ピーク:4ポップ:4ポップ:4ポップ:2ポップ:1ポップ:0ポップ:0 null ---ピーク:1ピーク:1ピーク:1ピーク:1ポップ:1ポップ:2ポップ:3ポップ:4ポップ:5
リンクされたリストの実装キューは、両端のリンクリストを使用して実装されます。
public class linkqueue <t> {private twoendpointlist <t> list; public linkqueue(){list = new TwoEndpointList <t>(); } //キューパブリックボイドインサート(tデータ)のテールを挿入{list.insertlast(data); } //チームの長を削除public public t remove(){return list.deletehead(); } //チームの責任者を表示しますpeek(){return list.peekhead(); } public boolean isempty(){return list.isempty(); } public static void main(string [] args){linkqueue <integer> queue = new linkqueue <integer>(); for(int i = 1; i <5; i ++){queue.insert(i); } for(int i = 1; i <5; i ++){integer peek = queue.peek(); System.out.println( "Peek:" + Peek); } for(int i = 1; i <5; i ++){integer remove = queue.remove(); system.out.println( "remove:" + remove); } system.out.println( "----"); for(int i = 5; i> 0; i-){queue.insert(i); } for(int i = 5; i> 0; i--){integer peek = queue.peek(); System.out.println( "peek2:" + peek); } for(int i = 5; i> 0; i-){integer remove = queue.remove(); system.out.println( "remove:" + remove); }}}印刷
ピーク:1ピーク:1ピーク:1ピーク:1ピーク:1削除:1削除:1削除:3削除:3削除:4 ---ピーク2:5 PEEK2:5 PEEK2:5 PEEK2:5 PEEK2:5削除:4削除:4削除:2削除:2削除:1