C언어로 연결 리스트 구현하기

gd. 이번 주는 구현이 주가 되는 과제 수행이 진행된다. 연결 리스트를 C언어로 직접 구현해보는 시간이다.
말은 이렇게 했지만 큼직큼직한 부분은 모두 잘 마련되어있다. 그래서 상대적으로 응용적인 부분에 대한 작성이 필요하다.

Insert, Delete, Find

기본 연산에 있어 세 가지 함수는 필수이다.

ListNode *findNode(LinkedList *ll, int index){
	// 노드를 찾는 함수이다.
	ListNode *temp;

	if (ll == NULL || index < 0 || index >= ll->size)
		return NULL;
    // 뭔가 이상한 상태를 차단한다.

	temp = ll->head;
    // 시작점부터 가리키기

	if (temp == NULL || index < 0)
		return NULL;
    // 혹시 모르니 여기서 이상한 상태를 한번 더 확인하기

	while (index > 0){
		temp = temp->next;
		if (temp == NULL)
			return NULL;
		index--;
	}
    // index가 0이면 적절한 위치를 찾았으니 반환

	return temp;
}

int insertNode(LinkedList *ll, int index, int value){

	ListNode *pre, *cur;

	if (ll == NULL || index < 0 || index > ll->size + 1)
		return -1;

	// 완전 첫 삽입이거나, 아니면 첫 번째 위치에 삽입을 임의로 시도하는 경우
	if (ll->head == NULL || index == 0){
    	// 첫 시작점을 일단 가리킨다. 아무것도 없다면 NULL 일 것이고, 값이 있다면 넣은 값 next로 배정한다.
		cur = ll->head;
        // 공간을 할당한다.
		ll->head = malloc(sizeof(ListNode));
        // 값을 할당한다.
		ll->head->item = value;
        // next = cur
		ll->head->next = cur;
        // 이 연결 리스트의 사이즈를 1 키운다.
		ll->size++;
		return 0;
	}
    
	// 위에 해당이 없는 경우 여기서 삽입을 진행하게 된다. 정확하게는 index 위치에 시도한다.
	if ((pre = findNode(ll, index - 1)) != NULL){
    	// pre는 index에 - 1 위치에 있다. 기존 내용을 빼두기
		cur = pre->next;
        // 그리고 실제 위치에 새로운 값을 배정한다.
		pre->next = malloc(sizeof(ListNode));
        // 실제 값을 부여한다.
		pre->next->item = value;
        // 이제 기존에 있던 값을 다시 입힌다.
		pre->next->next = cur;
        // 전체 사이즈를 1 늘린다.
		ll->size++;
		return 0;
	}

	return -1;
}

int removeNode(LinkedList *ll, int index){
	// index 번째의 내용을 지운다
	ListNode *pre, *cur;

	// 상태가 안좋은 애들 거르기
	if (ll == NULL || index < 0 || index >= ll->size)
		return -1;
        

	// 첫째 노드를 밀어버리면 수정이 반드시 필요하다
	if (index == 0){
    	// 지울 노드의 다음 노드를 일단 기억해야한다
		cur = ll->head->next;
        // 지울 노드는 그냥 밀어버린다.
		free(ll->head);
        // 다음 노드가 새로운 첫 노드가 된다.
		ll->head = cur;
        // 사이즈를 1 줄인다.
		ll->size--;

		return 0;
	}

	// 지울 노드의 직전 노드까지 찾는다.
	if ((pre = findNode(ll, index - 1)) != NULL){

		if (pre->next == NULL)
			return -1;
         // 근데 막상 지울 노드가 없는 경우를 구분한다.
		// 지울 노드를 픽한다.
		cur = pre->next;
        // 지울 노드의 다음 주소를 살아 있는 노드에 부여한다.
		pre->next = cur->next;
        // 밀어 버리기
		free(cur);
        // 사이즈 1 줄이기
		ll->size--;
		return 0;
	}

	return -1;
}

