[ 자료구조 ] Linked List: Move Max To Front

김쟇연·2025년 4월 15일

C c언어 linkedlist movemax 구조체 노드 단일연결리스트 리스트조작 리스트탐색 연결리스트 자료구조활용 최댓값찾기 포인터 포인터연결변경

Data Structures

목록 보기

6/6

금쪽이들 잘 따라오고 있나요?

이번에는 6번문제를 풀어볼게요~! 😄

Q6_A_LL (moveMaxToFront)

"가장 큰 수를 맨 앞으로 옮겨주세요~!"

6. (moveMaxToFront) Write a C function moveMaxToFront() that traverses a linked list 
of integers at most once, then moves the node with the largest stored value to the front of the 
list.  
 
The function prototype is given as follows: 
int moveMaxToFront(ListNode **ptrHead); 
 
For example, if the linked list is (30, 20, 40, 70, 50), the resulting linked list will be (70, 30, 20, 40, 
50). 
 
1: Insert an integer to the linked list: 
2:  Move  the  node  with  the  largest  stored  value  to  the  front  of  the 
list: 
0: Quit: 
 
Please input your choice(1/2/0): 1 
Input an integer that you want to add to the linked list: 30 
The Linked List is: 30 
Please input your choice(1/2/0): 1 
Input an integer that you want to add to the linked list: 20 
The Linked List is: 30 20 
Please input your choice(1/2/0): 1 
Input an integer that you want to add to the linked list: 40 
The Linked List is: 30 20 40 
Please input your choice(1/2/0): 1 
Input an integer that you want to add to the linked list: 70 
The Linked List is: 30 20 40 70 
Please input your choice(1/2/0): 1 
Input an integer that you want to add to the linked list: 50 
The Linked List is: 30 20 40 70 50 
 
Please input your choice(1/2/0): 2 
The resulting Linked List is: 70 30 20 40 50 
 
Please input your choice(1/2/0): 0

🧠 이 함수, 뭘 하는 걸까요?

하나의 연결 리스트가 있어요.

그 안에는 숫자들이 들어 있어요.

우리가 할 일은요~

그 중에서 가장 큰 숫자를 가진 노드 하나만 골라서

맨 앞으로 옮겨주는 거예요! 🥇

📌 조건 & 특징 정리

조건	설명
단 한 번만 순회 가능	while 한 번만 돌 수 있어요! 효율성 테스트~ ⏱️
값이 아니라 노드를 옮긴다	단순 swap❌ → 노드 자체를 앞으로 이동시켜야 해요!
최대값은 첫 번째로!	맨 앞(head)가 최대값 노드를 가리키게 해야 해요
리스트가 비어 있거나 하나라면	그냥 가만히 있어도 돼요~ 😊

📋 함수 원형

c

int moveMaxToFront(ListNode **ptrHead);

💡 왜 `ListNode` 인가요?

🧠 리스트의 head 자체를 바꿀 수도 있기 때문이에요!

예: 원래 head가 30이었는데,

70이라는 큰 값이 들어오면

head가 70을 가리켜야 하잖아요~?

👩‍🏫 예시로 보기

입력 전:

makefile

리스트: 30 → 20 → 40 → 70 → 50

현재 head는 30이에요.

함수 실행 후:

makefile

리스트: 70 → 30 → 20 → 40 → 50

70이라는 가장 큰 값이 head 자리로 올라왔어요!

뒤 순서는 그대로 유지하고,

단지 제일 큰 친구만 맨 앞에 서게 해주는 거예요! 👑

🔍 주요 기능 흐름 요약

리스트를 한 번만 순회하면서
가장 큰 값의 노드와 그 이전 노드(prevMax)를 기억하고
head 앞으로 이동!

💡 어떤 상황에 유용할까요?

우선순위가 가장 높은 데이터를 빠르게 뽑아야 할 때
최대값 기준으로 리스트를 재정렬하지 않고 일부만 바꾸고 싶을 때
연결 리스트의 동적 구조를 효율적으로 조작하고 싶을 때

💛 선생님의 따뜻한 정리

“이 함수는요~

리스트 안의 친구들 중에서 가장 리더십 있는 친구를

앞으로 한 걸음 나오게 해주는 거예요~

