[C언어] Linked List (1) - insertSortedLL 함수 구현하기

Linked List (1) - insertSortedLL 함수 구현하기

정수 하나를 입력받아 오름차순으로 정렬된 연결 리스트에 삽입하는 함수

주어진 요소 확인하기

구조체

• LinkedList: (struct) 연결 리스트 구조체
  • size: (int field) 연결 리스트 요소 갯수
  • *head: (pointer field) 연결 리스트 첫 노드의 주소
• ListNode: (struct) 노드 구조체
  • item: (int field) 노드의 값
  • *next: (pointer field) 다음 노드의 주소

insertSortedLL 함수의 매개 변수

• *ll: (pointer) 연결 리스트 주소
• item: (int) 삽입할 값

 

핵심 아이디어

• 먼저 정렬된 순으로 삽입된 연결 리스트에서 cur(현재 노드의 주소)을 추적하며, 삽입할 값을 넣을 위치(idx)를 찾아야 한다.
• 연결 리스트에 값을 삽입하기 위해서는 prev(이전 노드의 주소)를 추적해야 한다.
• 만약 중복된 값이 있는 경우, 삽입을 진행하지 않고 -1을 즉시 반환한다.
• 이외의 경우 해당 인덱스에 노드를 삽입하고 size를 1 증가시킨 후, idx를 반환한다.
  • 만약, 첫 노드를 삽입하는 경우, head에 해당 노드를 연결한다.

 

구현하기

int insertSortedLL(LinkedList *ll, int item)
{
	ListNode *cur = ll->head;
	ListNode *prev = NULL;

	int i = 0;
	while (cur != NULL) {
		if (item < cur->item) {
			break; 
		} else if (cur->item == item) {
			i = -1;
			break;
		} else {
			i++;
			prev = cur;
			cur = cur->next;
		}
	}

	if (i == -1) {
		return -1;
	}

	ListNode *new_node = malloc(sizeof(ListNode));
	new_node->item = item;
	new_node->next = cur;
	if (prev != NULL) {
		prev->next = new_node;
	} else {
		ll->head = new_node;
	}
	
	ll->size++;
	return i;
}