メニュー

イラスト付きC ++のリンクリストデータ構造

linked list data structure c with illustration

問題を排除するために楽器を試してください

C ++でのリンクリストの詳細な調査。

リンクリストは、データ項目を格納するための線形動的データ構造です。基本的なC ++に関する以前のトピックで、配列についてはすでに見てきました。また、配列は、データ項目を連続した場所に格納する線形データ構造であることもわかっています。

配列とは異なり、リンクリストは連続したメモリ位置にデータ項目を格納しません。

リンクリストは、2つの部分を含む「ノード」と呼ばれるアイテムで構成されています。最初の部分には実際のデータが格納され、2番目の部分には次のノードを指すポインターがあります。この構造は通常、「単一リンクリスト」と呼ばれます。

=> ここで最高のC ++トレーニングチュートリアルをチェックしてください。

リンクリスト

学習内容：

C ++のリンクリスト

このチュートリアルでは、単一リンクリストについて詳しく見ていきます。

任意のウェブサイトからビデオをダウンロードするソフトウェア

次の図は、単一リンクリストの構造を示しています。

単一リンクリストの構造

上に示したように、リンクリストの最初のノードは「ヘッド」と呼ばれ、最後のノードは「テール」と呼ばれます。ご覧のとおり、リンクリストの最後のノードには、ポイントされたメモリアドレスがないため、次のポインタがnullになります。

各ノードには次のノードへのポインタがあるため、リンクリスト内のデータ項目を連続した場所に保存する必要はありません。ノードはメモリ内に散在する可能性があります。各ノードには次のノードのアドレスがあるため、いつでもノードにアクセスできます。

リンクリストにデータ項目を追加したり、リストから項目を簡単に削除したりできます。したがって、リンクリストを動的に拡大または縮小することができます。リンクリストに含めることができるデータ項目の数に上限はありません。メモリが利用可能である限り、リンクリストにいくつでもデータ項目を追加できます。

簡単な挿入と削除に加えて、リンクリストに必要なアイテムの数を事前に指定する必要がないため、リンクリストはメモリスペースを浪費しません。リンクリストが占める唯一のスペースは、少しオーバーヘッドを追加する次のノードへのポインタを格納するためのものです。

次に、リンクリストで実行できるさまざまな操作について説明します。

操作

他のデータ構造と同様に、リンクリストに対してもさまざまな操作を実行できます。ただし、下付き文字を使用して要素に直接アクセスできる配列とは異なり、リンクリストを使用して同じランダムアクセスを行うことはできません。

任意のノードにアクセスするには、リンクリストを最初からトラバースする必要があります。そうしないと、目的のノードにアクセスできなくなります。したがって、リンクリストからランダムにデータにアクセスすると、コストがかかることがわかります。

以下に示すように、リンクリストに対してさまざまな操作を実行できます。

＃1）挿入

リンクリストの挿入操作により、リンクリストに項目が追加されます。リンクリストの構造を考えると、単純に聞こえるかもしれませんが、データアイテムがリンクリストに追加されるたびに、挿入した新しいアイテムの前のノードと次のノードの次のポインタを変更する必要があることがわかっています。

次に考慮しなければならないのは、新しいデータ項目を追加する場所です。

リンクリストには、データ項目を追加できる位置が3つあります。

＃1）リンクリストの最初

リンクリストは、2-> 4-> 6-> 8-> 10の下に表示されます。リストの最初のノードとして新しいノード1を追加する場合、ノード2を指すヘッドは1を指し、ノード1の次のポインタはノード2のメモリアドレスを持ちます（以下を参照）。図。

最初の挿入

したがって、新しいリンクリストは1-> 2-> 4-> 6-> 8-> 10になります。

＃2）指定されたノードの後

ここでは、ノードが指定されており、指定されたノードの後に​​新しいノードを追加する必要があります。以下のリンクリストa-> b-> c-> d-> eで、ノードcの後にノードfを追加する場合、リンクリストは次のようになります。

特定のノードの後に​​挿入

したがって、上の図では、指定されたノードが存在するかどうかを確認します。存在する場合は、新しいノードfを作成します。次に、ノードcの次のポインターをポイントして、新しいノードfをポイントします。ノードfの次のポインタはノードdを指します。

＃3）リンクリストの最後

3番目のケースでは、リンクリストの最後に新しいノードを追加します。同じリンクリストa-> b-> c-> d-> eがあり、リストの最後にノードfを追加する必要があるとします。ノードを追加すると、リンクリストは次のようになります。

リンクリストの最後に挿入

したがって、新しいノードfを作成します。次に、nullを指すテールポインタはfを指し、ノードfの次のポインタはnullを指します。以下のC ++プログラムでは、3種類すべての挿入関数を実装しています。

C ++では、リンクリストを構造またはクラスとして宣言できます。リンクリストを構造体として宣言することは、従来のCスタイルの宣言です。クラスとしてのリンクリストは、主に標準のテンプレートライブラリを使用しているときに、最新のC ++で使用されます。

次のプログラムでは、構造を使用してリンクリストを宣言および作成しました。そのメンバーとして、データと次の要素へのポインターがあります。

