C언어로 단일 연결 리스트 구현하는 방법과 실습

단일 연결 리스트(Singly Linked List)는 데이터가 순차적으로 연결된 구조로, 각 노드가 다음 노드에 대한 포인터를 포함하는 자료구조입니다. 이 구조는 배열과 달리 동적 크기 조정을 지원하며, 데이터 삽입 및 삭제가 효율적입니다. 본 기사에서는 C 언어를 활용해 단일 연결 리스트를 구현하는 방법을 다루며, 초기화, 삽입, 삭제, 탐색 등 주요 작업을 자세히 설명합니다. 이러한 지식을 통해 데이터 구조에 대한 이해와 활용 능력을 높일 수 있습니다.

목차

단일 연결 리스트란 무엇인가


단일 연결 리스트(Singly Linked List)는 각 노드가 데이터를 저장하고 다음 노드에 대한 포인터를 포함하는 데이터 구조입니다.

주요 특징

  • 연결된 노드 구조: 각 노드는 데이터를 저장하는 필드와 다음 노드를 가리키는 포인터를 포함합니다.
  • 동적 크기 조정: 배열과 달리 크기가 고정되지 않아 동적 메모리 할당을 통해 필요에 따라 크기를 조정할 수 있습니다.
  • 빠른 삽입과 삭제: 특정 위치에서의 삽입과 삭제가 O(1)의 시간 복잡도로 가능합니다(포인터만 조정).

용도와 한계

  • 용도: 데이터 삽입 및 삭제가 빈번한 애플리케이션, 큐 및 스택 구현 등에 유용합니다.
  • 한계: 임의의 요소 접근이 비효율적이며, 특정 요소를 찾으려면 전체 리스트를 탐색해야 합니다.

단일 연결 리스트는 효율적이고 유연한 데이터 구조로, 다양한 소프트웨어 설계에서 기본적인 구성 요소로 사용됩니다.

단일 연결 리스트의 구조 정의

단일 연결 리스트를 구현하기 위해 각 노드의 구조를 정의하고, 노드를 연결할 포인터를 설정해야 합니다.

노드 구조체 정의


C 언어에서 단일 연결 리스트의 노드는 구조체로 정의됩니다. 각 노드는 데이터를 저장하는 필드와 다음 노드를 가리키는 포인터를 포함합니다.

// 단일 연결 리스트의 노드 구조체 정의
struct Node {
    int data;           // 데이터를 저장하는 필드
    struct Node* next;  // 다음 노드를 가리키는 포인터
};

리스트 헤드 정의


리스트를 관리하기 위해 리스트의 시작점을 가리키는 포인터를 별도로 선언합니다. 일반적으로 이 포인터는 head라는 이름으로 사용됩니다.

struct Node* head = NULL;  // 리스트의 시작점을 가리키는 포인터

구조 정의의 중요성


이 구조 정의를 통해 리스트의 각 노드가 연결되고, 삽입, 삭제, 탐색과 같은 모든 작업을 수행할 수 있는 기반이 됩니다. 이 구조체를 기반으로 노드의 동적 메모리 할당과 데이터 처리 작업이 이루어집니다.

단일 연결 리스트의 초기화

단일 연결 리스트를 사용하려면 먼저 리스트를 초기화해야 합니다. 초기화는 리스트의 시작 지점(헤드 포인터)을 정의하고, 메모리 할당을 관리하는 과정을 포함합니다.

리스트 초기화


초기 상태에서는 리스트가 비어 있으므로 head 포인터를 NULL로 설정합니다.

struct Node* head = NULL;  // 리스트가 비어 있음을 나타냄

새 노드의 동적 메모리 할당


새로운 노드를 추가하려면 malloc 함수를 사용해 동적으로 메모리를 할당합니다.

#include <stdlib.h>

// 새로운 노드 생성
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("메모리 할당 실패\n");
        exit(1);
    }
    newNode->data = value;  // 데이터 필드 설정
    newNode->next = NULL;   // 다음 노드 초기화
    return newNode;
}

초기화 과정의 요약

  1. head 포인터를 선언하고 NULL로 초기화합니다.
  2. 새로운 노드를 동적으로 할당하며 데이터 필드와 포인터 필드를 설정합니다.
  3. 할당한 노드를 리스트의 시작 지점이나 원하는 위치에 연결합니다.

이 과정을 통해 리스트가 비어 있을 때 새로운 데이터를 추가할 준비가 완료됩니다. 초기화는 리스트의 기반을 형성하며, 이후 삽입 및 삭제 작업을 수행할 수 있도록 합니다.

