[C언어] 연결 리스트(Linked List) 구현 실습하기

연결 리스트(Linked List) 구현 실습하기

처음 문제를 보면 연결 리스트의 노드 구조체와 기본 함수들(삽입, 삭제, 출력 등)은 이미 구현되어 있고, 각 문제마다 특정 함수만 직접 작성하도록 되어 있습니다. 즉, 우리가 연결 리스트의 기본 개념을 알고 있다고 가정한 채 문제가 주어지는 것이죠.

 

그래서 당장 연결 리스트 문제를 풀고 싶지만 뭐가 뭔지 몰라서 답답하고 막막하다면, 아래의 실습 과정을 통해 먼저 연결 리스트와 포인터에 대한 기초적인 이해를 쌓은 후 문제에 접근하는 방법을 추천합니다.

 

물론 아무것도 없는 상태에서 연결 리스트에 어떤 구조체가 필요하고, 어떤 매개 변수를 받는 함수가 필요한지 정의해보면 정말 좋겠지만, 굉장히 힘들 것 같습니다.

 

그래서 먼저 필요한 구조체, 함수에 대해 최소한의 기본적인 형태를 받아 놓고 그것들을 직접 채워나가면서 '연결 리스트가 C언어에서 이렇게 작동하고 구현되는구나! 그리고 그 작동 과정에서 포인터가 이렇게 쓰이는구나!' 하는 시간을 가져 보면 좋지 않을까 싶습니다.

 

이 과정을 통해 이 글을 읽는 모든 분들이 저처럼 포인터와 동적 메모리의 핵심 개념을 체감하고, 연결 리스트 구현에 대한 자신감을 갖게 되면서 이 실습이 또 하나의 성장의 발판이 되어줄 수 있으리라 생각합니다.

 

 

필요한 구조체, 함수 정의하기

구조체

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

함수 (추천 구현 순서)

• ListNode *findNode(LinkedList *ll, int index): 연결 리스트에서 index에 해당하는 노드의 주소를 찾아 반환
• int insertNode(LinkedList *ll, int index, int value): index 위치에 새 노드를 삽입
• int removeNode(LinkedList *ll, int index): index 위치의 노드를 삭제
• void printList(LinkedList *ll): 연결 리스트의 모든 노드 값을 순서대로 출력
• void removeAllItems(LinkedList *ll): 연결 리스트의 모든 노드를 제거하고 초기화

 

전체 실습 코드

연결 리스트를 구현 실습용 뼈대 코드입니다. 각 함수에는 간단한 힌트가 주석으로 포함되어 있어, 스스로 고민하며 구현해볼 수 있게끔 되어 있습니다. 칠판이나 노트에 그림을 그려 보면서 기본 함수들을 하나씩 구현해 보세요.

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

// 연결 리스트 구조체
typedef struct _listnode{
	int item;
	struct _listnode *next;
} ListNode;
// 노드 구조체
typedef struct _linkedlist{
	int size;
	ListNode *head;
} LinkedList;

// 기본 함수 선언
ListNode *findNode(LinkedList *ll, int index);
int insertNode(LinkedList *ll, int index, int value);
int removeNode(LinkedList *ll, int index);
void printList(LinkedList *ll);
void removeAllItems(LinkedList *ll);