#include using namespace std; // A linked list node struct Node { int data; struct Node *next; }; //insert a new node in front of the list void push(struct Node** head, int node_data) { /* 1. create and allocate node */ struct Node* newNode = new Node; /* 2. assign data to node */ newNode->data = node_data; /* 3. set next of new node as head */ newNode->next = (*head); /* 4. move the head to point to the new node */ (*head) = newNode; } //insert new node after a given node void insertAfter(struct Node* prev_node, int node_data) { /*1. check if the given prev_node is NULL */ if (prev_node == NULL) { coutnext = prev_node->next; /* 5. move the next of prev_node as new_node */ prev_node->next = newNode; } /* insert new node at the end of the linked list */ void append(struct Node** head, int node_data) { /* 1. create and allocate node */ struct Node* newNode = new Node; struct Node *last = *head; /* used in step 5*/ /* 2. assign data to the node */ newNode->data = node_data; /* 3. set next pointer of new node to null as its the last node*/ newNode->next = NULL; /* 4. if list is empty, new node becomes first node */ if (*head == NULL) { *head = newNode; return; } /* 5. Else traverse till the last node */ while (last->next != NULL) last = last->next; /* 6. Change the next of last node */ last->next = newNode; return; } // display linked list contents void displayList(struct Node *node) { //traverse the list to display each node while (node != NULL) { coutnext; } if(node== NULL) cout

出力：

最終的なリンクリスト：

30–> 20–> 50–> 10–> 40–> null

次に、Javaでリンクリスト挿入操作を実装します。 Java言語では、リンクリストはクラスとして実装されます。以下のプログラムは、ロジックがC ++プログラムに似ていますが、唯一の違いは、リンクリストにクラスを使用することです。

