あ リンクされたリスト データ要素を保存するために使用する一種の線形動的データ構造です。配列は、データ項目が連続したメモリ ブロックに格納される線形データ構造の一種でもあります。
配列とは異なり、リンク リストではデータ要素を連続したメモリ領域またはブロックに格納する必要がありません。
テキストサイズラテックス
あ リンクされたリスト は 2 つの部分に分かれた「ノード」と呼ばれる要素で構成されています。最初のコンポーネントは実際のデータを格納する部分であり、2 番目のコンポーネントは次のノードへのポインターを格納する部分です。このタイプの構造は「」として知られています。 単一リンクリスト 。」
C++ のリンク リスト
このチュートリアルでは、単一リンク リストについて詳しく説明します。
単一リンクリストの構造を次の図に示します。
- 上の部分で見たように、リンクされたリストの最初のノードは「ヘッド」と呼ばれ、最後のノードは「テール」と呼ばれます。これは、最後のノードにメモリ アドレスが指定されていないため、リンク リストの最後のノードには null の次ポインタが設定されます。
- 各ノードには次のノードへのポインタが含まれるため、リンクされたリスト内のデータ要素を連続した場所に保持する必要はありません。ノードはメモリ全体に分散している場合があります。各ノードには後続のノードのアドレスがあるため、いつでも必要なときにノードにアクセスできます。
- 接続されたリストにデータ項目をすばやく追加したり、リストからデータ項目を削除したりできます。その結果、リンクされたリストは動的に増加または縮小する可能性があります。リンク リストには、含めることができるデータ項目の最大量はありません。その結果、利用可能な RAM がある限り、リンク リストに好きなだけデータ項目を追加できます。
- リンク リストに必要な項目の数を事前に指定する必要がないため、リンク リストは挿入と削除が簡単であるだけでなく、メモリ領域も節約できます。リンク リストで使用される唯一のスペースは、次のノードへのポインタを格納するためのものであり、コストが多少かかります。
続いて、リンクされたリストで実行できるさまざまな操作について説明します。
1) 挿入
リンクされたリストは、リストに追加するアクションによって拡張されます。リンク リストの構造を考えると、簡単そうに見えますが、データ項目が追加されるたびに、追加した新しい項目の前のノードと次のノードの次のポインタを変更する必要があることがわかります。
文字列を整数に変換する
新しいデータ項目がどこに挿入されるかは、2 番目に考慮すべき点です。
データ項目をリンク リストに追加できる場所は 3 つあります。
ａ．リンクリストから始める
以下は、2->4->6->8->10 という数字の接続リストです。新しいノード 1 をリストの最初のノードとして追加すると、以下の図に示すように、ノード 2 を指すヘッドはノード 1 を指すようになり、ノード 1 の次のポインタはノード 2 のメモリ アドレスを持つようになります。 。
その結果、新しいリンク リストは 1->2->4->6->8->10 になります。
b.指定されたノードの後
この場合、ノードが与えられているので、その背後に新しいノードを追加する必要があります。ノード f がノード c の後のリンク リスト a->b->c->d->e に追加される場合、リンク リストは次のようになります。
文字列を配列javaに入れる
したがって、指定されたノードが上の図に存在するかどうかを確認します。存在する場合は、新しいノード f が作成されます。その後、ノード c の次のポインタを新しいノード f に向けます。ノード f の次のポインタはノード d を指します。
c.リンクされたリストの最後の項目
3 番目のケースでは、新しいノードがリンクされたリストの末尾に追加されます。以下のリンク リスト: a->b->c->d->e を考慮してください。最後にノード f が追加されています。ノードを追加すると、このようにリンクされたリストが表示されます。
その結果、新しいノード f を構築します。 null につながる末尾ポインタは f を指し、ノード f の次のポインタは null を指します。以下のプログラミング言語では、3 種類の挿入関数すべてを生成しました。
リンク リストは、C++ の構造体またはクラスとして宣言できます。構造体として宣言されたリンク リストは、古典的な C スタイルのステートメントです。リンク リストは、主に標準テンプレート ライブラリを使用する場合に、最新の C++ のクラスとして使用されます。
構造体は、リンク リストを宣言および生成するために次のアプリケーションで使用されました。そのメンバーはデータと次の要素へのポインタになります。
C++ プログラム:
#include using namespace std; struct Node { int data; struct Node *next; }; void push ( struct Node** head, int nodeData ) { struct Node* newNode1 = new Node; newNode1 -> data = nodeData; newNode1 -> next = (*head); (*head) = newNode1; } void insertAfter ( struct Node* prevNode, int nodeData ) { if ( prevNode == NULL ) { cout <data = nodedata; newnode1 -> next = prevNode -> next; prevNode -> next = newNode1; } void append ( struct Node** head, int nodeData ) { struct Node* newNode1 = new Node; struct Node *last = *head; newNode1 -> data = nodeData; newNode1 -> next = NULL; if ( *head == NULL ) { *head = newNode1; return; } while ( last -> next != NULL ) last = last -> next; last -> next = newNode1; return; } void displayList ( struct Node *node ) { while ( node != NULL ) { cout <data <'; node="node" -> next; } if ( node== NULL) cout<next, 55 ); cout << 'final linked list: ' endl; displaylist (head); return 0; } < pre> <p> <strong>Output:</strong> </p> <pre> Final linked list: 35-->25-->55-->15-->45-->null </pre> <h3>2) Deletion</h3> <p>Similar to insertion, deleting a node from a linked list requires many points from which the node might be eliminated. We can remove the linked list's first, last, or kth node at random. We must correctly update the next pointer and all other linked list pointers in order to maintain the linked list after deletion.</p> <p>In the following C++ implementation, we have two deletion methods: deleting the list's initial node and deleting the list's last node. We begin by adding nodes to the head of the list. The list's contents are then shown following each addition and deletion.</p> <p> <strong>C++ Program:</strong> </p> <pre> #include using namespace std; struct Node { int data; struct Node* next; }; Node* deletingFirstNode ( struct Node* head ) { if ( head == NULL ) return NULL; Node* tempNode = head; head = head -> next; delete tempNode; return head; } Node* removingLastNode ( struct Node* head ) { if ( head == NULL ) return NULL; if ( head -> next == NULL ) { delete head; return NULL; } Node* secondLast = head; while ( secondLast -> next -> next != NULL ) secondLast = secondLast->next; delete ( secondLast -> next ); secondLast -> next = NULL; return head; } void push ( struct Node** head, int newData ) { struct Node* newNode1 = new Node; newNode1 -> data = newData; newNode1 -> next = ( *head ); ( *head ) = newNode1; } int main() { Node* head = NULL; push ( &head, 25 ); push ( &head, 45 ); push ( &head, 65); push ( &head, 85 ); push ( &head, 95 ); Node* temp; cout << 'Linked list created ' < next ) cout <data <'; if ( temp="=" null ) cout << 'null' endl; head="deletingFirstNode" (head); 'linked list after deleting node' < next <data cout<<'null'<<endl; last data 'null'; return 0; } pre> <p> <strong>Output:</strong> </p> <pre> Linked list created 95-->85-->65-->45-->25-->NULL Linked list after deleting head node 85-->65-->45-->25-->NULL Linked list after deleting last node 85-->65-->45-->NULL </pre> <h3>Node Count</h3> <p>While traversing the linked list, the process of counting the number of nodes can be performed. In the preceding approach, we saw that if we needed to insert/delete a node or display the contents of the linked list, we had to traverse the linked list from the beginning.</p> <p>Setting a counter and incrementing as well as we traverse each node will provide us the number of nodes in the linked list.</p> <h3>Differences between Array and Linked list:</h3> <table class="table"> <tr> <th>Array</th> <th>Linked list</th> </tr> <tr> <td>Arrays have a defined size.</td> <td>The size of the linked list is variable.</td> </tr> <tr> <td>Inserting a new element is difficult.</td> <td>Insertion and deletion are simpler.</td> </tr> <tr> <td>Access is permitted at random.</td> <td>No random access is possible.</td> </tr> <tr> <td>Elements are in relatively close or contiguous.</td> <td>The elements are not contiguous.</td> </tr> <tr> <td>No additional room is required for the following pointer.</td> <td>The following pointer requires additional memory.</td> </tr> </table> <h3>Functionality</h3> <p>Since linked lists and arrays are both linear data structures that hold objects, they can be utilised in similar ways for the majority of applications.</p> <p>The following are some examples of linked list applications:</p> <ul> <li>Stacks and queues can be implemented using linked lists.</li> <li>When we need to express graphs as adjacency lists, we can use a linked list to implement them.</li> <li>We can also use a linked list to contain a mathematical polynomial.</li> <li>In the case of hashing, linked lists are employed to implement the buckets.</li> <li>When a programme requires dynamic memory allocation, we can utilize a linked list because linked lists are more efficient in this instance.</li> </ul> <h2>Conclusion</h2> <p>Linked lists are data structures used to hold data elements in a linear but non-contiguous form. A linked list is made up of nodes with two components each. The first component is made up of data, while the second half has a pointer that stores the memory address of the following member of the list.</p> <p>As a sign that the linked list has ended, the last item in the list has its next pointer set to NULL. The Head is the first item on the list. The linked list allows for a variety of actions such as insertion, deletion, traversal, and so on. Linked lists are favoured over arrays for dynamic memory allocation.</p> <p>Linked lists are hard to print or traverse because we can't access the elements randomly like arrays. When compared to arrays, insertion-deletion procedures are less expensive.</p> <p>In this tutorial, we learned everything there is to know about linear linked lists. Linked lists can also be doubly linked or circular. In our forthcoming tutorials, we will go through these lists in detail.</p> <hr></data></pre></next,></data></data> 2) 削除
挿入と同様に、リンク リストからノードを削除するには、ノードを削除するための多くのポイントが必要です。リンクされたリストの最初、最後、または k 番目のノードをランダムに削除できます。削除後にリンク リストを維持するには、次のポインタと他のすべてのリンク リスト ポインタを正しく更新する必要があります。
次の C++ 実装では、リストの最初のノードの削除とリストの最後のノードの削除という 2 つの削除方法があります。まず、リストの先頭にノードを追加します。追加および削除のたびにリストの内容が表示されます。
C++ プログラム:
文字列をJavaと比較する
#include using namespace std; struct Node { int data; struct Node* next; }; Node* deletingFirstNode ( struct Node* head ) { if ( head == NULL ) return NULL; Node* tempNode = head; head = head -> next; delete tempNode; return head; } Node* removingLastNode ( struct Node* head ) { if ( head == NULL ) return NULL; if ( head -> next == NULL ) { delete head; return NULL; } Node* secondLast = head; while ( secondLast -> next -> next != NULL ) secondLast = secondLast->next; delete ( secondLast -> next ); secondLast -> next = NULL; return head; } void push ( struct Node** head, int newData ) { struct Node* newNode1 = new Node; newNode1 -> data = newData; newNode1 -> next = ( *head ); ( *head ) = newNode1; } int main() { Node* head = NULL; push ( &head, 25 ); push ( &head, 45 ); push ( &head, 65); push ( &head, 85 ); push ( &head, 95 ); Node* temp; cout << 'Linked list created ' < next ) cout <data <\'; if ( temp="=" null ) cout << \'null\' endl; head="deletingFirstNode" (head); \'linked list after deleting node\' < next <data cout<<\'null\'<<endl; last data \'null\'; return 0; } pre> <p> <strong>Output:</strong> </p> <pre> Linked list created 95-->85-->65-->45-->25-->NULL Linked list after deleting head node 85-->65-->45-->25-->NULL Linked list after deleting last node 85-->65-->45-->NULL </pre> <h3>Node Count</h3> <p>While traversing the linked list, the process of counting the number of nodes can be performed. In the preceding approach, we saw that if we needed to insert/delete a node or display the contents of the linked list, we had to traverse the linked list from the beginning.</p> <p>Setting a counter and incrementing as well as we traverse each node will provide us the number of nodes in the linked list.</p> <h3>Differences between Array and Linked list:</h3> <table class="table"> <tr> <th>Array</th> <th>Linked list</th> </tr> <tr> <td>Arrays have a defined size.</td> <td>The size of the linked list is variable.</td> </tr> <tr> <td>Inserting a new element is difficult.</td> <td>Insertion and deletion are simpler.</td> </tr> <tr> <td>Access is permitted at random.</td> <td>No random access is possible.</td> </tr> <tr> <td>Elements are in relatively close or contiguous.</td> <td>The elements are not contiguous.</td> </tr> <tr> <td>No additional room is required for the following pointer.</td> <td>The following pointer requires additional memory.</td> </tr> </table> <h3>Functionality</h3> <p>Since linked lists and arrays are both linear data structures that hold objects, they can be utilised in similar ways for the majority of applications.</p> <p>The following are some examples of linked list applications:</p> <ul> <li>Stacks and queues can be implemented using linked lists.</li> <li>When we need to express graphs as adjacency lists, we can use a linked list to implement them.</li> <li>We can also use a linked list to contain a mathematical polynomial.</li> <li>In the case of hashing, linked lists are employed to implement the buckets.</li> <li>When a programme requires dynamic memory allocation, we can utilize a linked list because linked lists are more efficient in this instance.</li> </ul> <h2>Conclusion</h2> <p>Linked lists are data structures used to hold data elements in a linear but non-contiguous form. A linked list is made up of nodes with two components each. The first component is made up of data, while the second half has a pointer that stores the memory address of the following member of the list.</p> <p>As a sign that the linked list has ended, the last item in the list has its next pointer set to NULL. The Head is the first item on the list. The linked list allows for a variety of actions such as insertion, deletion, traversal, and so on. Linked lists are favoured over arrays for dynamic memory allocation.</p> <p>Linked lists are hard to print or traverse because we can't access the elements randomly like arrays. When compared to arrays, insertion-deletion procedures are less expensive.</p> <p>In this tutorial, we learned everything there is to know about linear linked lists. Linked lists can also be doubly linked or circular. In our forthcoming tutorials, we will go through these lists in detail.</p> <hr></data> ノード数
リンクされたリストをトラバースしながら、ノードの数をカウントするプロセスを実行できます。前述のアプローチでは、ノードを挿入/削除したり、リンク リストの内容を表示したりする必要がある場合、リンク リストを最初からたどる必要があることがわかりました。
カウンタを設定してインクリメントし、各ノードをトラバースすると、リンク リスト内のノードの数が得られます。
配列とリンクリストの違い:
| 配列 | リンクされたリスト |
|---|---|
| 配列には定義されたサイズがあります。 | リンクされたリストのサイズは可変です。 |
| 新しい要素を挿入するのは難しいです。 | 挿入と削除がより簡単になります。 |
| アクセスはランダムに許可されます。 | ランダムアクセスは不可能です。 |
| 要素が比較的近くにある、または隣接している。 | 要素が連続していません。 |
| 次のポインターのために追加のスペースは必要ありません。 | 次のポインタには追加のメモリが必要です。 |
機能性
リンク リストと配列はどちらもオブジェクトを保持する線形データ構造であるため、ほとんどのアプリケーションで同様の方法で利用できます。
次に、リンク リスト アプリケーションの例をいくつか示します。
ハッシュセットJavaとは何ですか
- スタックとキューはリンク リストを使用して実装できます。
- グラフを隣接リストとして表現する必要がある場合、リンク リストを使用してそれらを実装できます。
- リンク リストを使用して数学的多項式を含めることもできます。
- ハッシュの場合、リンク リストを使用してバケットを実装します。
- プログラムで動的なメモリ割り当てが必要な場合は、リンク リストの方が効率的であるため、リンク リストを利用できます。
結論
リンク リストは、データ要素を線形だが連続しない形式で保持するために使用されるデータ構造です。リンク リストは、それぞれ 2 つのコンポーネントを持つノードで構成されます。最初のコンポーネントはデータで構成され、後半にはリストの次のメンバーのメモリ アドレスを格納するポインタがあります。
リンクされたリストが終了したことを示す兆候として、リスト内の最後の項目の次のポインタが NULL に設定されます。 Head はリストの最初の項目です。リンクされたリストでは、挿入、削除、走査などのさまざまなアクションが可能です。動的なメモリ割り当てでは、配列よりもリンク リストが好まれます。
リンクされたリストは、配列のように要素にランダムにアクセスできないため、印刷したり走査したりするのが困難です。配列と比較すると、挿入と削除の手順は安価です。
このチュートリアルでは、線形リンク リストについて知っておくべきことをすべて学びました。リンク リストは二重リンクまたは循環することもできます。今後のチュートリアルでは、これらのリストについて詳しく説明します。