[연결리스트 ADT] 추가 기능 구현 2가지 방법

1. Head & Tail 사용하기

Head와 Tail을 사용하면 경우를 생각하지 않아도 된다.

왜냐하면, Tail의 존재로 인해 NULLPOINT가 생길 수 없다.

따라서, Head부터 순회를 하면서 IDX가 0이 되면, 그자리의 노드를 밀어내고 그자리에 새로운 노드를 넣으면 된다.

 

void Add(List* list,int r, char c) {
	Node* NewNode = (Node*)malloc(sizeof(Node));
	NewNode->data = c;
	NewNode->next = NULL;
	NewNode->prev = NULL;
	
	Node* cur = list->Head;
	if (cur->next == list->Tail) {
		cur->next = NewNode;
		list->Tail->prev = NewNode;
		NewNode->prev = list->Head;
		NewNode->next = list->Tail;
		return;
	}

	int idx = r;
	while (idx > 0 && cur != list->Tail) {
		cur = cur->next;
		idx--;
	}
    
	//기존 노드 밀어내고 그자리에 새로운 노드 추가
	NewNode->next = cur;
	NewNode->prev = cur->prev;
	cur->prev->next = NewNode;
	cur->prev = NewNode;
	
}

 

---

2. Head만 사용하기

이 경우는 Tail이 없기 때문에 크게 두가지로 나누어서 구현한다.

1) 새롭게 추가하는 경우

2) 기존 노드를 밀어내는 경우

 

하나하나 살펴보도록 하자.

 

 

노드를 Head부터 순회하면서 다음 노드가 NULL인 경우까지 진행한다. 동시에 idx를 -1씩하며 원하는 포지션을 찾는다.

만약, idx가 1이라는 말은 원하는 포지션에는 노드가 비어있기 때문이다.

만역, idx가 0이라는 말은 그 자리에 이미 노드가 있기 때문에 기존 노드를 밀어내야한다.

 

1) 새롭게 추가하는 경우

NULLPOINT를 조심하면서 prev와 next를 변경한다.

 

2) 기존 노드를 밀어내는 경우

이미 기존 노드가 있기 때문에 NULLPOINT를 걱정할 필요가 없이 기존처럼 prev와 next를 변경한다.

 

void Add(Node* list, int idx, int data) {
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;
	newNode->prev = NULL;
	newNode->next = NULL;

	if (idx < 1) {
		printf("invalid position\n");
		return;
	}

	Node* cur = list;

	if (cur->next == NULL) {
		if (idx > 1) {
			printf("invalid position\n");
			return;
		}
		cur->next = newNode;
		newNode->prev = cur;
		return;
	}

	while (cur->next != NULL && idx > 0) {
		cur = cur->next;
		idx--;
	}

	// 새로 추가
	if (idx == 1) {
		newNode->prev = cur;
		newNode->next = cur->next;
		cur->next = newNode;

	}
	// 밀어내기
	else if (idx == 0) {
		newNode->next = cur;
		newNode->prev = cur->prev;
		cur->prev->next = newNode;
		cur->prev = newNode;

	}
}