リンクリスト(接続リスト)リンクリスト

リスト。

[固定順序](Fixed Order)リストで、
ある定義によって決定される「論理順序」の羅列.
リストの順序は、データがどの物理的な位置に格納されているか、または
これは、リスト内の要素間の意味のある順序を意味します.

配列とリストの違いは?

整列

索引として表示される「順序」
配列要素のメモリ領域の物理的意味.

インベントリ

リストの「順序」の概念は
ある定義によって決定される「論理順序」.
要素の物理的な格納順序や場所には関係ありません.
要素間の論理順序のみを維持します.

リストの実装方法

1）ポインタの使い方

원소값을 저장하는 공간課다음 원소를 가리키는 위치 정보를 저장하는 공간乙
一緒に表現する方法です.
👍 長所

必要に応じて任意の数のオブジェクトを生成するので無駄なところはない.

👎 短所
ポインタを格納するスペースが必要なため、各オブジェクトに必要なメモリは配列よりも大きい.

2）配列方法

配列を作成し、中央にデータを挿入します.
👍 長所

スピードが速い

👎 短所

挿入する位置の後ろのデータはすべて後ろに1マス押してから挿入する.

削除する場合も、削除する位置の後ろのデータを前に1マス引きます.

これらの動作は要素の数に比例してプログラム実行時間を大幅に増加させる.
リストは一般的にポインタを使用して実現されます.

こうぞう

ノード(ノード)

リンクリストにオブジェクトを格納

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

data:構造体内部にデータを格納

next:以下のノードのアドレスを格納

ListNode* head = NULL;

head:リンクリストの先頭へ
データにアクセスするには、head変数
に届く

えんざん

挿入

データは、リストの最初の場所または必要な場所に挿入できます.headデータがない場合、初めてデータを挿入します.
データがあれば、ノードはパラメータで渡されるpositionの位置に挿入されます.positionの値が1の場合は、1番目を挿入します.
ノードの長さがデータの長さより大きい場合は、リストの最後にノードが挿入されます.

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;
	}
}

削除

上の挿入ノードコードに示すように.position中の因子headの位置
該当するノードを削除します.
削除する場合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);
	}
}

長さ

リンクリストの長さを取得するには
要探索position最後head

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";
}

💡 注意:配置

[C++]接続リストリンクリストコードの実装方法
単一接続リストの説明とサンプルコード(C++)