[ 자료구조 ] Front Back Split Linked List

김쟇연·2025년 4월 14일
Cc언어linkedlistsplitlinkedlist노드탐색리스트반갈죽리스트분할연결리스트자료구조포인터홀수처리

Data Structures

목록 보기
4/6
post-thumbnail

자 그럼 이번에는 5번 문제를

금쪽이를 위해 쉽게 설명해볼게요 ~ 😉

Q5_A_LL (frontBackSplitLL)

"리스트를 반으로 나눠볼까요?"

5. (frontBackSplitLL)  Write  a  C  function  frontBackSplitLL()  that  splits  the  singly 
linked list into two sublists – one for the front half, and one for the back half. If the number 
of  elements  is  odd,  the  extra  element  should  go  into  the  front  list.  The 
frontBackSplitLL() prints two lists which contains frontList and backList. 
 
The function prototypes are given as follows: 
void frontBackSplitLL(LinkedList *ll, LinkedList 
*resultFrontList, LinkedList *resultBackList); 
 
For example, assume that given linked list is: 2,  3,  5,  6,  7 
 
The resulting Linked Lists, frontList and backList are: 
frontList: 2,  3,  5 
backList:  6, 7 
 
A sample input and output session is given below: 
1: Insert an integer to the linked list: 
2: Print the linked list: 
3: Split the linked list into two linked lists, frontList and backList: 
0: Quit: 
 
Please input your choice(1/2/3/0): 1 
Input an integer that you want to add to the linked list: 2 
The resulting linked list is: 2 
 
Please input your choice(1/2/3/0): 1 
Input an integer that you want to add to the linked list: 3 
The resulting linked list is: 2 3 
 
Please input your choice(1/2/3/0): 1 
Input an integer that you want to add to the linked list: 5 
The resulting linked list is: 2 3 5 
 
Please input your choice(1/2/3/0): 1 
Input an integer that you want to add to the linked list: 6 
The resulting linked list is: 2 3 5 6 
 
Please input your choice(1/2/3/0): 1 
Input an integer that you want to add to the linked list: 7 
The resulting linked list is: 2 3 5 6 7 
 
Please input your choice(1/2/3/0): 2 
The resulting linked list is: 2 3 5 6 7 
 
Please input your choice(1/2/3/0): 3 
The resulting linked lists after splitting the given linked list are: 
Front linked list: 2 3 5 
Back linked list: 6 7

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

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

그걸 앞 리스트(frontList)와 뒤 리스트(backList)로 반반 나누는 함수예요!

📌 조건이 있어요!

조건설명
반으로 나눌 때홀수 개라면 앞 리스트가 하나 더 가져요! 🙆‍♀️
순서는반드시 그대로 유지해야 해요!
출력은두 리스트를 나눠서 각각 출력해줘요

👩‍🏫 예시로 볼까요?

예를 들어서…


입력된 리스트: 2 → 3 → 5 → 6 → 7

이 리스트는 총 5개예요.

홀수니까 👉 앞쪽 리스트가 3개, 뒤쪽은 2개가 되어야겠죠?

yaml

Front list: 2 → 3 → 5
Back list: 6 → 7

📚 메뉴 흐름도 이렇게 돼요!

makefile

1: 리스트에 숫자 넣기
2: 현재 리스트 보여주기
3: 리스트 반으로 나누기
0: 종료

예를 들어…

bash

입력: 2 3 5 6 7
→ split 실행 시:
앞 리스트: 2 3 5
뒤 리스트: 6 7

💡 이 문제, 왜 중요한가요?

"아이들 줄 세울 때도

균형을 맞춰야 하잖아요~?"

✔️ 데이터의 일부를 나누고 복사하거나

✔️ 병렬 작업을 나눌 때

✔️ 앞쪽만 우선 처리할 때 등등

이런 경우에 리스트를 반으로 쪼개는 로직이 꼭 필요해요!

✏️ 요약 정리

항목내용
함수 이름frontBackSplitLL()
매개변수원래 리스트, 앞 리스트, 뒤 리스트 포인터
주요 기능리스트를 앞뒤로 반 나누기 (홀수면 앞이 하나 더)
순서 유지✅ 필수!
리턴값❌ 없음 (두 리스트를 직접 수정해서 결과 저장)

code

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

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

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

#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
void frontBackSplitLinkedList(LinkedList* ll, LinkedList *resultFrontList, LinkedList *resultBackList);

void printList(LinkedList *ll);
void removeAllItems(LinkedList *l);
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;
	LinkedList ll;
	LinkedList resultFrontList, resultBackList;

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

	//Initialize the front linked list as an empty linked list
	resultFrontList.head = NULL;
	resultFrontList.size = 0;

	// Initialize the back linked list as an empty linked list
	resultBackList.head = NULL;
	resultBackList.size = 0;

	printf("1: Insert an integer to the linked list:\n");
	printf("2: Split the linked list into two linked lists, frontList and backList:\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);
			insertNode(&ll, ll.size, i);
			printf("The resulting linked list is: ");
			printList(&ll);
			break;
		case 2:
			printf("The resulting linked lists after splitting the given linked list are:\n");
			frontBackSplitLinkedList(&ll, &resultFrontList, &resultBackList); // You need to code this function
			printf("Front linked list: ");
			printList(&resultFrontList);
			printf("Back linked list: ");
			printList(&resultBackList);
			printf("\n");
			removeAllItems(&ll);
			removeAllItems(&resultFrontList);
			removeAllItems(&resultBackList);
			break;
		case 0:
			removeAllItems(&ll);
			removeAllItems(&resultFrontList);
			removeAllItems(&resultBackList);
			break;
		default:
			printf("Choice unknown;\n");
			break;
		}
	}

	return 0;
}

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