단일 연결 리스트에 데이터 삽입

단일 연결 리스트에 데이터를 삽입하는 작업은 노드를 특정 위치에 추가하는 과정을 포함합니다. 이는 리스트의 맨 앞, 중간, 또는 맨 끝에 삽입하는 경우로 나눌 수 있습니다.

리스트 맨 앞에 데이터 삽입


리스트의 맨 앞에 새 노드를 삽입하려면 새 노드의 next를 현재 head가 가리키는 노드로 설정한 후, head를 새 노드로 업데이트합니다.

void insertAtBeginning(struct Node** head, int value) {
    struct Node* newNode = createNode(value);
    newNode->next = *head;  // 새 노드의 next를 기존 head로 설정
    *head = newNode;        // head를 새 노드로 업데이트
}

리스트 중간에 데이터 삽입


특정 위치에 데이터를 삽입하려면 해당 위치 이전의 노드를 탐색한 후 새 노드를 연결합니다.

void insertAtPosition(struct Node* head, int position, int value) {
    struct Node* newNode = createNode(value);
    struct Node* temp = head;

    // 삽입 위치 이전의 노드까지 이동
    for (int i = 1; i < position - 1 && temp != NULL; i++) {
        temp = temp->next;
    }

    if (temp == NULL) {
        printf("잘못된 위치입니다.\n");
        return;
    }

    // 새 노드를 연결
    newNode->next = temp->next;
    temp->next = newNode;
}

리스트 맨 끝에 데이터 삽입


맨 끝에 데이터를 삽입하려면 리스트를 끝까지 탐색한 후 새 노드를 연결합니다.

void insertAtEnd(struct Node** head, int value) {
    struct Node* newNode = createNode(value);
    if (*head == NULL) {  // 리스트가 비어 있을 경우
        *head = newNode;
        return;
    }

    struct Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;  // 마지막 노드에 새 노드를 연결
}

삽입의 요약

  1. 새 노드를 생성하고 데이터를 저장합니다.
  2. 삽입 위치에 따라 next 포인터를 적절히 조정합니다.
  3. 리스트가 비어 있는 경우, head를 새 노드로 설정합니다.

데이터 삽입 작업은 리스트의 유연성을 극대화하며, 다양한 상황에서 효율적인 데이터 추가를 가능하게 합니다.

단일 연결 리스트에서 데이터 삭제

단일 연결 리스트에서 데이터 삭제는 특정 노드를 제거하고, 연결 관계를 재구성하는 작업을 포함합니다. 이는 리스트의 맨 앞, 중간, 또는 맨 끝에서 삭제하는 경우로 나눌 수 있습니다.

리스트 맨 앞의 노드 삭제


맨 앞의 노드를 삭제하려면 head 포인터를 다음 노드로 이동시키고, 제거할 노드의 메모리를 해제합니다.

void deleteAtBeginning(struct Node** head) {
    if (*head == NULL) {
        printf("리스트가 비어 있습니다.\n");
        return;
    }
    struct Node* temp = *head;  // 현재 head를 저장
    *head = (*head)->next;      // head를 다음 노드로 이동
    free(temp);                 // 이전 head 메모리 해제
}

리스트 중간의 노드 삭제


중간에 있는 특정 노드를 삭제하려면 해당 노드 이전 노드를 탐색하고, 삭제할 노드를 건너뛰도록 next 포인터를 조정합니다.

void deleteAtPosition(struct Node** head, int position) {
    if (*head == NULL) {
        printf("리스트가 비어 있습니다.\n");
        return;
    }

    struct Node* temp = *head;

    if (position == 1) {  // 첫 번째 노드를 삭제하는 경우
        *head = temp->next;
        free(temp);
        return;
    }

    // 삭제할 노드의 이전 노드까지 이동
    for (int i = 1; i < position - 1 && temp != NULL; i++) {
        temp = temp->next;
    }

    if (temp == NULL || temp->next == NULL) {
        printf("잘못된 위치입니다.\n");
        return;
    }

    struct Node* nodeToDelete = temp->next;
    temp->next = nodeToDelete->next;  // 삭제할 노드를 건너뛰도록 설정
    free(nodeToDelete);               // 삭제할 노드 메모리 해제
}

리스트 맨 끝의 노드 삭제


