単一リンクリスト(Singly Linked List)の説明とサンプルコード(C ++)

リンクリスト(Linked List、リンクリスト)は、データのセットを保存するために使用されるデータ構造です。 連続的なデータ構造になっており、配列と比較して長所と短所があります。

リンクリストは、次の属性を持っています。

  • 連続項目がポインタで接続
  • 最後のエントリは、NULLを指す
  • 動的にリストのサイズが大きくなったり減少することがあります
  • 必要に応じて使用するため、不要なメモリを無駄にしない

リンクリストは、配列で実装することができて、ポインタを利用して実装することもできます。配列の場合、速度が速いが、一定のメモリを事前に確保しなければならない短所があります。 一方、ポインタを利用する場合、必要に応じ、オブジェクトを生成するための無駄になる部分がありません。しかし、ポインタを格納するスペースが必要なため、オブジェクト1個あたりに必要なメモリが配列よりも大きくなる点があり書き込みます。

この記事では、サンプルコードへのポインタを利用した単一のリンクリスト(Singly Linked List)をC ++で実装しました。 完成したコードは、GitHub - Singly Linked Listにあります コードのみ注方はGitHubをご確認ください。

リンクリストのデータ構造

リンクリストにデータが保存されるオブジェクトの1つをノード(Node)と呼ばれます。

コードでこのように定義することができます。構造体の内部には、データを格納する dataと次のノードのアドレスを格納するnext変数があります。

typedef struct ListNode {
	int data;
	struct ListNode* next;
} ListNode;

そしてリンクリストの最初を指す headという変数があります。データにアクセスするには、この変数を使ってアクセスすることができます。

ListNode* head = NULL;

リンクリストにデータを挿入する

データは、リストの最初または任意の場所に挿入することができます。 次のコードは、リストの挿入コードです。 headに何のデータがない場合は一番最初にデータが挿入され、データがある場合は、引数として渡されたpositionの位置にノードが挿入されます。 positionの値が1であれば、最も最初に挿入されます。データの長さよりもpositionが大きい面リストの一番最後にノードが挿入されます。

void InsertInLinkedList(ListNode**head, int data, int position) {
	ListNode* inserted = new ListNode;
	inserted->data = data;

	if (position == 1 || *head == NULL) {
		inserted->next = *head;
		*head = inserted;
	}
	else {
		ListNode* inserted_prev = *head;
		for (int i = 1; (inserted_prev->next != NULL) && (i < position-1); i++) {
			inserted_prev = inserted_prev->next;
		}

		ListNode* inserted_next = inserted_prev->next;
		inserted_prev->next = inserted;
		inserted->next = inserted_next;
	}
}

リンクリストの長さ

リンクリストの長さを取得するには、headから最後NULLまで移動する必要があります。 以下のように実装することができます。

int ListLength(struct ListNode* head) {
	int len = 0;
	struct ListNode* current = head;
	while (current!= NULL)
	{
		len++;
		current = current->next;
	}
	return len;
}

リンクリストのすべてのデータ出力

リストの長さを求めるコードのように、すべてのリストを参照しながら、データを出力します。

void PrintList(struct ListNode* head) {
	struct ListNode* current = head;
	while (current != NULL)
	{
		cout << current->data << " -> ";
		current = current->next;
	}
	cout << "NULL\n";
}

リンクリストのノードの削除

上記のノードを挿入コードのように、 headで引数positionの位置に対応するノードを削除します。 削除したいpositionにノードが存在しない場合は、最後のノードを削除します。

void DeleteNodeFromLinkedList(ListNode** head, int position) {
	if (*head == NULL) {
		cout << "List empty" << "\n";
		return;
	}
	ListNode* removed_prev;
	ListNode* removed;
	if (position == 1) {
		removed = *head;
		*head = (*head)->next;
		delete(removed);
	}
	else {
		ListNode* removed_prev = *head;
		removed = removed_prev->next;
		for (int i = 1; (removed->next != NULL) && (i < position-1); i++) {
			removed_prev = removed_prev->next;
			removed = removed_prev->next;
		}
		removed_prev->next = removed->next;
		delete(removed);
	}
}

完成したコード

完成したコードは、GitHub - Singly Linked Listにあります。

mainを実行してみると、ノードが生成され、削除されたことを見ることができます。

ListNode* head = NULL;
int main()
{
	InsertInLinkedList(&head, 4, 1);
	InsertInLinkedList(&head, 17, 1);
	InsertInLinkedList(&head, 1, 1);
	InsertInLinkedList(&head, 5, 1);

	PrintList(head);
	InsertInLinkedList(&head, 10, 1);
	PrintList(head);
	InsertInLinkedList(&head, 11, 3);
	PrintList(head);
	InsertInLinkedList(&head, 11, 9);
	PrintList(head);
	DeleteNodeFromLinkedList(&head, 1);
	PrintList(head);
	DeleteNodeFromLinkedList(&head, 3);
	PrintList(head);
	DeleteNodeFromLinkedList(&head, 10);
	PrintList(head);
}

実行結果

5 -> 1 -> 17 -> 4 -> NULL
10 -> 5 -> 1 -> 17 -> 4 -> NULL
10 -> 5 -> 11 -> 1 -> 17 -> 4 -> NULL
10 -> 5 -> 11 -> 1 -> 17 -> 4 -> 11 -> NULL
5 -> 11 -> 1 -> 17 -> 4 -> 11 -> NULL
5 -> 11 -> 17 -> 4 -> 11 -> NULL
5 -> 11 -> 17 -> 4 -> NULL

参考

次の文は、双方向リンクリスト(リンクリスト)の説明とサンプルコード(C ++)です。

codechachaCopyright ©2019 codechacha