class LinkedList { Node head; // head of list //linked list node declaration class Node { int data; Node next; Node(int d) {data = d; next = null; } } /* Insert a new node at the front of the list */ public void push(int new_data) { //allocate and assign data to the node Node newNode = new Node(new_data); //new node becomes head of linked list newNode.next = head; //head points to new node head = newNode; } // Given a node,prev_node insert node after prev_node public void insertAfter(Node prev_node, int new_data) { //check if prev_node is null. if (prev_node == null) { System.out.println('The given node is required and cannot be null'); return; } //allocate node and assign data to it Node newNode = new Node(new_data); //next of new Node is next of prev_node newNode.next = prev_node.next; //prev_node->next is the new node. prev_node.next = newNode; } //inserts a new node at the end of the list public void append(intnew_data) { //allocate the node and assign data Node newNode = new Node(new_data); //if linked list is empty, then new node will be the head if (head == null) { head = new Node(new_data); return; } //set next of new node to null as this is the last node newNode.next = null; // if not the head node traverse the list and add it to the last Node last = head; while (last.next != null) last = last.next; //next of last becomes new node last.next = newNode; return; } //display contents of linked list public void displayList() { Node pnode = head; while (pnode != null) { System.out.print(pnode.data+'-->'); pnode = pnode.next; } if(pnode == null) System.out.print('null'); } } //Main class to call linked list class functions and construct a linked list class Main{ public static void main(String() args) { /* create an empty list */ LinkedList lList = new LinkedList(); // Insert 40. lList.append(40); // Insert 20 at the beginning. lList.push(20); // Insert 10 at the beginning. lList.push(10); // Insert 50 at the end. lList.append(50); // Insert 30, after 20. lList.insertAfter(lList.head.next, 30); System.out.println(' Final linked list: '); lList. displayList (); } }

出力：

最終的なリンクリスト：

10–> 20–> 30–> 40–> 50–> null

上記のプログラム、C ++とJavaの両方で、リストの前、リストの最後、およびノー​​ドで指定されたリストの間にノードを追加するための個別の関数があります。最後に、3つの方法すべてを使用して作成されたリストの内容を印刷します。

＃2）削除

挿入と同様に、リンクリストからノードを削除するには、ノードを削除できるさまざまな位置も含まれます。リンクリストから最初のノード、最後のノード、またはランダムなk番目のノードを削除できます。削除後、リンクリストをそのまま維持するために、リンクリスト内の次のポインタと他のポインタを適切に調整する必要があります。

次のC ++実装では、削除の2つの方法を示しています。つまり、リストの最初のノードを削除する方法と、リストの最後のノードを削除する方法です。まず、ヘッドにノードを追加してリストを作成します。次に、挿入および削除のたびにリストの内容を表示します。

#include using namespace std; /* Link list node */ struct Node { int data; struct Node* next; }; //delete first node in the linked list Node* deleteFirstNode(struct Node* head) { if (head == NULL) return NULL; // Move the head pointer to the next node Node* tempNode = head; head = head->next; delete tempNode; return head; } //delete last node from linked list Node* removeLastNode(struct Node* head) { if (head == NULL) return NULL; if (head->next == NULL) { delete head; return NULL; } // first find second last node Node* second_last = head; while (second_last->next->next != NULL) second_last = second_last->next; // Delete the last node delete (second_last->next); // set next of second_last to null second_last->next = NULL; return head; } // create linked list by adding nodes at head void push(struct Node** head, int new_data) { struct Node* newNode = new Node; newNode->data = new_data; newNode->next = (*head); (*head) = newNode; } // main function int main() { /* Start with the empty list */ Node* head = NULL; // create linked list push(&head, 2); push(&head, 4); push(&head, 6); push(&head, 8); push(&head, 10); Node* temp; cout<<'Linked list created '

出力：

リンクリストが作成されました

10–> 8–> 6–> 4–> 2–
> NULL

ヘッドノード削除後のリンクリスト

8–> 6–> 4–> 2–
> NULL

最後のノードを削除した後のリンクリスト

8–> 6–> 4–> NULL

次は、リンクリストからノードを削除するためのJava実装です。実装ロジックは、C ++プログラムで使用されているものと同じです。唯一の違いは、リンクリストがクラスとして宣言されていることです。

class Main { // Linked list node / static class Node { int data; Node next; }; // delete first node of linked list static Node deleteFirstNode(Node head) { if (head == null) return null; // Move the head pointer to the next node Node temp = head; head = head.next; return head; } // Delete the last node in linked list static Node deleteLastNode(Node head) { if (head == null) return null; if (head.next == null) { return null; } // search for second last node Node second_last = head; while (second_last.next.next != null) second_last = second_last.next; // set next of second last to null second_last.next = null; return head; } // Add nodes to the head and create linked list static Node push(Node head, int new_data) { Node newNode = new Node(); newNode.data = new_data; newNode.next = (head); (head) = newNode; return head; } //main function public static void main(String args()) { // Start with the empty list / Node head = null; //create linked list head = push(head, 1); head = push(head, 3); head = push(head, 5); head = push(head, 7); head = push(head, 9); Node temp; System.out.println('Linked list created :'); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + '-->'); if(temp == null) System.out.println('null'); head = deleteFirstNode(head); System.out.println('Linked list after deleting head node :'); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + '-->'); if(temp == null) System.out.println('null'); head = deleteLastNode(head); System.out.println('Linked list after deleting last node :'); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + '-->'); if(temp == null) System.out.println('null'); } }

出力：

リンクリストが作成されました：

9–> 7–> 5–> 3–> 1–
> null

ヘッドノード削除後のリンクリスト：

7–> 5–> 3–> 1–
> null

最後のノードを削除した後のリンクリスト：

7–> 5–> 3–> null

ノードの数を数える

リンクリストをトラバースしながら、ノード数をカウントする操作を行うことができます。上記の実装では、ノードを挿入/削除したり、リンクリストの内容を表示したりする必要があるときはいつでも、リンクリストを最初からトラバースする必要があることをすでに見てきました。

カウンターを保持し、各ノードをトラバースするときにカウンターをインクリメントすると、リンクリストに存在するノードの数がわかります。このプログラムは、読者が実装できるようにしておきます。

配列とリンクリスト

リンクリストの操作と実装を見てきましたが、配列とリンクリストがどのように公平であるかを比較してみましょう。

配列リンクリスト
配列のサイズは固定されていますリンクリストのサイズは動的です
新しい要素の挿入は高価です挿入/削除が簡単です
ランダムアクセスが許可されますランダムアクセスはできません
要素は隣接する場所にあります要素の位置が連続していない
次のポインタに余分なスペースは必要ありません次のポインタに必要な追加のメモリスペース

アプリケーション

配列とリンクリストはどちらもアイテムの格納に使用され、線形データ構造であるため、これらの構造はどちらもほとんどのアプリケーションで同様の方法で使用できます。

リンクリストのアプリケーションのいくつかは次のとおりです。

  • リンクリストを使用して、スタックとキューを実装できます。
  • リンクリストは、グラフを隣接リストとして表す必要がある場合はいつでも、グラフを実装するために使用することもできます。
  • 数学多項式は、リンクリストとして保存できます。
  • ハッシュ手法の場合、ハッシュで使用されるバケットは、リンクリストを使用して実装されます。
  • プログラムがメモリの動的割り当てを必要とするときはいつでも、リンクリストがより効率的に機能するため、リンクリストを使用できます。

結論

リンクリストは、データ項目を直線的に格納するために使用されるデータ構造ですが、連続していない場所です。リンクリストは、データ部分を含むノードのコレクションと、リスト内の次の要素のメモリアドレスを含む次のポインタです。

リストの最後の要素の次のポインタはNULLに設定されているため、リストの終わりを示します。リストの最初の要素はヘッドと呼ばれます。リンクリストは、挿入、削除、トラバーサルなどのさまざまな操作をサポートします。動的メモリ割り当ての場合、リンクリストは配列よりも優先されます。

例を使用したソフトウェアテストのバグとは

リンクリストは、配列などの要素にランダムにアクセスできないため、トラバーサルに関する限りコストがかかります。ただし、挿入と削除の操作は、配列と比較した場合、より安価です。

このチュートリアルでは、線形リンクリストについてすべて学習しました。リンクリストは、循環または二重にすることもできます。これらのリストについては、今後のチュートリアルで詳しく説明します。

=> 完全なC ++トレーニングシリーズについては、こちらを確認してください。

推奨読書

^