번외

void printList(LinkedList *ll){
	// 전체 인쇄하기. 그냥 순회의 일반적인 형태를 볼 수 있다.
	ListNode *cur;
	if (ll == NULL)
		return;
	cur = ll->head;

	if (cur == NULL)
		printf("Empty");
	while (cur != NULL)
	{
		printf("%d ", cur->item);
		cur = cur->next;
	}
	printf("\n");
}

void removeAllItems(LinkedList *ll)
{
	// 순회하먀 전부 밀어버리는 코드. 순회 하며 존재하는 경우 모두 free한다.
	ListNode *cur = ll->head;
	ListNode *tmp;

	while (cur != NULL){
		tmp = cur->next;
		free(cur);
		cur = tmp;
	}
	ll->head = NULL;
	ll->size = 0;
}

---

 

Quest #1 : 정렬된 리스트에 순서 지켜 삽입하기

중복 값은 허용되지 않으며, 기본 정렬은 오름차순이다.
즉, 순회를 하다가 적절하 위치를 찾으면 추가하게끔 했다. 여기서는 numCnt로 몇 번째를 해야하냐? 를 논해야 했다.

int insertSortedLL(LinkedList *ll, int item)
{	
	ListNode *cur;
	int numCnt = 0;
	if(ll->head == NULL)
	{
		cur = ll->head;
		ll->head = malloc(sizeof(ListNode));
		ll->head->item = item;
		ll->head->next = cur;
		ll->size++;
		return 0;
		// 첫 번째 아이템 삽입 위치는 반드시 0이니 당연하게 0을 반환하도록 한다.
	}
	else 
	{
		int isInsertable = 0;
		ListNode *exists;
		exists = ll->head;
		if(exists->item == item)
			return -1;

		// cur가 제대로 준비 안된 상태에서 cur->item 사용 시도해서 SegFault
		if(exists->item > item)
		{
			cur = ll->head;
			ll->head = malloc(sizeof(ListNode));
			ll->head->item = item;
			ll->head->next = exists;
			ll->size++;
			return 0;
		}
		while (isInsertable == 0)
		{
			if(exists->next == NULL)
			{
				cur = exists->next;
				exists->next = malloc(sizeof(ListNode));
				exists->next->item = item;
				exists->next->next = NULL;
				ll->size++;
				isInsertable = 1;
				return ll->size - 1;
				// 맨 끝 도달시 이렇게 반환하도록 한다.
			}

			if(exists->next->item == item) // is this already exists?
				return -1;

			if(exists->next->item < item)
			{
				exists = exists->next;
				numCnt++;
			}
			else // 아이템을 배치 해야하는 상태
			{
				ListNode *tmp = exists->next;
				cur = exists->next;
				exists->next = malloc(sizeof(ListNode));
				exists->next->item = item;
				exists->next->next = tmp;
				ll->size++;

				isInsertable = 1;
				return numCnt + 1;
			}
			
		}
	}
}

Quest #2 : 두 리스트에 대한 내용 합치기

List1, List2가 주어지면, List1.1st | List2.1st | List1.2nd | List2.2nd .... 를 둘 중에 한 리스트의 내용이 없어질 때까지 한다.
정확히는, List1이 전부 소모되면 List2도 더 이용 할 수 없다. 그러나 List2가 전부 소모되면, List1은 전부 이용한다.

그니까 이게.. List1 사이사이에 List2의 아이템을 끼는 개념인데, List2가 아이템이 더 없고 List1이 남았다면 더 끼워넣지 않는 채로 진행된다는 것. 따라서 이것은 List1이 아이템이 얼마나 있냐를 우선적인 진행 조건으로써 생각해야 한다.

