TechCodeview

• リンクされたリストは、と呼ばれるオブジェクトのコレクションとして定義できます。 ノード メモリにランダムに保存されます。
• ノードには 2 つのフィールド、つまり、その特定のアドレスに格納されているデータと、メモリ内の次のノードのアドレスを含むポインタが含まれています。
• リストの最後のノードには、null へのポインタが含まれます。

リンクリストの使用法

• リストはメモリ内に連続して存在する必要はありません。ノードはメモリ内の任意の場所に存在し、リンクしてリストを作成できます。これにより、スペースの最適利用が実現します。
• リストのサイズはメモリ サイズに制限されており、事前に宣言する必要はありません。
• 空のノードはリンク リストに存在できません。
• プリミティブ型またはオブジェクトの値を単一リンクリストに保存できます。

なぜ配列ではなくリンクされたリストを使用するのでしょうか?

これまでは、配列データ構造を使用して、メモリに個別に保存される要素のグループを編成していました。ただし、Array には、プログラム全体で使用されるデータ構造を決定するために知っておく必要があるいくつかの利点と欠点があります。

配列には次の制限があります。

1. 配列のサイズは、プログラムで使用する前に事前に知っておく必要があります。
2. 配列のサイズを増やすのは時間のかかるプロセスです。実行時に配列のサイズを拡張することはほとんど不可能です。
3. 配列内のすべての要素はメモリに連続して格納される必要があります。配列に要素を挿入するには、そのすべての先行要素をシフトする必要があります。

リンク リストは、配列のすべての制限を克服できるデータ構造です。リンク リストを使用すると便利な理由は次のとおりです。

Javaは文字列にキャストします

1. メモリを動的に割り当てます。リンク リストのすべてのノードはメモリに非連続的に格納され、ポインタを使用してリンクされます。
2. 宣言時にサイズを定義する必要がないため、サイズ設定は問題になりません。リストはプログラムの要求に応じて増加し、利用可能なメモリ領域に制限されます。

単一リンクリストまたは一方向チェーン

単一リンクリストは、順序付けられた要素セットのコレクションとして定義できます。要素の数はプログラムの必要性に応じて変わります。単一リンクリストのノードは、データ部分とリンク部分の 2 つの部分で構成されます。ノードのデータ部分には、ノードによって表現される実際の情報が格納され、ノードのリンク部分には、その直接の後続ノードのアドレスが格納されます。

一方向のチェーンまたは単一リンクされたリストは、一方向にのみトラバースできます。言い換えると、各ノードには次のポインターのみが含まれているため、リストを逆方向に走査することはできません。

1nf 2nf 3nf

図に示すように、学生が 3 つの科目で取得した点数がリンク リストに格納されている例を考えてみましょう。

上の図では、矢印はリンクを表しています。すべてのノードのデータ部分には、生徒がさまざまな科目で取得した点数が含まれています。リスト内の最後のノードは、最後のノードのアドレス部分に存在するヌル ポインタによって識別されます。リストのデータ部分には、必要なだけ要素を含めることができます。

JavaFX チュートリアル

複雑

単一リンクリストの操作

単一リンクリストに対して実行できるさまざまな操作があります。このようなすべての操作のリストを以下に示します。

ノードの作成

 struct node { int data; struct node *next; }; struct node *head, *ptr; ptr = (struct node *)malloc(sizeof(struct node *)); 

挿入

単一リンクリストへの挿入は、さまざまな位置で実行できます。挿入される新しいノードの位置に基づいて、挿入は次のカテゴリに分類されます。

削除とトラバース

単一リンクリストからのノードの削除は、さまざまな位置で実行できます。削除するノードの位置に基づいて、操作は次のカテゴリに分類されます。

C のリンク リスト: メニュー駆動プログラム

 #include #include struct node { int data; struct node *next; }; struct node *head; void beginsert (); void lastinsert (); void randominsert(); void begin_delete(); void last_delete(); void random_delete(); void display(); void search(); void main () { int choice =0; while(choice != 9) { printf('

