MENU
  1. ホーム
  2. C 언어
  3. C 언어로 링크드 리스트 기반 큐 구현하기: 개념과 코드

C 언어로 링크드 리스트 기반 큐 구현하기: 개념과 코드

C 언어

링크드 리스트는 노드의 동적 연결로 데이터를 저장하는 데이터 구조로, 큐를 구현하는 데 매우 적합합니다. 큐는 FIFO(First In, First Out) 원칙을 따르는 자료구조로, 데이터의 삽입과 삭제가 각각 다른 끝에서 이루어집니다. 본 기사에서는 C 언어를 사용해 링크드 리스트로 큐를 구현하는 방법과 이를 활용한 실용적인 사례를 살펴봅니다. 이 과정을 통해 자료구조의 기본 원리부터 실용적인 코드 작성 방법까지 익힐 수 있습니다.

목차

큐와 링크드 리스트의 기본 개념


큐(Queue)는 데이터가 먼저 들어온 순서대로 처리되는 FIFO(First In, First Out) 구조의 자료구조입니다. 데이터를 삽입하는 작업은 rear(후미)에서 이루어지고, 데이터를 제거하는 작업은 front(전면)에서 이루어집니다.

큐의 특징

  • 삽입(Enqueue): 새로운 데이터를 큐의 끝(rear)에 추가합니다.
  • 삭제(Dequeue): 큐의 앞(front)에서 데이터를 제거합니다.
  • 큐는 비어 있을 때 더 이상 삭제할 수 없고, 가득 찬 상태에서는 삽입이 불가능합니다.

링크드 리스트의 특징


링크드 리스트(Linked List)는 각 노드가 데이터를 저장하고 다음 노드를 가리키는 포인터를 포함하는 자료구조입니다.

  • 동적 크기: 배열과 달리, 메모리 크기가 고정되지 않아 데이터 추가 및 삭제가 자유롭습니다.
  • 노드 구조: 각 노드는 두 부분으로 구성됩니다. 하나는 데이터를 저장하고, 다른 하나는 다음 노드의 주소를 저장합니다.

큐와 링크드 리스트의 조합


링크드 리스트를 이용해 큐를 구현하면 다음과 같은 장점이 있습니다.

  • 메모리 활용성: 배열 기반 큐와 달리, 링크드 리스트 기반 큐는 크기에 제한이 없습니다.
  • 유연성: 노드를 동적으로 추가하거나 제거할 수 있어 데이터 처리에 유연합니다.

링크드 리스트와 큐의 결합은 큐의 FIFO 원칙을 유지하면서 메모리를 효율적으로 사용하는 구현 방식을 제공합니다.

링크드 리스트 기반 큐의 구조

링크드 리스트 기반 큐는 동적으로 메모리를 할당받아 노드(Node) 단위로 데이터를 저장하며, 두 개의 포인터(front와 rear)를 사용해 큐의 시작과 끝을 관리합니다.

기본 구성 요소

  1. 노드(Node)
  • 데이터와 다음 노드의 주소를 저장하는 구조체입니다.
   typedef struct Node {
       int data;
       struct Node* next;
   } Node;
  • data는 큐에 저장되는 값을 나타내며, next는 다음 노드를 가리키는 포인터입니다.
  1. 큐 구조(Queue)
  • 큐의 front와 rear를 관리하는 구조체입니다.
   typedef struct Queue {
       Node* front;
       Node* rear;
   } Queue;
  • front: 큐의 첫 번째 노드를 가리킵니다.
  • rear: 큐의 마지막 노드를 가리킵니다.

큐의 초기 상태

  • 큐가 비어 있을 때, front와 rear는 모두 NULL을 가리킵니다.
  • 삽입(Enqueue) 시 rear가 새로운 노드를 가리키고, front는 처음 추가된 노드를 유지합니다.

구조의 동작 원리

  • 삽입(Enqueue):
  • 새로운 노드를 생성하고, rear->next가 이 노드를 가리키도록 설정합니다.
  • rear를 새 노드로 업데이트합니다.
  • 삭제(Dequeue):
  • front가 가리키는 노드를 삭제하고, front를 다음 노드로 이동시킵니다.
  • 노드를 삭제한 후 큐가 비게 되면 front와 rear는 다시 NULL로 설정됩니다.