void alternateMergeLinkedList(LinkedList *ll1, LinkedList *ll2)
{
	ListNode *target = ll1->head;
	while(target != NULL)
	{
		ListNode *nxtTarget = target->next;
		if(ll2->head != NULL)
		{
			ListNode *insertTarget = ll2->head;
			ll2->head = ll2->head->next;

			insertTarget->next = target->next;
			target->next = insertTarget;
		}
		target = nxtTarget;
	}
}

Quest #3 : 홀수 아이템 뒤로 보내기

도움되라고 주석을 많이 쓰다가 주석에 모든 내용을 담았다.

void moveOddItemsToBack(LinkedList *ll)
{
	
	LinkedList* tmpll = malloc(sizeof(LinkedList));
	tmpll->head = NULL;
	tmpll->size = 0;
	// 해당 되는 수 (여기서는 홀수)를 저장 할 연결리스트 신규 선언

	ListNode *cur;
	// 모든 아이템 순회에 필요한 커서 선언
	ListNode *BackupNext;
	// 홀수 처리 발생시, 다음 목적지 누락 방지를 위한 백업
	ListNode *latestEven = NULL;
	// 가장 마지막에 있는 짝수 노드에 최종 완성된 홀수 리스트를 이어 줄 예정.
	
	if (ll == NULL)
		return;
	// 유효하지 않은 연결 리스트에 대한 작동 차단
	cur = ll->head;
	int visitedCount = 0;
	// 사전 정의 함수 사용을 위해서는 n번째 위치 파악이 필요하여 선언.
	while (cur != NULL)
	{
		BackupNext = cur->next;
		// 목적지 누락 방지
		if((cur->item % 2) == 1)
		{
			insertNode(tmpll, tmpll->size, cur->item);
			int a = removeNode(ll, visitedCount);
			// 홀수에 대한 처리로, 별도의 연결 리스트에 추가하며 기존 연결 리스트에서 제거
			visitedCount--;
			// 기존 리스트에서 한 개의 아이템이 빠졌으니 길이도 달라짐, 이 visitedCount로 해당 내용에 맞춰 조정되어야함.
			
		}
		else
		{
			latestEven = cur;
			// 짝수의 경우 붙여줘야하는 위치를 현재 위치로 조정하기
		}
		visitedCount++;

		cur = BackupNext;
		// cur 갱신 후 쭉 진행
	}
	// 전체 내용 마무리 된 경우, 마지막에 ll에 매핑시켜서 끝내기
	if(latestEven != NULL)
		latestEven->next = tmpll->head;
	else
		ll->head = tmpll->head;
	
	free(tmpll);
	// is free
}

Quest #4 : 짝수 뒤로 보내기

#3과 한 글자 다르다. 다만 여긴 주석이 없고 아주 조금은 다르지만, 핀트는 완전히 같다.

void moveEvenItemsToBack(LinkedList *ll)
{
	LinkedList tmpll;
	tmpll.head = NULL;
	tmpll.size = 0;

	ListNode *cur;
	ListNode *BackupNext;
	ListNode *latestOdd = NULL;
	if (ll == NULL)
		return;
	cur = ll->head;
	int visitedCount = 0;
	while (cur != NULL)
	{
		BackupNext = cur->next;
		if((cur->item % 2) == 0)
		{
			insertNode(&tmpll, tmpll.size, cur->item);
			int a = removeNode(ll, visitedCount);
			visitedCount--;
			// delete this node.
		}
		else
		{
			latestOdd = cur;
		}
		visitedCount++;

		cur = BackupNext;
	}
	if(latestOdd != NULL)
		latestOdd->next = tmpll.head;
	else
		ll->head = tmpll.head;
	// 
}

Quest #5 : 주어진 리스트 2등분 하기

단, 홀수인경우 첫번째 리스트가 1 더 길게 배치한다.