// 연결 리스트 기본 함수 확인용 프로그램
// 함수 구현 후 C파일을 실행해 제대로 동작하는지 테스트해볼 수 있습니다.
int main() {
    LinkedList ll;
    int c = 1;
    int index, value;
    ListNode *node;

    // 초기화
    ll.head = NULL;
    ll.size = 0;

    printf("===== 연결 리스트 테스트 메뉴 =====\n");
    printf("1: insertNode(index, value)\n");
    printf("2: removeNode(index)\n");
    printf("3: findNode(index)\n");
    printf("4: printList()\n");
    printf("5: removeAllItems()\n");
    printf("0: 종료\n");

    while (c != 0) {
        printf("\n메뉴 선택 (0~5): ");
        scanf("%d", &c);

        switch (c) {
        case 1:
            printf("삽입할 인덱스를 입력하세요: ");
            scanf("%d", &index);
            printf("삽입할 값을 입력하세요: ");
            scanf("%d", &value);
            if (insertNode(&ll, index, value) == 0)
                printf("삽입 성공!\n");
            else
                printf("삽입 실패 (인덱스 오류)!\n");
            break;

        case 2:
            printf("삭제할 인덱스를 입력하세요: ");
            scanf("%d", &index);
            if (removeNode(&ll, index) == 0)
                printf("삭제 성공!\n");
            else
                printf("삭제 실패 (인덱스 오류)!\n");
            break;

        case 3:
            printf("찾을 인덱스를 입력하세요: ");
            scanf("%d", &index);
            node = findNode(&ll, index);
            if (node != NULL)
                printf("해당 노드의 값: %d\n", node->item);
            else
                printf("노드를 찾을 수 없습니다 (인덱스 오류)!\n");
            break;

        case 4:
            printf("현재 연결 리스트: ");
            printList(&ll);
            break;

        case 5:
            removeAllItems(&ll);
            printf("모든 노드 삭제 완료!\n");
            break;

        case 0:
            removeAllItems(&ll);
            printf("프로그램 종료.\n");
            break;

        default:
            printf("알 수 없는 선택입니다.\n");
            break;
        }
    }

    return 0;
}

// index에 해당하는 노드의 주소를 반환하는 함수
// 노드를 찾았다면 해당 노드, 노드를 찾을 수 없다면 NULL 반환
ListNode *findNode(LinkedList *ll, int index)
{
    /*  index가 유효하지 않다면 어떻게 처리해야 할까요?
        노드를 어떻게 찾아가면 좋을까요?
        add your code here  */
}

// index 위치에 새로운 노드를 삽입하는 함수
// 성공 시 0, 실패 시 -1 반환
int insertNode(LinkedList *ll, int index, int value)
{
    /*  삽입할 위치가 head일 때와 아닐 때, 무엇이 다를까요?
        이전 노드를 찾을 땐 어떤 함수가 도움될까요?
        add your code here  */
}

// index 위치의 노드를 삭제하는 함수
// 성공 시 0, 실패 시 -1 반환
int removeNode(LinkedList *ll, int index)
{
    /*  삭제할 노드가 head일 때와 아닐 때 어떻게 나눠서 처리할 수 있을까요?
        연결을 바꾸고 나면 어떤 자원을 정리해야 할까요?
        add your code here  */
}

// 연결 리스트의 모든 노드를 순서대로 출력하는 함수
void printList(LinkedList *ll)
{
    /*  리스트가 비어 있다면 어떻게 출력할까요?
        순서대로 출력하려면 어떤 구조를 반복해야 할까요?
        add your code here  */
}

// 연결 리스트의 모든 노드를 제거하고 초기화하는 함수
void removeAllItems(LinkedList *ll)
{
    /*  모든 노드를 제거하려면 어떤 방식으로 순회해야 할까요?
        제거 후 리스트의 어떤 속성도 함께 갱신해야 할까요?
        add your code here  */
}

 

 

연결 리스트 구현하기

함수마다 주어진 매개변수(parameter)를 바탕으로, 해당 함수가 어떤 기능을 수행해야 하는지 먼저 논리적으로 생각해보고, 그 후에 실제로 직접 구현해봅니다.

 

각 함수는 어떤 기본 동작 흐름을 따르는지, 어떤 포인터 변수를 새로 만들어야 할지, 그리고 예외 상황(리스트가 비어 있는 경우나, 주어진 인덱스가 유효하지 않은 경우)에는 어떻게 대응해야 할지도 함께 고민해보면 더 좋습니다.

 

findNode 함수

index에 해당하는 노드의 주소를 반환하는 함수

• *ll: (pointer) 연결 리스트 주소
• index: (int) 찾을 노드의 인덱스

findNode 구현하기

