[資料構造]4.インベントリ2

円形の接続リスト
円形接続リストは、リスト内の最後のノードのリンクがNULLではなく、最初のノードアドレスのリストです.
円形接続リストの利点であれば、1つのノードから他のすべてのノードにアクセスできます.
1つのノードでリンクに従い続け、最終的にはすべてのノードを通じて自分に戻ることができるので、任意のノードに到達することができます.
したがって、ノードの挿入と削除は、単純な接続リストよりも容易です.
削除または挿入には、常に前のノードのポインタが必要であることを覚えておいてください.

円形接続リストが特に有用である場合、リストの最後にノードを挿入する演算は、単純な接続リストよりも有効である可能性があります.
単純接続リストのリストの最後にノードを挿入するには、最初のノードからリンクに沿って最後のノードまでノード数で操作してから挿入する必要があります.
ただし、[円形接続](Circular Connections)リストで最後のノードを指すようにヘッドポインタを設定すると、リストの先頭または末尾に一定時間ノードを挿入できます.

この変形した円形接続リストを使用して、リストの先頭に挿入された関数を作成します.
まず、新しいノードのリンクnode->linkを最初のノードに、最後のノードのリンクをノードに向けるようにします.
headポインタが最後のノードを指していることを覚えておけば、ソースを理解するのに問題はありません.

void insert_first(ListNode** phead,ListNode* node) {

	if (*phead == NULL) {
		*phead = node;
		node->link = node;
	}

	else {
		node->link = (*phead)->link;
		(*phead)->link = node;
	}
}

上記のアルゴリズムに文を追加するだけで、円形接続リストの最後に挿入できます.
つまり、丸接続リストはどうせ丸接続なので、どこが一番、どこが最後なのかよくわかりません.
したがってheadの位置のみを新しいノードに変更すると、新しいノードは最後のノードになります.

void insert_last(ListNode** phead, ListNode* node) {
	if (*phead == NULL) {
		*phead = node;
		node->link = node;
	}

	else {
		node->link = (*phead)->link;
		(*phead)->link = node;
		*phead = node;
	}
}

テストプログラム
プロトタイプリストにはこのような利点があるが、display関数の実装に示すように、最後のノードのリンクはNULLではないので、リストが最後に達したかどうかをチェックするには、ヘッダポインタと比較する必要がある.
また、whileではなくdo-whileループを使用する必要があります.

#include <stdio.h>

typedef int element;
typedef struct ListNode {
	element data;
	struct ListNode* link;
}ListNode;

void error(char* message) {
	fprintf(stderr, "%s\n", message);
	exit(1);
}

ListNode* create_node(element data, ListNode* link) {
	ListNode* new_node;
	new_node = (ListNode*)malloc(sizeof(ListNode));
	if (new_node == NULL) error("메모리 할당 에러");
	new_node->data = data;
	new_node->link = link;

	return new_node;
}

void display(ListNode* head) {

	ListNode* p;
	if (head == NULL)return;
	else head = head->link;

	p = head;
	do {
		printf("%d->", p->data);
		p = p->link;
	} while (p != head);
}

void insert_first(ListNode** phead,ListNode* node) {

	if (*phead == NULL) {
		*phead = node;
		node->link = node;
	}

	else {
		node->link = (*phead)->link;
		(*phead)->link = node;
	}
}

void insert_last(ListNode** phead, ListNode* node) {
	if (*phead == NULL) {
		*phead = node;
		node->link = node;
	}

	else {
		node->link = (*phead)->link;
		(*phead)->link = node;
		*phead = node;
	}
}

int main() {

	ListNode* list1 = NULL;

	insert_first(&list1, create_node(10, NULL));
	insert_first(&list1, create_node(20, NULL));
	insert_last(&list1, create_node(30, NULL));

	display(list1);

	return 0;
}