void frontBackSplitLinkedList(LinkedList *ll, LinkedList *resultFrontList, LinkedList *resultBackList)
{
	int pivotCount = ll->size;
	if(pivotCount % 2 == 1)
	{
		pivotCount /= 2;
		pivotCount += 1;
	}
	else
	{
		pivotCount /= 2;
	}
    // pivotCount가 리스트 아이템 갯수를 찢는 기준이 된다.

	ListNode *target;
	target = ll->head;
	int cnt = 0;
	resultFrontList->head = ll->head;
	while (target != NULL)
	{
		cnt++;
		if(cnt == pivotCount)
		{
        	// cnt가 설정한 값에 도달하면
            // 해당 시점부터의 리스트를 찢는다
			ListNode *rightHead;
			rightHead = target->next;
			target->next = NULL;
			resultBackList->head = rightHead;
		}
		target = target->next;
	}
		
}

Quest #6 : 최대값을 첫 위치로 보내기

어쨌든 최대값을 구하려면 전체 순회를 하며 해당 위치를 알아야한다. 그리고 해당 위치와 관련되어 조정을 하려고 하겠다면 해당 위치 그 자체가 아니라 해당 위치 한 칸 이전에서 조정이 필요하다. 최대값을 갱신하면서 왜 최대값을 가리키는 노드를 해당 노드 전으로 했는지에 대해 이해하는데 도움이 될 것이다.

마지막에 도달하면 찍어뒀던 노드에 대해 직접적인 위치 조정 후 마무리된다.

int moveMaxToFront(ListNode **ptrHead)
{
	// 값을 직접 조정하기 위해선 해당 노드를 알아보긴 하되, 해당 노드 이전에서 조작이 일어나야한다.
	ListNode *prev = NULL, *cur = NULL;

	if( (*ptrHead) == NULL)
		return -1;
     

	prev = (*ptrHead);
	cur = prev->next;
	int maxItemValue = 0;
	ListNode *maxItemPos, *maxItemPosPrev;
	
	while(cur != NULL)
	{
		int prevMax = maxItemValue;
		maxItemValue = max(maxItemValue, cur->item);
		if(prevMax != maxItemValue)
		{
			// 최대 수가 수정되면 최대 기준점, 그리고 최대의 위치 전부 수정 되게끔 해야한다.
			maxItemPos = cur;
			maxItemPosPrev = prev;
		}
        // 꼭 해당이 아니더라도 cur와 prev는 계속 돌게끔 해야한다.
		prev = cur;
		cur = cur->next;
	}
		// 리스트에 끝에 도달한경우 우리가 얻은 데이터를 실 적용 해야한다.
		maxItemPosPrev->next = maxItemPos->next;
		ListNode *backUp = (*ptrHead);
		(*ptrHead) = maxItemPos;
		(*ptrHead)->next = backUp;
        // 맨 앞으로 값을 끌고오는 과정
}

Quest #7 : 재귀적으로 리스트 내용 뒤집기

void RecursiveReverse(ListNode **ptrHead)
{
	// 이중 포인터를 사용한다. 해당 포인터는 리스트의 첫 시작점을 가리키는 주소의 위치를 말한다.
	ListNode *first = NULL, *rest = NULL;
	first = (*ptrHead);
	rest = first->next;
    // 맨 좌측 노드를 뺀 상태로 새롭게 재귀를 시도한다.
    // 한 칸씩 뒤집어야하는 만큼, base case를 찍어야한다.

	if(rest == NULL)
		return;
	
	RecursiveReverse(&rest);

	first->next->next = first;
    // 5 4 3 2 1 이 기준이고 지금 2 1을 논하고 있다고 하자.
    // 1의 다음을 2로 배정하면, 2 -> 1 -> 저 왼쪽에 있던 2를 가리키게 된다.
	first->next = NULL;
    // 기존 좌측에 위치하는 2의 연결을 끊는다. 1 -> 2가 된다.
	*ptrHead = rest;
    // 다음 진행이 가능하게끔 다시 넘겨준다.
}

수시로 수정하며 수습해야 할 것만 같다.