Linked LIst의 정렬 (입력 할 때마다 O(N))

NODE* add(int track)
{
	NODE* n = myalloc();
	n->t = track;

	if (ht[KEY(track)] == NULL)
	{
		n->next = ht[KEY(track)];
		ht[KEY(track)] = n;
	}
	else
	{
	NODE* prev = NULL;
		for (NODE* p = ht[KEY(track)]; p != NULL; prev = p, p = p->next)
		{
			if (n->t > p->t)
			{
				if (prev == NULL)
				{
					n->next = p;
					ht[KEY(track)] = n;
					break;
				}
				else
				{
					// 4¹ø
					prev->next = n;
					n->next = p;
					break;
				}
			}
			else
			{
				if (p->next == NULL)
				{
					//2¹ø
					p->next = n;
					n->next = NULL;
					break;
				}
				else
				{
					continue;
				}
			}
		}
	}

	/*for (NODE* pp = ht[KEY(track)]; pp != NULL; pp = pp->next)
	{
		printf("%d ", pp->t);
	}
	printf("\n");*/
	return n;
}

 

총 4가지의 Case가 있다.

1. List가 비어있는 경우

2. 가장 앞에 들어가는 경우

3. 가운데 들어가는 경우

4. 가장 마지막에 들어가는 경우

 

연산자 1개만 바꿔주면, 오름차순, 내림차순으로 구현이 가능하다.

대신 시간 복잡도는 O(N)이다.

 

NODE* prev 하나를 만들어서 작업해야한다.

 

머리아프다.