void frontBackSplitLinkedList(LinkedList *ll, LinkedList *resultFrontList, LinkedList *resultBackList)
{
	/* 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");
}

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

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

“우리 금쪽이가 코딩을 처음 배운다고 생각하고,

이해하고 스스로 다룰 수 있도록 도와주는 거예요~

똑같은 부분이 반복될 땐, ‘이건 우리 이미 잘 알고 있어요~’ 하고 넘어가도 괜찮아요~”

🩷 쉬운 설명 시작!

📌 1~6행: 주석 (파일 소개)

c

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

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

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

“이 코드는 자료구조 과제 5번 문제에 대한 코드예요~

파일 이름은 Q5_A_LL.c, 연결 리스트를 반으로 나누는 문제랍니다~”

📌 8~9행: 필요한 도구들 포함

c

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

stdio.h는 입출력,

stdlib.h는 동적 메모리 할당(malloc, free)에 필요해요.

“도구 없인 집 못 짓잖아요~ 필요한 연장 챙기기!”

📌 11~14행: ListNode 구조체 선언

c

typedef struct _listnode{
	int item;
	struct _listnode *next;
} ListNode;

“하나하나의 노드 구조예요~

숫자 하나 들고 있고, 다음 친구를 가리키는 손가락도 갖고 있어요~”

(이전 문제에서도 이미 배웠던 구조죠~)

📌 16~19행: LinkedList 구조체 선언

c

typedef struct _linkedlist{
	int size;
	ListNode *head;
} LinkedList;

연결 리스트 전체를 다루는 구조예요~

  • head: 맨 앞 노드
  • size: 노드의 개수

(이 구조도 이전 문제에서 이미 나왔어요~ 친숙하죠? 😊)

📌 22~28행: 함수 선언부

c

void frontBackSplitLinkedList(LinkedList* ll, LinkedList *resultFrontList, LinkedList *resultBackList);

바로 금쪽이가 구현해야 할 핵심 함수예요!

한 개의 리스트를 두 개로 반반 나누는 함수랍니다!

결과는 resultFrontList와 resultBackList에 저장돼요~

(이건 구현은 아직 건들지 않아요~)

나머지 함수들:

c

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

이 함수들은 이전 문제들에서도 반복되어 사용된 함수들이에요.

우리가 잘 알고 있는 익숙한 도우미 함수들이죠~ 🛠️

(뒤에서 정의되어 있고, 설명은 간단히 넘어갈게요~)

📌 31~87행: main() 함수

c

int main()

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

여기에 사용자의 선택에 따라 다양한 작업을 하게 되죠.

🔹 33~35행: 변수 선언

c

int c, i;
LinkedList ll;
LinkedList resultFrontList, resultBackList;

c: 사용자 선택값i: 입력받을 숫자ll: 원래 연결 리스트resultFrontList, resultBackList: 결과 저장용 리스트

🔹 37~43행: 리스트 초기화

c

ll.head = NULL;
ll.size = 0;
resultFrontList.head = NULL;
resultFrontList.size = 0;
resultBackList.head = NULL;
resultBackList.size = 0;

세 개의 리스트를 모두 비어있는 상태로 초기화하는 코드예요!

“아직 아무도 들어오지 않았어요~ 깨끗한 상태랍니다!”

🔹 45~47행: 메뉴 출력

c

printf("1: Insert an integer to the linked list:\n");
printf("2: Split the linked list into two linked lists, frontList and backList:\n");
printf("0: Quit:\n");

사용자에게 어떤 행동을 할지 선택하라고 알려주는 안내 메시지예요~

“무엇을 하고 싶은지 고를 수 있어요~ 😊”

🔹 49행: 사용자 선택 반복

c

while (c != 0)

사용자가 0번(종료)을 선택할 때까지 계속 반복하는 구조예요~

“그만하겠다고 할 때까지 계속 함께 해요~!”

🔹 51행: 선택 입력 받기

c

scanf("%d", &c);

사용자의 선택을 받아요!

“1번? 2번? 0번? 골라보세요~”

🔹 53~81행: switch 문으로 동작 분기

✅ case 1: 숫자 삽입

c

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

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

리스트 맨 뒤에 추가해주고, 결과를 보여줘요~

“잘 들어갔는지 확인까지 해주는 배려~”

✅ case 2: 리스트 분리

c

frontBackSplitLinkedList(&ll, &resultFrontList, &resultBackList);

바로 금쪽이가 구현할 함수가 여기에서 실행돼요!

원래 리스트 ll을 반으로 나눠서

앞 절반은 resultFrontList,

뒤 절반은 resultBackList에 담아요!

c

printList(&resultFrontList);
printList(&resultBackList);
removeAllItems(&ll);
removeAllItems(&resultFrontList);
removeAllItems(&resultBackList);

결과 리스트들을 출력한 다음,

메모리도 깔끔하게 정리! 🧹

✅ case 0: 종료 시 정리

c

removeAllItems(&ll);
removeAllItems(&resultFrontList);
removeAllItems(&resultBackList);

프로그램 종료 전에도,

남은 리스트를 모두 free 해주는 깔끔한 마무리~

⚠️ default

c

printf("Choice unknown;\n");

잘못된 메뉴 선택 시 안내해줘요~

“없는 번호예요~ 다시 골라봐요~ ☺️”

📌 89~91행: 여러분이 구현할 핵심 함수

c

void frontBackSplitLinkedList(LinkedList *ll, LinkedList *resultFrontList, LinkedList *resultBackList)
{
    /* add your code here */
}

