◀ 74.6 심사문제: 특정 노드 삭제하기Q & A ▶︎

핵심 정리

거품 정렬

거품 정렬은 처음부터 끝까지 요소를 순회하면서 인접한 요소를 비교합니다.

  • 오름차순: 현재 값과 바로 뒤에 있는 값을 비교하여 큰 값을 뒤로 보냅니다. 따라서 큰 값을 뒤로 보내다 보면 작은 값에서 큰 값으로 오름차순 정렬이 됩니다.
  • 내림차순: 현재 값과 바로 뒤에 있는 값을 비교하여 작은 값을 뒤로 보냅니다. 따라서 작은 값을 뒤로 보내다 보면 큰 값에서 작은 값으로 내림차순 정렬이 됩니다.

퀵 정렬

C 언어에서는 효율이 좋은 퀵 정렬(quick sort) 함수를 표준 함수로 제공합니다. qsort 함수는 정렬할 배열, 요소 개수, 요소 크기, 비교 함수의 포인터를 매개변수로 받습니다. 여기서 비교 함수는 직접 구현해야 합니다.

qsort(정렬할배열, 요소개수, 요소크기, 비교함수);
qsort(정렬할메모리주소, 요소개수, 요소크기, 비교함수);

비교 함수는 const void 포인터 매개변수 두 개를 받는데 void 포인터로는 값을 가져올 수 없으므로 정렬할 배열, 메모리 주소의 자료형으로 역참조하여 값을 가져옵니다.

  • 오름차순: a < b → -1, a > b → 1, a == b → 0
  • 내림차순: a > b → -1, a < b → 1, a == b → 0 
int compare(const void *a, const void *b)
{
    // 정렬할 배열, 메모리 주소의 자료형으로 a와 b를 역참조하여 값을 가져옴

    // 오름차순 또는 내림차순 규칙에 따라 -1, 0 1을 반환
}

단일 연결 리스트

연결 리스트는 데이터가 담긴 노드(메모리 공간)를 서로 연결해놓은 상태를 말합니다. 단일 연결 리스트는 다른 노드를 가리키는 포인터가 하나씩만 있어서 단일 연결 리스트라고 합니다. 따라서 한 쪽 방향으로만 이동할 수 있습니다.

단일 연결 리스트의 구조체는 다음 노드의 주소를 저장하는 next 포인터를 멤버로 가지고 있습니다.

struct NODE {             // 연결 리스트의 노드 구조체
    struct NODE *next;    // 다음 노드의 주소를 저장할 포인터
    int data;             // 데이터를 저장할 멤버
};

단일 연결 리스트의 머리 노드

머리 노드(head node)는 단일 연결 리스트의 시작점이며 헤드(head)라고도 부릅니다. 특히 머리 노드는 연결 리스트의 첫 번째 노드를 가리키는 용도이므로 데이터를 저장하지 않습니다.

struct NODE *head = malloc(sizeof(struct NODE));    // 머리 노드 생성
                                                    // 머리 노드는 데이터를 저장하지 않음

free(head);    // 리스트를 사용한 뒤 동적 메모리 해제

단일 연결 리스트의 노드 추가

단일 연결 리스트에 노드를 추가하려면 먼저 새 노드를 생성(메모리 할당)합니다. 그리고 새 노드의 다음 노드에 기준 노드의 다음 노드를 지정한 뒤 기준 노드의 다음 노드에 새 노드를 지정하면 됩니다.

void addFirst(struct NODE *target, int data)    // 기준 노드 뒤에 노드를 추가하는 함수
{
    struct NODE *newNode = malloc(sizeof(struct NODE));    // 새 노드 생성
    newNode->next = target->next;    // 새 노드의 다음 노드에 기준 노드의 다음 노드를 지정
    newNode->data = data;            // 데이터 저장

    target->next = newNode;    // 기준 노드의 다음 노드에 새 노드를 지정
}

단일 연결 리스트의 노드 삭제

단일 연결 리스트는 기준 노드의 다음 노드를 삭제합니다. 따라서 기준 노드의 다음 노드에 삭제할 노드의 다음 노드를 지정하여 노드를 끌어옵니다. 노드간 연결을 정리했다면 삭제할 노드를 free 함수로 해제해줍니다.

void removeFirst(struct NODE *target)    // 기준 노드의 다음 노드를 삭제하는 함수
{
    struct NODE *removeNode = target->next;    // 기준 노드의 다음 노드 주소를 저장
    target->next = removeNode->next;    // 기준 노드의 다음 노드에 삭제할 노드의 다음 노드를 지정

    free(removeNode);    // 노드 메모리 해제
}

단일 연결 리스트의 순회

연결 리스트를 순회하려면 첫 번째 노드(head->next)부터 시작해서 현재 노드 curr에 curr->next를 계속 넣어주는 식으로 만듭니다. 이때 curr이 NULL이면 리스트의 끝이므로 반복을 끝내면 됩니다.

struct NODE *curr = head->next;    // 연결 리스트 순회용 포인터에 첫 번째 노드의 주소 저장
while (curr != NULL)               // 포인터가 NULL이 아닐 때 계속 반복
{
    printf("%d\n", curr->data);    // 현재 노드의 데이터 출력
    curr = curr->next;             // 포인터에 다음 노드의 주소 저장
}

◀ 74.6 심사문제: 특정 노드 삭제하기Q & A ▶︎