그냥 제일 큰 숫자를 바꾸는 게 아니라,

그 아이 자체의 자리를 바꿔주는 배려 있는 동작이죠~

아이들이 줄 서 있는 순서를

한 번만 살펴보면서

‘누가 제일 앞에 서면 좋을까~?’ 고민하는 아주 예쁜 문제예요 😊

정말 중요한 개념들이 많답니다~

지금부터 저랑 같이 하나씩 풀어보면 돼요~

정말 잘하고 있어요~ 한 번 더 안아주세요~ 🤗💛”

code

//////////////////////////////////////////////////////////////////////////////////

/* CE1007/CZ1007 Data Structures
Lab Test: Section A - Linked List Questions
Purpose: Implementing the required functions for Question 6 */

//////////////////////////////////////////////////////////////////////////////////

#include <stdio.h>
#include <stdlib.h>

//////////////////////////////////////////////////////////////////////////////////

typedef struct _listnode
{
	int item;
	struct _listnode *next;
} ListNode;			// You should not change the definition of ListNode

typedef struct _linkedlist
{
	int size;
	ListNode *head;
} LinkedList;			// You should not change the definition of LinkedList

//////////////////////// function prototypes /////////////////////////////////////

// You should not change the prototype of this function
int moveMaxToFront(ListNode **ptrHead);

void printList(LinkedList *ll);
void removeAllItems(LinkedList *ll);
ListNode * findNode(LinkedList *ll, int index);
int insertNode(LinkedList *ll, int index, int value);
int removeNode(LinkedList *ll, int index);

//////////////////////////// main() //////////////////////////////////////////////

int main()
{
	int c, i, j;
	c = 1;

	LinkedList ll;
	//Initialize the linked list 1 as an empty linked list
	ll.head = NULL;
	ll.size = 0;

	printf("1: Insert an integer to the linked list:\n");
	printf("2: Move the largest stored value to the front of the list:\n");
	printf("0: Quit:\n");

	while (c != 0)
	{
		printf("Please input your choice(1/2/0): ");
		scanf("%d", &c);

		switch (c)
		{
		case 1:
			printf("Input an integer that you want to add to the linked list: ");
			scanf("%d", &i);
			j=insertNode(&ll, ll.size, i);
			printf("The resulting linked list is: ");
			printList(&ll);
			break;
		case 2:
			moveMaxToFront(&(ll.head));  // You need to code this function
			printf("The resulting linked list after moving largest stored value to the front of the list is: ");
			printList(&ll);
			removeAllItems(&ll);
			break;
		case 0:
			removeAllItems(&ll);
			break;
		default:
			printf("Choice unknown;\n");
			break;
		}
	}
	return 0;
}

////////////////////////////////////////////////////////////////////////

int moveMaxToFront(ListNode **ptrHead)
{
    /* add your code here */
}

//////////////////////////////////////////////////////////////////////////////////

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");
}

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--;
	}

	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 empty list or inserting first node, need to update head pointer
	if (ll->head == NULL || index == 0){
		cur = ll->head;
		ll->head = malloc(sizeof(ListNode));
		ll->head->item = value;
		ll->head->next = cur;
		ll->size++;
		return 0;
	}

	// Find the nodes before and at the target position
	// Create a new node and reconnect the links
	if ((pre = findNode(ll, index - 1)) != NULL){
		cur = pre->next;
		pre->next = malloc(sizeof(ListNode));
		pre->next->item = value;
		pre->next->next = cur;
		ll->size++;
		return 0;
	}

	return -1;
}

int removeNode(LinkedList *ll, int index){

	ListNode *pre, *cur;

	// Highest index we can remove is size-1
	if (ll == NULL || index < 0 || index >= ll->size)
		return -1;

	// If removing first node, need to update head pointer
	if (index == 0){
		cur = ll->head->next;
		free(ll->head);
		ll->head = cur;
		ll->size--;

		return 0;
	}

	// Find the nodes before and after the target position
	// Free the target node and reconnect the links
	if ((pre = findNode(ll, index - 1)) != NULL){

		if (pre->next == NULL)
			return -1;

		cur = pre->next;
		pre->next = cur->next;
		free(cur);
		ll->size--;
		return 0;
	}

	return -1;
}