링크드 리스트 기반 큐는 이러한 구조를 통해 데이터의 동적 삽입과 삭제를 효율적으로 처리할 수 있습니다.

링크드 리스트 기반 큐 구현 코드

아래 코드는 링크드 리스트 기반 큐의 주요 동작을 구현한 예제입니다. 여기에는 큐 초기화, 삽입(Enqueue), 삭제(Dequeue), 그리고 큐 상태 확인 함수가 포함되어 있습니다.

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

// 노드 구조 정의
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 큐 구조 정의
typedef struct Queue {
    Node* front; // 큐의 앞쪽
    Node* rear;  // 큐의 뒤쪽
} Queue;

// 큐 초기화 함수
Queue* createQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->front = NULL;
    q->rear = NULL;
    return q;
}

// 삽입(Enqueue) 함수
void enqueue(Queue* q, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;

    if (q->rear == NULL) { // 큐가 비어 있는 경우
        q->front = newNode;
        q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
    printf("Enqueued: %d\n", value);
}

// 삭제(Dequeue) 함수
int dequeue(Queue* q) {
    if (q->front == NULL) { // 큐가 비어 있는 경우
        printf("Queue is empty.\n");
        return -1;
    }

    Node* temp = q->front;
    int value = temp->data;
    q->front = q->front->next;

    if (q->front == NULL) { // 큐가 비게 된 경우
        q->rear = NULL;
    }

    free(temp);
    printf("Dequeued: %d\n", value);
    return value;
}

// 큐 상태 출력 함수
void displayQueue(Queue* q) {
    if (q->front == NULL) {
        printf("Queue is empty.\n");
        return;
    }

    Node* temp = q->front;
    printf("Queue: ");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

// 메인 함수
int main() {
    Queue* q = createQueue();

    enqueue(q, 10);
    enqueue(q, 20);
    enqueue(q, 30);

    displayQueue(q);

    dequeue(q);
    dequeue(q);

    displayQueue(q);

    dequeue(q);
    dequeue(q); // 빈 큐에서 삭제 시도

    return 0;
}

코드 설명

  1. 큐 생성: createQueue 함수는 front와 rear가 NULL로 초기화된 큐를 생성합니다.
  2. 삽입(Enqueue): enqueue 함수는 새로운 노드를 생성해 큐의 끝에 추가합니다.
  3. 삭제(Dequeue): dequeue 함수는 front 노드를 제거하고, 그 데이터를 반환합니다.
  4. 상태 확인: displayQueue 함수는 현재 큐의 모든 데이터를 출력합니다.

이 코드는 링크드 리스트 기반 큐의 기본 동작을 이해하고 활용할 수 있는 토대를 제공합니다.

주요 함수의 동작 원리

링크드 리스트 기반 큐에서의 주요 연산인 삽입(Enqueue)와 삭제(Dequeue)는 각각 큐의 끝(rear)과 앞(front)을 조작하며 수행됩니다. 이 연산들의 동작 원리를 상세히 살펴보겠습니다.

삽입(Enqueue) 함수의 동작 원리

  1. 새로운 노드 생성:
  • 동적 메모리 할당으로 새로운 노드를 생성하고, 데이터를 저장합니다.
   Node* newNode = (Node*)malloc(sizeof(Node));
   newNode->data = value;
   newNode->next = NULL;
  1. 큐가 비어 있는 경우:
  • front와 rear가 모두 NULL인 경우, 새 노드를 front와 rear로 설정합니다.
   if (q->rear == NULL) {
       q->front = newNode;
       q->rear = newNode;
   }
  1. 큐가 비어 있지 않은 경우:
  • 현재 rear의 next를 새 노드로 연결하고, rear를 새 노드로 업데이트합니다.
   else {
       q->rear->next = newNode;
       q->rear = newNode;
   }
  1. 결과:
  • 새 노드가 큐의 끝에 추가되고, rear는 새 노드를 가리킵니다.
  • 시간 복잡도: O(1)

삭제(Dequeue) 함수의 동작 원리

  1. 큐가 비어 있는 경우:
  • front가 NULL인 경우, 큐가 비어 있음을 알리고 동작을 중단합니다.
   if (q->front == NULL) {
       printf("Queue is empty.\n");
       return -1;
   }
  1. 노드 제거:
  • front가 가리키는 노드를 임시 변수에 저장합니다.
  • 데이터를 복사한 후 front를 다음 노드로 이동시킵니다.
   Node* temp = q->front;
   int value = temp->data;
   q->front = q->front->next;
  1. 큐가 비게 된 경우:
  • 삭제 후 front가 NULL이 되면, rear도 NULL로 설정하여 큐의 상태를 초기화합니다.
   if (q->front == NULL) {
       q->rear = NULL;
   }
  1. 메모리 해제:
  • 임시 변수에 저장된 노드를 삭제합니다.
   free(temp);
  1. 결과:
  • front의 데이터를 반환하고, 큐의 앞에서 한 노드를 제거합니다.
  • 시간 복잡도: O(1)

큐 상태 변화 예시

연산큐 상태frontrear설명
초기 상태(empty)NULLNULL큐가 비어 있음
enqueue(10)101010첫 번째 노드 추가
enqueue(20)10 → 20102020을 끝에 추가
dequeue()20202010을 제거, front 이동
dequeue()(empty)NULLNULL20을 제거, 큐가 비어짐

이 동작 원리를 이해하면 큐의 효율적인 사용 및 디버깅이 가능해집니다.

링크드 리스트 기반 큐의 장점과 단점

링크드 리스트 기반 큐는 배열 기반 큐와 비교했을 때 몇 가지 중요한 장점과 단점을 가지고 있습니다. 이 특성을 이해하면 구현 환경에 적합한 자료구조를 선택할 수 있습니다.

장점

  1. 동적 크기 조정 가능
  • 링크드 리스트는 노드를 동적으로 할당하므로, 큐의 크기가 사전에 고정되지 않습니다.
  • 삽입 연산(Enqueue) 시 메모리가 부족하지 않는 한 제한 없이 데이터를 추가할 수 있습니다.
  1. 메모리 효율성
  • 배열 기반 큐는 크기를 초과하면 메모리 재할당이 필요하지만, 링크드 리스트 기반 큐는 현재 필요한 만큼만 메모리를 사용합니다.
  1. 데이터 처리의 유연성
  • 삽입과 삭제 연산 모두 O(1)의 시간 복잡도를 가지므로, 데이터의 크기가 커져도 성능에 큰 영향을 미치지 않습니다.
  1. 오버플로우 방지
  • 배열 기반 큐는 정해진 크기를 초과하면 오버플로우가 발생하지만, 링크드 리스트 기반 큐는 메모리가 허용하는 한 삽입 연산이 가능합니다.

단점

  1. 추가 메모리 사용
  • 각 노드는 데이터와 함께 다음 노드의 주소를 저장하는 포인터를 포함하므로, 배열 기반 큐에 비해 추가 메모리가 필요합니다.
  1. 구현 복잡성
  • 배열 기반 큐는 간단히 인덱스 값을 조작하여 삽입과 삭제를 수행할 수 있지만, 링크드 리스트 기반 큐는 포인터를 정확히 관리해야 하므로 구현이 더 복잡합니다.
  1. 캐시 비효율성
  • 링크드 리스트는 메모리 공간이 비연속적으로 할당되므로 배열에 비해 캐시 친화적이지 않습니다. 이는 성능 저하로 이어질 수 있습니다.
  1. 메모리 누수 위험
  • 동적 메모리를 사용하므로, 삽입과 삭제 과정에서 메모리를 적절히 해제하지 않으면 메모리 누수가 발생할 위험이 있습니다.

배열 기반 큐와 비교

특성링크드 리스트 큐배열 기반 큐
크기 제한없음고정 크기(재할당 필요)
메모리 사용동적 메모리 할당고정된 메모리 사용
삽입/삭제 성능O(1)O(1) (순환 큐에서)
구현 난이도높음낮음
캐시 성능낮음높음

결론


링크드 리스트 기반 큐는 동적 크기 조정과 유연성이 필요한 경우에 적합하며, 메모리 사용량과 성능을 세밀히 관리해야 하는 환경에서 유용합니다. 그러나 메모리 누수 방지와 포인터 관리의 복잡성을 염두에 두고 사용해야 합니다.

디버깅과 주요 에러 해결 방법

링크드 리스트 기반 큐를 구현할 때 자주 발생하는 문제와 이를 해결하기 위한 디버깅 방법을 살펴보겠습니다. 적절한 디버깅은 코드 안정성과 신뢰성을 높이는 핵심입니다.

1. 큐가 비어 있을 때 삭제(Dequeue)를 시도

  • 문제: 큐가 비어 있을 때 삭제 연산을 수행하면 front가 NULL인 상태에서 잘못된 접근이 발생해 프로그램이 충돌합니다.
  • 해결 방법:
  • dequeue 함수에서 먼저 front가 NULL인지 확인하여 큐가 비어 있는 상태인지 검사합니다.
  if (q->front == NULL) {
      printf("Queue is empty.\n");
      return -1;
  }

2. 메모리 누수

  • 문제: 삭제(Dequeue) 과정에서 제거된 노드의 메모리를 해제하지 않으면 메모리 누수가 발생합니다.
  • 해결 방법:
  • 삭제된 노드를 임시 변수에 저장하고, 사용이 끝난 후 free()를 호출해 메모리를 해제합니다.
  Node* temp = q->front;
  q->front = q->front->next;
  free(temp);

3. 큐가 비게 되었을 때 rear 포인터 관리

  • 문제: 큐가 비게 된 후 rear 포인터가 이전 노드를 계속 가리키고 있으면 삽입(Enqueue) 시 잘못된 연결이 발생할 수 있습니다.
  • 해결 방법:
  • dequeue 함수에서 front가 NULL이 되면 rear도 함께 NULL로 설정합니다.
  if (q->front == NULL) {
      q->rear = NULL;
  }

4. 잘못된 포인터 초기화

  • 문제: 노드를 초기화하지 않거나 next 포인터를 설정하지 않으면, 큐 연결이 올바르게 이루어지지 않습니다.
  • 해결 방법:
  • 새로운 노드를 생성할 때 반드시 next 포인터를 NULL로 초기화합니다.
  Node* newNode = (Node*)malloc(sizeof(Node));
  newNode->data = value;
  newNode->next = NULL;

5. 메모리 부족

  • 문제: 동적 메모리 할당이 실패하면 프로그램이 예상치 못한 동작을 할 수 있습니다.
  • 해결 방법:
  • 메모리 할당 후 반환값이 NULL인지 확인하고, 적절히 오류 메시지를 출력합니다.
  Node* newNode = (Node*)malloc(sizeof(Node));
  if (newNode == NULL) {
      printf("Memory allocation failed.\n");
      return;
  }

6. 큐 순환 확인

  • 문제: 잘못된 포인터 연결로 인해 큐의 노드들이 순환을 형성하여 무한 루프가 발생할 수 있습니다.
  • 해결 방법:
  • 디버깅 시 큐를 순회하며 방문한 노드의 주소를 추적하여 순환 여부를 확인합니다.

디버깅 팁

  1. 로그 활용: 각 연산(삽입, 삭제, 출력) 직후에 큐의 상태를 출력하여 동작을 확인합니다.
  2. 디버거 사용: 포인터의 값과 메모리 상태를 디버거로 점검합니다.
  3. 유닛 테스트: 큐의 다양한 시나리오(빈 큐, 단일 노드, 여러 노드, 초과 삽입 등)에 대해 테스트 케이스를 작성합니다.

결론


링크드 리스트 기반 큐의 디버깅은 포인터와 동적 메모리 관리가 핵심입니다. 위의 문제와 해결 방법을 숙지하면 안전하고 효율적인 코드를 작성할 수 있습니다.

응용 예제: 큐를 활용한 작업 스케줄링

링크드 리스트 기반 큐는 작업 스케줄링과 같은 문제에서 효율적으로 사용할 수 있습니다. 아래는 여러 작업을 순차적으로 처리하기 위해 큐를 사용하는 간단한 예제입니다.

문제 상황


시스템에서 처리해야 할 작업 목록이 주어졌으며, 작업은 도착한 순서대로 처리되어야 합니다. 각 작업은 작업 ID와 처리 시간을 포함합니다.

큐를 사용한 해결 방안

  1. 각 작업을 큐에 삽입합니다(Enqueue).
  2. 큐에서 작업을 하나씩 꺼내면서(Dequeue) 처리합니다.
  3. 모든 작업이 처리될 때까지 반복합니다.

코드 구현

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h> // 작업 시뮬레이션을 위한 sleep 함수 사용

// 작업 구조 정의
typedef struct Task {
    int id;         // 작업 ID
    int processTime; // 처리 시간(초)
} Task;

// 노드 구조 정의
typedef struct Node {
    Task task;
    struct Node* next;
} Node;

// 큐 구조 정의
typedef struct Queue {
    Node* front;
    Node* rear;
} Queue;

// 큐 초기화 함수
Queue* createQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->front = NULL;
    q->rear = NULL;
    return q;
}

// 작업 삽입(Enqueue)
void enqueue(Queue* q, Task task) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->task = task;
    newNode->next = NULL;

    if (q->rear == NULL) {
        q->front = newNode;
        q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
    printf("Task %d added to queue (Process time: %d seconds)\n", task.id, task.processTime);
}

// 작업 삭제(Dequeue)
Task dequeue(Queue* q) {
    Task nullTask = {-1, 0};
    if (q->front == NULL) {
        printf("Queue is empty.\n");
        return nullTask;
    }

    Node* temp = q->front;
    Task task = temp->task;
    q->front = q->front->next;

    if (q->front == NULL) {
        q->rear = NULL;
    }

    free(temp);
    return task;
}

// 큐 상태 확인
int isQueueEmpty(Queue* q) {
    return q->front == NULL;
}

// 메인 함수
int main() {
    Queue* taskQueue = createQueue();

    // 작업 추가
    enqueue(taskQueue, (Task){1, 3});
    enqueue(taskQueue, (Task){2, 2});
    enqueue(taskQueue, (Task){3, 1});

    // 작업 처리
    while (!isQueueEmpty(taskQueue)) {
        Task task = dequeue(taskQueue);
        if (task.id != -1) {
            printf("Processing Task %d...\n", task.id);
            sleep(task.processTime); // 작업 시간 시뮬레이션
            printf("Task %d completed.\n", task.id);
        }
    }

    printf("All tasks processed.\n");
    return 0;
}

코드 설명

  1. Task 구조체: 작업 ID와 처리 시간을 저장합니다.
  2. enqueue: 새로운 작업을 큐의 끝에 추가합니다.
  3. dequeue: 큐의 맨 앞 작업을 제거하고 반환합니다.
  4. isQueueEmpty: 큐가 비어 있는지 확인합니다.
  5. 작업 처리: sleep 함수를 사용해 작업 처리 시간을 시뮬레이션하며, 큐에서 작업을 하나씩 처리합니다.

결과 출력

Task 1 added to queue (Process time: 3 seconds)
Task 2 added to queue (Process time: 2 seconds)
Task 3 added to queue (Process time: 1 second)
Processing Task 1...
Task 1 completed.
Processing Task 2...
Task 2 completed.
Processing Task 3...
Task 3 completed.
All tasks processed.

응용 가능성

  • 프린터 대기열: 여러 사용자의 프린터 작업을 순차적으로 처리.
  • 프로세스 스케줄링: CPU에서 여러 작업을 처리할 때 사용.
  • 데이터 스트림 처리: 도착 순서대로 데이터를 처리하는 경우.

큐를 활용한 작업 스케줄링은 순차적 작업 처리의 기본 모델로, 다양한 시스템에서 사용됩니다.

요약

링크드 리스트 기반 큐는 C 언어에서 유연하고 효율적인 큐 구현 방법을 제공합니다. 이 기사에서는 큐와 링크드 리스트의 기본 개념, 구현 코드, 주요 함수의 동작 원리, 장단점, 디버깅 방법, 그리고 작업 스케줄링과 같은 실용적인 응용 예제를 살펴보았습니다.

링크드 리스트 기반 큐는 배열 기반 큐에 비해 동적 크기 조정, 메모리 효율성, 유연성과 같은 강점을 가지지만, 추가적인 메모리 사용과 구현의 복잡성을 고려해야 합니다. 이 기사를 통해 큐의 구조와 활용법을 명확히 이해하고, 실제 개발 환경에서 효과적으로 적용할 수 있을 것입니다.

C 언어
C언어 링크드 리스트 자료구조 큐 구현
목차