// index에 해당하는 노드의 주소를 반환하는 함수
// 노드를 찾았다면 해당 노드, 노드를 찾을 수 없다면 NULL 반환
ListNode *findNode(LinkedList *ll, int index)
{
    // 리스트가 비었거나 인덱스가 범위를 벗어나는 경우 실패 처리
    if (ll == NULL || ll->head == NULL || index < 0 || index >= ll->size)
        return NULL;

    // head부터 시작해서 index번째 노드까지 이동
    ListNode *cur = ll->head;
    int i = 0;
    while (i < index) {
        cur = cur->next;
        i++;
    }

    // index 위치의 노드 주소 반환
    return cur;
}

 

insertNode 함수

index 위치에 새로운 노드를 삽입하는 함수

• *ll: (pointer) 연결 리스트 주소
• index: (int) 삽입할 노드의 인덱스
• value: (int) 삽입할 노드의 값(item)

insertNode 구현하기

// index 위치에 새로운 노드를 삽입하는 함수
// 삽입 성공 시 0, 실패 시 -1 반환
int insertNode(LinkedList *ll, int index, int value)
{
    // 유효하지 않은 인덱스는 실패 처리
    if (index < 0 || index > ll->size) return -1;

    // 새 노드 생성 및 초기화
    ListNode *pre;
    ListNode *new_node = malloc(sizeof(ListNode));
    new_node->item = value;
    new_node->next = NULL;

    if (index == 0) {
    	// 맨 앞에 삽입하는 경우
        new_node->next = ll->head;
        ll->head = new_node;
    } else {
    	// 중간 또는 끝에 삽입하는 경우
        pre = findNode(ll, index - 1);
        new_node->next = pre->next;
        pre->next = new_node;
    }

    // 리스트 크기 증가
    ll->size++;
    return 0;
}

 

removeNode 함수

index 위치의 노드를 삭제하는 함수

• *ll: (pointer) 연결 리스트 주소
• index: (int) 찾을 노드의 인덱스

removeNode 구현하기

// index 위치의 노드를 삭제하는 함수
// 성공 시 0, 실패 시 -1 반환
int removeNode(LinkedList *ll, int index)
{
    // 리스트가 비었거나 인덱스가 범위를 벗어나는 경우 실패 처리
    if (ll == NULL || ll->head == NULL || index < 0 || index >= ll->size)
        return -1;

    ListNode *pre, *cur;

    if (index == 0) {
        // 첫 번째 노드 삭제
        cur = ll->head;
        ll->head = cur->next;
        free(cur);
    } else {
        // 중간 또는 마지막 노드 삭제
        pre = findNode(ll, index - 1);
        cur = pre->next;
        pre->next = cur->next;
        free(cur);
    }

    // 리스트 크기 감소
    ll->size--;
    return 0;
}

 

 

printList 함수

연결 리스트의 모든 노드 값을 순서대로 출력하는 함수

• *ll: (pointer) 연결 리스트 주소

printList 구현하기

// 연결 리스트의 모든 노드 값을 순서대로 출력하는 함수
void printList(LinkedList *ll)
{
    ListNode *cur;

    printf("현재 연결 리스트: ");
    
    // 리스트가 비어 있는 경우
    if (ll == NULL || ll->head == NULL) {
        printf("Empty\n");
    } else {
        // 리스트를 순회하며 값 출력
        cur = ll->head;
        while (cur != NULL) {
            printf("%d ", cur->item);
            cur = cur->next;
        }
        printf("\n"); // 마지막 줄바꿈
    }
}

 

removeAllItems 함수

연결 리스트의 모든 노드를 제거하고 초기화하는 함수

• *ll: (pointer) 연결 리스트 주소

removeAllItems 구현하기

void removeAllItems(LinkedList *ll)
{
    // 빈 리스트인 경우
    if (ll == NULL || ll->head == NULL) {
        printf("이미 빈 리스트입니다.\n");
        return;
    }

    ListNode *cur;

    // head가 NULL이 될 때까지 노드를 차례로 제거
    while (ll->head != NULL) {
        cur = ll->head;           // 현재 노드 포인터 저장
        ll->head = cur->next;     // head를 다음 노드로 이동
        free(cur);                // 현재 노드 메모리 해제
        ll->size--;               // 리스트 크기 감소
    }
    printf("리스트 초기화 완료\n");
}