*********Main Menu*********
'); printf('
Choose one option from the following list ...
'); printf('
===============================================
'); printf('
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
 5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
'); printf('
Enter your choice?
'); scanf('
%d',&choice); switch(choice) { case 1: beginsert(); break; case 2: lastinsert(); break; case 3: randominsert(); break; case 4: begin_delete(); break; case 5: last_delete(); break; case 6: random_delete(); break; case 7: search(); break; case 8: display(); break; case 9: exit(0); break; default: printf('Please enter valid choice..'); } } } void beginsert() { struct node *ptr; int item; ptr = (struct node *) malloc(sizeof(struct node *)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter value
'); scanf('%d',&item); ptr->data = item; ptr->next = head; head = ptr; printf('
Node inserted'); } } void lastinsert() { struct node *ptr,*temp; int item; ptr = (struct node*)malloc(sizeof(struct node)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter value?
'); scanf('%d',&item); ptr->data = item; if(head == NULL) { ptr -> next = NULL; head = ptr; printf('
Node inserted'); } else { temp = head; while (temp -> next != NULL) { temp = temp -> next; } temp->next = ptr; ptr->next = NULL; printf('
Node inserted'); } } } void randominsert() { int i,loc,item; struct node *ptr, *temp; ptr = (struct node *) malloc (sizeof(struct node)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter element value'); scanf('%d',&item); ptr->data = item; printf('
Enter the location after which you want to insert '); scanf('
%d',&loc); temp=head; for(i=0;inext; if(temp == NULL) { printf('
can't insert
'); return; } } ptr ->next = temp ->next; temp ->next = ptr; printf('
Node inserted'); } } void begin_delete() { struct node *ptr; if(head == NULL) { printf('
List is empty
'); } else { ptr = head; head = ptr->next; free(ptr); printf('
Node deleted from the begining ...
'); } } void last_delete() { struct node *ptr,*ptr1; if(head == NULL) { printf('
list is empty'); } else if(head -> next == NULL) { head = NULL; free(head); printf('
Only node of the list deleted ...
'); } else { ptr = head; while(ptr->next != NULL) { ptr1 = ptr; ptr = ptr ->next; } ptr1->next = NULL; free(ptr); printf('
Deleted Node from the last ...
'); } } void random_delete() { struct node *ptr,*ptr1; int loc,i; printf('
 Enter the location of the node after which you want to perform deletion 
'); scanf('%d',&loc); ptr=head; for(i=0;inext; if(ptr == NULL) { printf('
Can't delete'); return; } } ptr1 ->next = ptr ->next; free(ptr); printf('
Deleted node %d ',loc+1); } void search() { struct node *ptr; int item,i=0,flag; ptr = head; if(ptr == NULL) { printf('
Empty List
'); } else { printf('
Enter item which you want to search?
'); scanf('%d',&item); while (ptr!=NULL) { if(ptr->data == item) { printf('item found at location %d ',i+1); flag=0; } else { flag=1; } i++; ptr = ptr -> next; } if(flag==1) { printf('Item not found
'); } } } void display() { struct node *ptr; ptr = head; if(ptr == NULL) { printf('Nothing to print'); } else { printf('
printing values . . . . .
'); while (ptr!=NULL) { printf('
%d',ptr->data); ptr = ptr -> next; } } } 

出力：

 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 1 Enter value 1 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 2 Enter value? 2 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 3 Enter element value1 Enter the location after which you want to insert 1 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 8 printing values . . . . . 1 2 1 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 2 Enter value? 123 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 1 Enter value 1234 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 4 Node deleted from the begining ... *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 5 Deleted Node from the last ... *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 6 Enter the location of the node after which you want to perform deletion 1 Deleted node 2 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 8 printing values . . . . . 1 1 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 7 Enter item which you want to search? 1 item found at location 1 item found at location 2 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 9