맨 끝의 노드를 삭제하려면 마지막 노드 이전의 노드를 탐색하여 next 포인터를 NULL로 설정하고, 마지막 노드를 해제합니다.

void deleteAtEnd(struct Node** head) {
    if (*head == NULL) {
        printf("리스트가 비어 있습니다.\n");
        return;
    }

    struct Node* temp = *head;

    if (temp->next == NULL) {  // 리스트에 노드가 하나만 있는 경우
        free(temp);
        *head = NULL;
        return;
    }

    // 마지막 노드 이전 노드까지 이동
    while (temp->next->next != NULL) {
        temp = temp->next;
    }

    free(temp->next);  // 마지막 노드 메모리 해제
    temp->next = NULL; // 이전 노드의 next를 NULL로 설정
}

삭제의 요약

  1. 삭제할 노드를 찾기 위해 리스트를 탐색합니다.
  2. 삭제할 노드의 이전 노드가 next 포인터를 적절히 연결하도록 설정합니다.
  3. 삭제된 노드의 메모리를 해제하여 메모리 누수를 방지합니다.

이 작업을 통해 리스트에서 효율적으로 데이터를 삭제하며, 리스트의 무결성을 유지할 수 있습니다.

단일 연결 리스트 순회와 검색

단일 연결 리스트에서 순회와 검색은 리스트의 데이터를 탐색하거나 특정 데이터를 찾기 위한 작업입니다. 이 과정은 노드를 하나씩 방문하며 수행됩니다.

리스트 순회


리스트 순회는 리스트의 모든 노드를 방문하며 데이터를 출력하거나 조작하는 과정을 포함합니다.

void traverseList(struct Node* head) {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);  // 현재 노드의 데이터 출력
        temp = temp->next;            // 다음 노드로 이동
    }
    printf("NULL\n");
}

특정 데이터 검색


리스트에서 특정 데이터를 검색하려면 각 노드를 방문하여 데이터 필드와 비교합니다.

struct Node* searchList(struct Node* head, int target) {
    struct Node* temp = head;
    while (temp != NULL) {
        if (temp->data == target) {  // 데이터가 목표값과 일치하는 경우
            return temp;             // 해당 노드의 포인터 반환
        }
        temp = temp->next;           // 다음 노드로 이동
    }
    return NULL;                     // 목표값이 없으면 NULL 반환
}

검색 결과 출력


검색 작업 후, 반환된 노드를 이용해 결과를 출력할 수 있습니다.

void printSearchResult(struct Node* result, int target) {
    if (result != NULL) {
        printf("값 %d를 가진 노드가 발견되었습니다.\n", target);
    } else {
        printf("값 %d를 가진 노드가 리스트에 없습니다.\n", target);
    }
}

순회와 검색의 요약

  1. 순회: 노드를 순서대로 방문하며 데이터를 출력하거나 조작합니다.
  2. 검색: 리스트에서 특정 값을 찾고, 해당 값을 가진 노드를 반환합니다.
  3. 효율성: 단일 연결 리스트의 순회 및 검색은 O(n)의 시간 복잡도를 가집니다.

이 작업은 리스트에서 데이터를 효과적으로 확인하고 처리할 수 있는 기본적인 도구입니다.

단일 연결 리스트 메모리 해제

단일 연결 리스트에서 사용된 메모리를 해제하지 않으면 메모리 누수가 발생할 수 있습니다. 따라서 프로그램 종료 전에 모든 노드를 안전하게 삭제해야 합니다.

전체 리스트 메모리 해제


리스트의 모든 노드를 삭제하려면 리스트를 순회하며 각 노드의 메모리를 해제합니다.

void freeList(struct Node** head) {
    struct Node* temp;
    while (*head != NULL) {
        temp = *head;        // 현재 노드를 임시 저장
        *head = (*head)->next;  // head를 다음 노드로 이동
        free(temp);          // 현재 노드의 메모리 해제
    }
    printf("리스트의 메모리가 모두 해제되었습니다.\n");
}

노드 삭제 시 주의사항

  • 연결 끊김 방지: 노드를 삭제하기 전에 다음 노드로의 연결을 유지해야 합니다.
  • 헤드 포인터 초기화: 모든 노드가 삭제된 후, head 포인터를 NULL로 설정하여 빈 리스트임을 나타냅니다.
  • 메모리 누수 방지: free 함수로 메모리를 해제하지 않으면 프로그램 종료 후에도 사용되지 않는 메모리가 시스템에 남아 있게 됩니다.

메모리 해제의 확인


