シミュレートされたシングルリンクテーブル
線形テーブル：
線形テーブル（シーケンシャルテーブルとも呼ばれます）は、最も基本的で、最も単純で、最も一般的に使用されるデータ構造です。
線形テーブルのデータ要素間の関係は、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