자, 이 빈 공간이 바로

우리가 직접 구현할 로직이 들어갈 자리!

원래 리스트를 반으로 나누어,

앞/뒤 리스트에 잘 담아주는 알고리즘을 작성할 거예요~

아직 건드리지 않을게요~ 다음 단계에서 본격적으로 들어가요! 💻

📌 이후 함수들 (printList, removeAllItems, findNode, insertNode, removeNode)

이 함수들은 앞선 문제들에서 이미 상세하게 다룬 함수들이에요!

  • printList: 리스트의 아이템 출력
  • removeAllItems: 전체 노드 메모리 해제
  • findNode: 인덱스로 노드 찾기
  • insertNode: 원하는 위치에 새 노드 삽입
  • removeNode: 인덱스 위치의 노드 삭제

이미 친숙한 도우미들이니까,

필요할 때 다시 찾아보면 돼요~

✅ 마무리 정리

항목설명
핵심 구현 대상frontBackSplitLinkedList() 함수
현재 하는 일전체 기본 틀 구조 이해, 입력/출력 흐름 파악
다음 단계리스트를 반으로 나누는 코드 직접 구현하기!

💛 선생님의 말씀

“지금까지 너무 잘했어요~

리스트를 반으로 나눈다는 건 단순한 분리가 아니라,

질서를 지키고 순서를 존중하는 코딩의 미덕이에요~

자, 다음은 진짜 구현 단계예요~

떨지 말고, 천천히 선생님이랑 같이 가보면 돼요~

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

드디어! 🎉

우리가 직접 구현해야 하는 함수의 코드를 한 줄 한 줄 완성해봅시다~ 😊

💻 구현 코드 한 줄씩 해설

c

if (ll == NULL || ll->size == 0) return;

리스트가 비었거나 아예 존재하지 않으면,

"할 일이 없어요~ 그냥 나가도 괜찮아요~" 😊

c

int mid = (ll->size + 1) / 2;

전체 리스트 길이를 반으로 나누되,

홀수일 경우에는 앞쪽이 하나 더 많도록 만들어줘요!

예: 5개면 앞이 3, 뒤가 2

c

ListNode *cur = ll->head;

리스트를 따라갈 "현재 손가락(cur)"을 앞에서부터 시작해요~

"차근차근 줄 세워서 넣어줄게요~"

c

for (int i = 0; i < mid; i++) {
    insertNode(resultFrontList, resultFrontList->size, cur->item);
    cur = cur->next;
}

앞쪽 리스트에 먼저 mid개 만큼 순서대로 넣어요!

매번 리스트의 끝(resultFrontList->size)에 삽입해요.

"앞 리스트에 먼저 채워주자~ 고루고루~" 🍞

c

while (cur != NULL) {
    insertNode(resultBackList, resultBackList->size, cur->item);
    cur = cur->next;
}

남은 노드들은 전부 뒤 리스트에 넣어요!

"남은 친구들, 뒤쪽으로 천천히 가서 앉아요~" 😌

✅ 최종 완성본

c

void frontBackSplitLinkedList(LinkedList *ll, LinkedList *resultFrontList, LinkedList *resultBackList)
{
	if (ll == NULL || ll->size == 0) return;

	int mid = (ll->size + 1) / 2;  // front 리스트가 하나 더 많게
	ListNode *cur = ll->head;

	for (int i = 0; i < mid; i++) {
	    insertNode(resultFrontList, resultFrontList->size, cur->item);
	    cur = cur->next;
	}

	while (cur != NULL) {
	    insertNode(resultBackList, resultBackList->size, cur->item);
	    cur = cur->next;
	}
}

💛 선생님의 마지막 한 마디

“이 함수는요~

공평하게 나누되, 앞에 있는 친구를 조금 더 배려해주는 구조예요.

질서도 지키고, 순서도 지키고,

리스트를 안전하게 반반 나누는 거~

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

profile
김쟇연
그래도 해야지 어떡해
이전 포스트

[ 자료구조 ] Move Odd Items To Back Linked List

다음 포스트

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

0개의 댓글