1。序文
最近、データ構造とアルゴリズムを確認するとき、いくつかのアルゴリズムの問題はスタックのアイデアを使用し、スタックに関してはリンクリストについて話す必要があります。配列とリンクリストは線形ストレージ構造の基礎であり、スタックとキューは線形ストレージ構造のアプリケーションです〜
この記事では、主に単一リンクリストの基本的な知識ポイントを説明し、簡単な紹介をします。間違いがある場合は、修正してください。
2。レビューと知識
リンクリストといえば、まず配列について言及しましょう。それらを配列と比較すると、リンクリストのストレージ構造を非常によく理解できます。
2.1配列を確認します
CとJavaの両方でアレイを学びました。
配列の利点：
配列の短所：
2.2リンクリストの説明
配列を読んだ後、リンクリストに戻ります。
Nノードは個別に割り当てられ、ポインターを介して互いに接続されます。各ノードには1つの前身ノードのみがあり、各ノードには次のノードが1つしかなく、最初のノードには前身ノードがなく、テールノードには後続のノードがありません。
リンクリストの利点：
リンクされたリストの短所：
上記の写真からリンクリストに関連する用語を説明します。
リンクリストを決定するには、ヘッドポインターのみが必要であり、リンクされたリスト全体をヘッドポインターから推定できます〜
リンクされたリストにはいくつかのカテゴリがあります。
1.一元配置リンクテーブル
2。双方向リンクテーブル
3.リサイクルリンクリスト
リンクされたリストを操作するときに覚えておく必要があるのは、次のとおりです。
ノードのポインターフィールドは、ノードを指します！
3。Java実装リンクリスト
アルゴリズム：
まず、クラスをノードとして定義します
運用の便利さのために、私はそれを一般に定義しました。
public class node {//データドメインpublic int data; //次のノードパブリックノードを指すポインタードメイン。 public node（）{} public node（int data）{this.data = data; } public node（int data、node next）{this.data = data; this.next = next; }} 3.1リンクリストを作成します（ノードを追加）
リンクリストにデータを挿入します。
/***リンクリストにデータを追加** @param値データを追加する*/public static void adddata（int value）{//ノードを初期化するNewNode = new Node（value）; //一時ノードノードTemp = head; //テールノードを見つけますwhile（temp.next！= null）{temp = temp.next; } // head node.nextがnullが含まれている場合〜temp.next = newnode; } 3.2リンクリストのトラバース
上記の追加方法を作成しましたが、それが正しいかどうかを確認するためにそれを調べます~~~
最初のノードから始めて、後続のノードにデータがなくなるまで後ろを検索し続けます。
/ ***リンクリストのトラバース** @paramヘッドヘッドヘッドノード*/ public static void traverse（node head）{//一時ノード、最初のノードノードから開始temp = head.next; while（temp！= null）{system.out.println（ "公式アカウントJava3y：" + temp.data）; //次のtemp = temp.nextを続行します。 }}結果：
3.3ノードを挿入します
/*** node** @paramヘッドヘッドポインター* @paramインデックス位置挿入* @param値値を挿入する*/public static void insertnode（node head、int index、int value）{//まず、指定された位置が合法かどうかを判断する必要があります。 違法。"）;戻る; } //一時的なノード、最初から開始しますノードノードtemp = head; // traversal int currentPos = 0の現在の位置をクリックします。 //挿入されるノードを初期化しますnode insertnode = newノード（値）; while（temp.next！= null）{//前のノードの位置は（（index -1）== currentpos）{//前のノードを表します//前のノードから元のポインターを挿入したノードから挿入したノードに指して、挿入next.next = temp.next; //前のノードのポインターフィールドをノードに向けて挿入するtemp.next = insertNode;戻る; } currentpos ++; temp = temp.next; }} 3.4リンクリストの長さを取得します
リンクリストの長さを取得するのは非常に簡単です。それを通過することで実行でき、各ノードで+1を取得することができます〜
/ ***リンクリストの長さを取得* @paramヘッドヘッドポインター*/ public static int linklistlength（node head）{int length = 0; //一時ノード、最初のノードノードから開始temp = head.next; //（temp！= null）{length ++; temp = temp.next; } return length; } 3.5ノードを削除します
特定の場所でノードを削除することは、実際には挿入ノードと非常に似ており、前のノードを見つける必要もあります。前のノードのポインターフィールドを変更すると、削除できます〜
/** *場所によるとノードを削除 * * @paramヘッドヘッドポインター * @param deletedの場所 */public static void deleteNode（node head、int index）{//まず、指定された場所が合法かどうかを判断する必要があります。戻る; } //一時的なノード、最初から開始しますノードノードtemp = head; //レコードトラバーサルの現在の位置はint currentpos = 0です。 while（temp.next！= null）{//前のノードの位置は（（index -1）== currentpos）{//前のノードを表します// temp.nextは削除するノードを表します//ノードをストレージしたいノードを削除するノードを削除するdeletenode = temp.next; //ノードを削除する次のノードが前のノードに引き渡され、temp.next = deleteNode.next; // javaはそれをリサイクルします、そして、それをnullに設定することはあまり意味がありません（私はそれが正しくない場合、それを指摘してください〜）deleteNode = null;戻る; } currentpos ++; temp = temp.next; }} 3.6リンクリストを並べ替えます
私はすでに8つの並べ替えアルゴリズム[8つのソートアルゴリズムの要約]について話しています。今回は簡単なバブルソートを選択します（実際、簡単な種類を書きたいのですが、試してみるのは少し難しいと感じています...）
/ ** *リンクリストをソート * * @param head * */ public static void sortlinklist（node head）{node currentNode;ノードNextNode; for（currentNode = head.next; currentNode.next！= null; currentNode = currentNode.next）{for（nextnode = head.next; nextnode.next！= null; nextnode = nextnode.next）{if（nextnode.data> nextnode.next.data）{int temp = nextnode.data; nextnode.data = nextnode.next.data; nextnode.next.data = temp; }}}} 3.7リンクリストでk-lastノードを見つけます
このアルゴリズムは非常に興味深いです。2つのポインターP1とP2を設定して、P2 KノードをP1よりも速くすると同時に後方に移動します。 P2が空の場合、P1はk番目の最後のノードです
/ ***リンクリストの最後のノードまでk-thを見つけます（2つのポインターP1とP2を設定し、P2 kをP1よりも速くし、同時に後方に移動します。P2が空になると、P1は最後のノードまでk-theです** @param head* @param k-thは最後のノードk-th/ public static node head（k） linklistled（head）Node P1 = Head; p1.next;
3.8リンクリストの複製データを削除します
バブルソートに似ています。等しい限り、削除できる〜
/ ** *リンクリストの複製データを削除します（バブルと同様に、削除と同等です） //現在のノードの次のノード（最初のノード）ノードNextNode = temp.next; while（temp.next！= null）{while（nextnode.next！= null）{if（nextnode.next.data == nextnode.data）{//次のノード（現在のノードが次のノードを指します）nextnode.next = nextnode.next.next.next.next.next.next.next.next.next.next.next.next.next.next; } else {//次のnextNode = nextNode.next; }} //比較の次のラウンドtemp = temp.next; }} 3.9リンクリストの中間ノードをクエリします
このアルゴリズムも非常に興味深いです。毎回1ステップを踏むポインター、毎回2ステップを踏むポインター、そして1つのステップ、つまり中間ノードです
/ ***単一のリンクリストの中間ノードをクエリします*/ public staticノードSearchMid（ノードヘッド）{node p1 = head;ノードP2 = head; // 1つのステップを踏み、1つのステップを獲得します。到達する中央ノード（p2！= null && p2.next！= null && p2.next.next！= null）{p1 = p1.next; p2 = p2.next.next; } p1を返します。 }3.10尾から頭までの単一リンクテーブルを再帰的に出力します
/ ***再帰的にテールからヘッドへのシングルリンクリストを出力** @paramヘッドノード*/ public static void printlistReversely（node head）{if（head！= null）{printListreversely（head.next）; System.out.println（head.data）; }} 3.11リバースリンクリスト
/ ***リンクリストの反転を実装** @paramノードリンクリストのヘッドノード*/ public staticノードreverselinkList（ノードノード）{node prev; if（node == null || node.next == null）{prev = node; } else {node tmp = reverselinklist（node.next）; node.next.next = node; node.next = null; prev = tmp; } return prev; }逆リンクリストへの参照：//www.vevb.com/article/136185.htm
4。最後に
リンクされたリスト自体を理解することは難しくありませんが、関連操作を行うときに頭痛を引き起こす可能性があります。次は次のhead.nextです。
リンクリストを操作するときにヘッドポインターを知っているだけで、何でもできます。
1.リンクリストにデータを追加します
2.リンクリストをトラバースします
3.特定の場所のリンクリストにノードを挿入します
4.リンクリストの長さを取得します
5.指定された場所でノードを削除します
6.リンクリストを並べ替えます
7.リンクリストでk-lastノードを見つけます
8。リンクリストの複製データを削除します
9。リンクリストの中間ノードをクエリします
10。尾から頭への単一リンクテーブルを再帰的に出力します
11。リバースリンクリスト
PS：全員の実装が異なるため、いくつかの小さな詳細は必然的に変更され、それを書くための固定方法はありませんので、対応する機能を実現できます〜
要約します
上記は、この記事のコンテンツ全体です。この記事の内容には、すべての人の研究や仕事に特定の参照値があることを願っています。ご質問がある場合は、メッセージを残してコミュニケーションをとることができます。 wulin.comへのご支援ありがとうございます。
参考文献：