모든 노드가 삭제된 후, 리스트가 비어 있는지 확인하는 간단한 검증을 추가할 수 있습니다.

if (head == NULL) {
    printf("리스트가 비어 있습니다.\n");
} else {
    printf("리스트가 여전히 데이터로 채워져 있습니다.\n");
}

메모리 해제의 요약

  1. 리스트의 각 노드를 순회하며 메모리를 해제합니다.
  2. 마지막 노드를 해제한 후, head 포인터를 NULL로 초기화합니다.
  3. 메모리 누수를 방지하여 프로그램의 안정성을 높입니다.

이 작업은 프로그램 종료 전 필수적으로 수행해야 하며, 동적 메모리를 사용하는 C 프로그램에서 기본적인 책임 중 하나입니다.

단일 연결 리스트 연습 문제

단일 연결 리스트의 개념과 구현을 강화하기 위해 다음과 같은 연습 문제를 제시합니다. 이 문제들은 리스트의 다양한 기능과 활용을 실습하는 데 도움이 됩니다.

문제 1: 리스트 회전


주어진 단일 연결 리스트를 k개의 노드를 기준으로 오른쪽으로 회전시키는 함수를 구현하세요.

예시

  • 입력 리스트: 1 → 2 → 3 → 4 → 5
  • k = 2
  • 결과: 4 → 5 → 1 → 2 → 3

힌트

  1. 리스트의 길이를 계산합니다.
  2. k를 리스트 길이로 나눈 나머지를 사용합니다.
  3. k번째 노드에서 리스트를 분리하고 다시 연결합니다.

문제 2: 리스트 역순 출력


단일 연결 리스트를 역순으로 출력하는 함수를 구현하세요.

제약 조건

  • 리스트를 역순으로 출력하되, 원래 리스트의 순서를 변경하지 마세요.

힌트

  1. 재귀 함수나 스택 자료구조를 활용할 수 있습니다.
  2. 재귀 함수에서 가장 깊은 노드까지 탐색한 후 데이터를 출력합니다.

문제 3: 중복 제거


정렬되지 않은 단일 연결 리스트에서 중복된 데이터를 제거하는 함수를 구현하세요.

예시

  • 입력 리스트: 1 → 2 → 2 → 3 → 4 → 4 → 5
  • 결과: 1 → 2 → 3 → 4 → 5

힌트

  1. 중복 확인을 위해 해시 테이블을 사용할 수 있습니다.
  2. 포인터를 활용하여 중복된 노드를 건너뛰고 삭제합니다.

문제 4: 리스트 중간 노드 찾기


단일 연결 리스트의 중간 노드를 찾는 함수를 구현하세요.

예시

  • 입력 리스트: 1 → 2 → 3 → 4 → 5
  • 결과: 3

힌트

  1. 두 개의 포인터를 사용합니다(빠른 포인터와 느린 포인터).
  2. 빠른 포인터가 리스트 끝에 도달하면 느린 포인터는 중간 노드를 가리킵니다.

문제 5: 리스트 합병


두 개의 정렬된 단일 연결 리스트를 합병하여 새로운 정렬된 리스트를 생성하는 함수를 구현하세요.

예시

  • 입력 리스트 1: 1 → 3 → 5
  • 입력 리스트 2: 2 → 4 → 6
  • 결과: 1 → 2 → 3 → 4 → 5 → 6

힌트

  1. 두 리스트를 병합하는 동안 데이터를 비교하여 작은 값을 먼저 추가합니다.
  2. 하나의 리스트가 끝나면 나머지 리스트를 연결합니다.

연습 문제 요약


이 문제들은 단일 연결 리스트의 다양한 동작 원리를 실습하고, 실전에서 적용할 수 있는 능력을 기르는 데 도움이 됩니다. 코드 작성 후 디버깅을 통해 개념을 확실히 이해하세요.

요약

본 기사에서는 C 언어로 단일 연결 리스트를 구현하는 방법을 다루었습니다. 리스트의 정의와 초기화, 데이터 삽입 및 삭제, 순회와 검색, 메모리 관리 방법을 상세히 설명했으며, 이를 응용할 수 있는 연습 문제를 제시하였습니다. 단일 연결 리스트는 동적 데이터 구조의 기본으로, 본 기사를 통해 기초부터 실전 응용까지 익힐 수 있습니다. 이를 통해 데이터 구조와 알고리즘 설계 능력을 향상시킬 수 있을 것입니다.

목차