void removeAllItems(LinkedList *ll)
{
	ListNode *cur = ll->head;
	ListNode *tmp;

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

그럼 지금부터 이 문제의 전체 기본 코드 틀을

✨ 한 줄 한 줄 따뜻하고 쉽게 설명해줄게요~ 😊

우리 금쪽이가 비슷한 문제를 이미 몇 개 풀어봐서

공통된 앞부분 코드들은 생략해볼까요? 🙌

🧾 31~87행: `main()` 함수 – 사용자 인터페이스 중심

c

int main()

프로그램이 시작되는 입구예요!

“여기서부터 모든 일이 펼쳐져요~ 🎬”

33~36행: 변수 선언과 리스트 초기화

c

int c, i, j;
c = 1;

LinkedList ll;
ll.head = NULL;
ll.size = 0;

c: 사용자의 선택i: 입력받는 정수j: 삽입 결과값

그리고 ll은 비어있는 연결 리스트 상태로 시작해요~

“이제 아이들이 줄을 서기 전, 아무도 없는 상태죠~”

39~41행: 메뉴 안내

c

printf("1: Insert an integer to the linked list:\n");
printf("2: Move the largest stored value to the front of the list:\n");
printf("0: Quit:\n");

사용자에게 “어떤 걸 하고 싶으세요?” 하고

메뉴를 친절하게 보여줘요~ 😊

43~85행: 사용자 선택을 반복하는 `while` 루프

c

while (c != 0)

c가 0이 아니면 계속 반복해요~

“그만하겠다고 할 때까지 계속 도와주는 구조예요~”

45행: 사용자 선택 받기

c

scanf("%d", &c);

사용자가 고른 메뉴 번호를 받아요~

“어떤 걸 하고 싶나요~?”

47~83행: `switch` 문 – 선택에 따라 다른 행동

✅ case 1: 리스트에 값 추가

c

scanf("%d", &i);
j = insertNode(&ll, ll.size, i);
printList(&ll);

사용자가 넣고 싶은 숫자를 입력하면,

리스트 맨 뒤에 추가해주고,

현재 리스트를 출력해요~

✅ case 2: 가장 큰 값 맨 앞으로 이동

c

moveMaxToFront(&(ll.head));
printList(&ll);
removeAllItems(&ll);

문제의 핵심!

moveMaxToFront() 함수를 실행해서

가장 큰 값 노드를 앞으로 가져오고,

결과를 보여준 뒤 리스트를 정리해요~

✅ case 0: 종료할 때

c

removeAllItems(&ll);

깔끔하게 메모리를 정리하고 종료해요!

“마무리도 우아하게~”

⚠️ default: 잘못된 번호 입력 시

c

printf("Choice unknown;\n");

“없는 번호예요~ 다시 골라주세요~!”

🧾 89~91행: `moveMaxToFront()` 함수 틀

c

int moveMaxToFront(ListNode **ptrHead) {
    /* add your code here */
}

이제 여러분이 직접 구현해야 할 함수예요!

노드 자체를 앞으로 옮겨주는 알고리즘을 만들면 되는 거예요~

아직 비어있고, 우리는 곧 이걸 채워 넣을 거랍니다~ ✍️

🧾 이후 함수들: 도우미 함수들 (중복설명 생략)

printList()
findNode()
insertNode()
removeNode()
removeAllItems()

이 함수들은 이전 문제들과 거의 동일한 기본 도우미들이에요~

줄 보여주기, 삽입/삭제하기, 메모리 정리까지

하나하나 우리가 이미 잘 알고 있는 친구들이에요~ 😊

필요하면 함수 5종 포스팅을 보고 오세요!

✅ 중간 정리

구성	설명
`main()`	사용자 입력을 받아서 연결 리스트에 숫자를 넣거나, 최대값을 앞으로 옮기는 구조
`moveMaxToFront()`	우리가 직접 구현할 핵심 함수 (노드 이동)
도우미 함수들	리스트 출력, 삽입, 삭제, 탐색 등 기본 기능 담당

여기까지 잘 따라왔나요!?! 🎉

이제 moveMaxToFront() 함수가 멋지게 동작할 준비가 되었답니다.

한 줄씩 천천히 해설해볼게요~ 😊

✨ 구현 코드 한 줄 한 줄 해설

c

if (ptrHead == NULL || *ptrHead == NULL || (*ptrHead)->next == NULL)
    return 0;

“리스트가 비었거나, 노드가 하나밖에 없으면요~

굳이 옮길 게 없으니까 그냥 가만히 있어요~” 😊

c

ListNode *prevMax = NULL;
ListNode *maxNode = *ptrHead;
ListNode *prev = NULL;
ListNode *cur = *ptrHead;

prevMax: 가장 큰 값을 가진 노드의 바로 앞 친구maxNode: 가장 큰 값을 가진 노드prev: 지금 순회 중인 노드의 바로 앞 친구cur: 지금 보고 있는 노드

“각자 역할을 맡아서 순회하면서 비교해보는 거예요~”

c

while (cur != NULL) {
    if (cur->item > maxNode->item) {
        maxNode = cur;
        prevMax = prev;
    }
    prev = cur;
    cur = cur->next;
}

“이건요~ 리스트를 한 번만 훑으면서

누가 제일 큰 친구인지 찾는 과정이에요.

큰 값을 발견하면 maxNode를 바꾸고,

그 앞 친구(prevMax)도 같이 기억해둬요!”

c

if (maxNode != *ptrHead) {

“만약 제일 큰 값이 이미 맨 앞에 있었다면?

아무것도 안 해도 되죠~ 이 조건은 그걸 걸러주는 거예요!”

c

    prevMax->next = maxNode->next;

“가장 큰 값을 가진 노드를

지금 자리에서 쏙 빼주는 코드예요!

앞 친구가 이제 maxNode 다음 친구와 손을 잡게 되죠~”

c

    maxNode->next = *ptrHead;
    *ptrHead = maxNode;

“그리고 maxNode를 맨 앞으로 데려와요~

지금 head가 가리키는 애보다 더 큰 친구니까,

이제 이 친구가 대표(head)가 되는 거예요~ 👑”

c

return 0;

“정상적으로 잘 마무리됐다는 표시예요~”

✅ 정리 요약

포인트	설명
최대값 탐색	한 번만 리스트 순회
노드 이동	값 바꾸는 게 아니라, 노드 자체를 옮김
head 갱신	필요한 경우 head 직접 바꿈
안전 처리	리스트 비었거나 노드 1개면 변화 없음

‼️ 최종 완성본 코드: `moveMaxToFront()`

c

int moveMaxToFront(ListNode **ptrHead)
{
    // 리스트가 비었거나 노드가 하나뿐이면 굳이 안 움직여도 돼요
    if (ptrHead == NULL || *ptrHead == NULL || (*ptrHead)->next == NULL)
        return 0;

    ListNode *prevMax = NULL;        // 최대값 노드의 앞 노드
    ListNode *maxNode = *ptrHead;    // 현재까지 가장 큰 값을 가진 노드
    ListNode *prev = NULL;           // 현재 노드의 이전 노드
    ListNode *cur = *ptrHead;        // 현재 탐색 중인 노드

    // 리스트를 한 번 순회하면서 최대값 노드 찾기
    while (cur != NULL) {
        if (cur->item > maxNode->item) {
            maxNode = cur;
            prevMax = prev;
        }
        prev = cur;
        cur = cur->next;
    }

    // 만약 최대값 노드가 이미 맨 앞이면 굳이 옮길 필요 없어요
    if (maxNode != *ptrHead) {
        // 현재 위치에서 maxNode 제거
        prevMax->next = maxNode->next;

        // maxNode를 맨 앞으로 이동
        maxNode->next = *ptrHead;
        *ptrHead = maxNode;
    }

    return 0;
}

💛 선생님의 마무리 한마디

“이걸 완성한 금쪽이 여러분은

이제 진짜 연결 리스트를 자유자재로 다룰 수 있는 능력자예요!

정말 너무 잘했어요~

오늘도 한 번 더 안아주세요~ 🤗💛”

김쟇연

그래도 해야지 어떡해

이전 포스트

[ 자료구조 ] 야 쫄지마! Linked List 기본 함수 5종

3개의 댓글

이순간

2025년 4월 15일

정신과 한번 가보시겠어요?

1개의 답글