[C++ Fundamentals of Data Structures/C++ 자료구조론(이석호)] 4.4 원형 리스트 체인 연습 문제

1. 체인에 있는 노드의 수를 계산하는 C++ 함수 length를 작성하라. 이 함수의 시간 복잡도는 얼마인가?

	int length() {
		ChainNode<T>* ptr;
		if (isEmpty()) {
			return 0;
		}
		int length = 1;
		for (ptr = head->link; ptr != head; ptr = ptr->link)
			length++;
		return length;
	}

* 시간 복잡도 : O(n) 원소의 개수만큼 반복

* 노드가 공백인 경우는 길이 0 반환. 아닌 경우는 1부터 시작하여 ptr을 head노드가 가르키는 노드부터 시작하여 head가 아닐때까지 반복 시킴.

 

 

2. x를 체인에 있는 임의의 노드를 지시하는 포인터라고 하자. 체인으로부터 이것을 삭제하는 C++ 함수를 작성하라.

만일 x == first라고 하면, first는 체인에서 새로 첫 번째가 된 노드를 가리키도록 반드시 재설정 되어야 한다. 이 함수의 시간 복잡도는 얼마인가?

 

	void Delete(ChainNode<T>* x) {
		if (x == head)
			head = head->link;
		else {
			ChainNode* ptr;
			for (ptr = head->link; ptr != x; ptr = ptr->link);
			ptr->link = x->link;
		}
		delete x;
	}

* 시간복잡도 : O(n) //원소 개수 -  x가 위치한 노드의 원소 위치

* 단순 연결리스트와 방법 동일. But, 반복문이 조금 다름

* KMOOC강의에서 본 퀴즈 유심히 복습!

* 4,5,6,8,9,10은 2회독 때!

* https://huangdi.tistory.com/99

* https://jaimemin.tistory.com/162

아직도 두 풀이 이해 못 함 노드 너무 어려워잉 ~!