[C] 연결 리스트 구현

방법이있지·2025년 6월 14일
C크래프톤 정글

[정글 4-8주차] C언어

목록 보기
11/26
post-thumbnail

정글 5주차 과제로는 기본적으로 제공하는 자료구조 구조체 및 함수를 이용해서, 다양한 응용문제를 풀게 됩니다.

블로그에서 모든 응용문제를 다루기보다는, 기본 제공 코드의 구조체 및 함수의 동작 원리만 분석할 계획입니다. 사실 이걸 제대로 알면 응용문제를 푸는 게 더 수월할 거에요.

  • 따라서 코드는 제가 직접 작성하진 않았고(약간의 수정은 있음) 정글에서 제공한 코드입니다. 물론 주석, 설명이랑 그림은 제가 추가했습니다!

연결 리스트에 대한 상세한 설명은 이 글을 참고해주세요

본 글의 전체 소스 코드는 깃허브에 올려 두었습니다

구조체 선언

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

// 각 노드를 나타내는 구조체 ListNode
typedef struct _listnode{
    int item;                   // 노드에 저장된 값
    struct _listnode *next;     // 다음 노드를 가리키는 포인터
} ListNode;

// 연결 리스트 전체를 나타내는 구조체 LinkedList
typedef struct _linkedlist{
    int size;                   // 연결 리스트의 원소 수
    ListNode *head;             // 머리 노드를 가리키는 포인터
} LinkedList;

  • 연결 리스트는 각 노드가 다음 노드를 가리키는 구조

    • 따라서 ListNode 구조체에, 다음 노드를 가리키는 ListNode *형 포인터 next를 둠
    • 꼬리 노드라 다음 노드를 가리키지 않을 시, next의 값은 NULL (널 포인터)

  • 머리 노드의 위치를 모르면 연결 리스트의 탐색을 할 수 없음

    • 따라서 LinkedList 구조체에, 머리 노드를 가리키는 ListNode *형 포인터 head를 둠
    • 연결 리스트가 비어 있을 땐, 머리 노드가 없으므로 head의 값은 NULL (널 포인터)

⚠️ 엄밀히 말하면 head나 next의 포인터에는 가리키는 노드 구조체의 주소가 저장됩니다. 다만 본 글에서는 간결성을 위해 head에 노드를 저장, next에 노드를 저장과 같은 방식으로 표현하겠습니다. 착오가 없길 바랍니다.

특정 인덱스의 원소 찾기

  • 머리 노드부터 차례로 찾고자 하는 위치의 노드까지 이동
  • 도착하면 해당 노드를 반환
// 연결 리스트의 특정 인덱스 노드를 반환
ListNode *findNode(LinkedList *ll, int index){
    
    // 연결 리스트가 없거나, 인덱스가 범위를 벗어나는 경우
    if (ll == NULL || index < 0 || index >= ll -> size){
        return NULL;
    }

    // 리스트 순회 중 현재 노드
    ListNode *temp = ll -> head;    // 머리부터 시작

    // 리스트에 노드가 없는 경우 (그럼 head가 NULL이겠죠)
    if (temp == NULL){
        return NULL;
    }

    // 본격적으로 연결 리스트 탐색
    // index번째 요소를 찾으려면, 총 index번 이동해야 함
    while (index > 0){
        temp = temp -> next;    // 다음 노드로 이동
        if (temp == NULL) return NULL;
        index--;                // index 값 1 감소
    }

    // 현재 위치의 노드 반환
    return temp;
}

  • 리스트 내에서 이동할 때, 현재 노드를 가리키는 포인터 temp 선언
  • index번째 요소를 찾기 위해선, 0번째 노드인 head부터 총 index번 이동해야 함
    • while문으로 temp = temp -> next로 다음 노드로 이동하며 - index--로 값을 1씩 감소시킴
  • index == 0이 되었을 때 temp를 반환하여, 현재 위치의 노드 반환

노드 삽입

// 연결 리스트 ll의 인덱스 index에 값 value 삽입
int insertNode(LinkedList *ll, int index, int value){

    // pre는 이전 노드, cur은 현재 노드를 가리킴
    ListNode *pre, *cur;

    // 연결 리스트가 없거나, 인덱스가 범위를 벗어나는 경우
    if (ll == NULL || index < 0 || index > ll->size)
		return -1;

    // 이후 코드에 계속
}
  • 노드를 삽입할 때도 연결 리스트에서 삽입할 위치까지 이동해야 함
    • 따라서 현재 노드를 가리키는 포인터 cur을 선언
  • 추가로, 노드를 삽입할 땐 이전 노드의 next 포인터가 삽입된 노드를 가리키도록 변경해야 함
    • 따라서 현재 노드의 직전 노드를 가리키는 포인터 pre 역시 선언
  • 이후 동작은, 삽입할 노드의 위치가 머리 (맨 앞)인지, 다른 위치인지에 따라 달라짐

머리 노드에 삽입할 때

int insertNode(LinkedList *ll, int index, int value){
    // 위 코드에서 계속

    // 리스트가 비어 있거나 머리에 삽입할 때 (index == 0)
    if (ll -> head == NULL || index == 0) {
        // (1) 현재 머리 노드를 cur에 저장
        cur = ll -> head;
        
        // (2) 새로운 노드 생성 후, 머리 노드를 새로운 노드로 변경
        ll -> head = malloc(sizeof(ListNode));
        ll -> head -> item = value;

        // (3) 새로운 노드는 기존 머리노드 (cur)를 가리키게 함
        ll -> head -> next = cur;

        // (4) 연결리스트의 size를 1 증가
        ll -> size++;
        return 0;
    }

    // 아래 코드에서 계속
}

  • (1단계) 기존 머리 노드를 cur에 임시 저장
  • (2단계) 새로운 노드를 생성 후, ll -> head에 생성한 노드를 저장
    • 생성 과정에서 malloc(sizeof(ListNode)) 썼으니, 나중에 삭제 시 free해줘야 함!!
    • 이후 ll -> head -> item, ll -> head -> next로 새로운 노드의 멤버 설정 가능
  • (3단계) 새로운 노드의 next에 기존 머리 노드 cur을 저장
    • 즉 ll -> head -> next = cur
  • (4단계) 연결리스트의 원소 수인 ll -> size를 1 증가

머리 노드가 아닌 위치에 삽입할 때

int insertNode(LinkedList *ll, int index, int value){
    // 위 코드에서 계속

    // 0이 아닌 인덱스에 삽입하는 경우
    // (1) 삽입할 인덱스 직전 노드를 `pre`에 저장
    // 앞서 만든 findNode로 index-1번째 노드를 찾으면 됨
    if ((pre = findNode(ll, index - 1)) != NULL){
        // (1계속) 그리고 삽입할 인덱스의 노드는 `cur`에 저장
        // 당연히 `pre`의 다음 노드
        cur = pre -> next;

        // (2) 새로운 노드 생성 후, 인덱스 이전의 노드가 새로운 노드를 가리키게 함
        pre -> next = malloc(sizeof(ListNode));
        pre -> next -> item = value;

        // (3) 새로운 노드는 원래 인덱스의 노드를 가리키게 함
        pre -> next -> next = cur;

        // (4) 연결리스트의 size를 1 증가
        ll -> size++;

        return 0;
    }

    // findNode 과정에서 NULL을 만나면 -1 반환
    return -1;
}

  • (1단계) 삽입할 인덱스의 직전 노드를 pre, 삽입할 인덱스의 기존 노드를 cur에 저장
    • 앞서 특정 인덱스의 원소 찾기에서 구현한 findIndex로 index-1번째 노드를 찾아 pre를 구함
    • cur은 pre의 다음 노드
  • (2단계) 새로운 노드를 생성 후, pre -> next에 생성한 노드를 저장
    • 생성 과정에서 malloc(sizeof(ListNode)) 썼으니, 나중에 삭제 시 free해줘야 함!!
    • 이후 pre -> next -> item, pre -> next -> next로 새로운 노드의 멤버 설정 가능
  • (3단계) 새로운 노드의 next에 기존 위치의 노드 cur을 저장
    • 즉 pre -> next -> next = cur
  • (4단계) 연결리스트의 원소 수인 ll -> size를 1 증가

🫤 연결 리스트의 맨 끝에 삽입을 해도 정상 작동하나요? 이 경우 삽입할 위치에 아무것도 없으니 cur이 NULL이 될 것 같은데요.

  • 네, 정상 작동합니다.
  • (3단계)에서 새 노드의 next를 cur로 설정하면, 결국 NULL이 저장되므로 새 노드가 꼬리 노드가 됩니다.
  • 코드 내에서 cur을 * 연산자로 참조할 일이 없기 때문에, 널 포인터를 참조하는 오류는 발생하지 않습니다.

노드 삭제

// 연결 리스트 ll의 index번째 노드를 제거
int removeNode(LinkedList *ll, int index){

    // pre는 이전 노드, cur은 현재 노드를 가리킴
    ListNode *pre, *cur;

    // 연결 리스트가 없거나, 인덱스가 범위를 벗어나는 경우
    if (ll == NULL || index < 0 || index >= ll -> size){
        return -1;
    }

    // 이후 코드에 계속
}
  • 노드를 삭제할 때도 연결 리스트에서 삭제할 위치까지 이동해야 함
    • 따라서 현재 노드를 가리키는 포인터 cur을 선언
  • 추가로, 노드를 삽입할 땐 이전 노드의 next 포인터가 삭제할 노드 다음의 노드를 가리키도록 변경해야 함
    • 따라서 현재 노드의 직전 노드를 가리키는 포인터 pre 역시 선언
  • 이후 동작은, 삭제할 노드의 위치가 머리 (맨 앞)인지, 다른 위치인지에 따라 달라짐

머리 노드를 삭제할 때

int removeNode(LinkedList *ll, int index){
    // 위 코드에서 계속
    // 머리 노드를 삭제하는 경우 (index == 0)
    if (index == 0){
        // (1) 삭제할 노드의 다음 노드를 cur에 저장
        cur = ll -> head -> next;

        // (2) 삭제할 노드의 메모리 사용 해제
        free(ll -> head);

        // (3) 머리 노드를, 삭제할 노드의 다음 노드로 변경
        ll -> head = cur;

        // (4) 연결 리스트의 size를 1 감소
        ll -> size--;
        return 0;
    }

    // 아래 코드에서 계속
}

  • (1단계) 삭제할 노드의 다음 노드를 cur에 저장
    • 머리 노드 (ll -> head)를 삭제하므로, cur은 (ll -> head -> next)
  • (2단계) 삭제할 노드의 메모리 사용 해제
    • 이전에 malloc으로 메모리를 할당했으니, free해 주어야 함
  • (3단계) 머리 노드, 즉 ll -> head를 cur로 변경
  • (4단계) 연결 리스트의 원소 수인 ll -> size를 1 감소

⚠️ 머리 노드가 유일한 노드인 경우, 다음 노드가 없기 때문에 cur은 NULL이 됩니다. 하지만 cur을 간접참조(*, ->)할 일은 없으니 에러가 발생하지 않습니다.

  • 이 경우 ll -> head = NULL이 되어 빈 연결 리스트가 됩니다.

머리 노드가 아닌 위치의 노드를 삭제할 때

// 연결 리스트 ll의 index번째 노드를 제거
int removeNode(LinkedList *ll, int index){
    // 위 코드에서 계속
    
    // 머리 노드가 아닌 노드를 제거하는 경우

    // (1) 제거할 인덱스 직전 노드를 `pre`에 저장
    // 앞서 만든 findNode로 index-1번째 노드를 찾으면 됨
    if ((pre = findNode(ll, index - 1)) != NULL){
        
        // 제거할 인덱스의 노드가 NULL인 경우 삭제 불가
        // -1 반환
        if (pre -> next == NULL) return -1;

        // (1계속) 제거할 인덱스의 노드는 `cur`에 저장
        // 당연히 `pre`의 다음 노드
        cur = pre -> next;

        // (2) 삭제할 인덱스 직전 노드가, 삭제할 인덱스 다음 노드를 가리키게 함
        pre -> next = cur -> next;
        
        // (3) 삭제할 `cur`의 메모리 사용 해제
        free(cur);

        // (4) 연결 리스트의 size를 1 감소
        ll -> size--;

        return 0;
    }
    
    // 삭제에 실패
    return -1;
}

  • (1단계) 삭제할 인덱스 직전 노드를 pre에, 삭제할 노드를 cur에 저장
    • 앞서 특정 인덱스의 원소 찾기에서 구현한 findIndex로 index-1번째 노드를 찾아 pre를 구함
    • cur은 pre의 다음 노드
  • (2단계) pre -> next에 cur -> next를 저장해, 삭제할 인덱스 직전 노드가 삭제할 인덱스 다음 노드를 가리키게 함
  • (3단계) 삭제할 노드의 메모리 사용 해제
    • 이전에 malloc으로 메모리를 할당했으니, free해 주어야 함
  • (4단계) 연결 리스트의 원소 수인 ll -> size를 1 감소

⚠️ 꼬리 노드를 제거하는 경우, 다음 노드가 없기 때문에 cur -> next는 NULL이 됩니다. 하지만 cur -> next를 간접참조(*, ->)할 일은 없으니 에러가 발생하지 않습니다.

  • 이 경우 pre -> next = NULL이 되어, 삭제할 노드 이전 노드가 꼬리 노드가 됩니다.

연결 리스트 출력

void printList(LinkedList *ll){
    // 연결리스트가 없는 경우
    if (ll == NULL) return;

    // 탐색하는 현재 노드
    // 머리 노드부터 시작
    ListNode *cur = ll -> head;

    // 연결 리스트가 비어 있을 때
    if (cur == NULL) printf("빈 리스트입니다.");

    // NULL을 만날 때까지 각 노드를 이동하며 값 출력
    while (cur != NULL){
        printf("%d ", cur -> item);
        cur = cur -> next;
    }
    printf("\n");
}
  • 연결 리스트를 탐색하면서, NULL 주소를 만날 때까지 각 값을 출력
  • 현재 노드를 가리키는 포인터 cur을 두고, cur -> item으로 출력
  • 그리고 cur = cur -> next로 다음 노드로 이동

모든 노드를 삭제

// 모든 노드를 삭제
void removeAllItems(LinkedList *ll)
{
	ListNode *cur = ll->head;   // 현재 노드
	ListNode *tmp;              // 다음 노드를 저장할 임시 변수

    // 모든 노드의 메모리 할당 해제
	while (cur != NULL){
		tmp = cur->next;
		free(cur);
		cur = tmp;
	}
    
    // 머리 노드는 NULL, 연결리스트 크기는 0으로 
	ll -> head = NULL;
	ll -> size = 0;
}
  • C언어에선 malloc으로 동적 할당한 메모리 공간은, 함수가 종료되어도 자동으로 회수되지 않음
  • 이를 위해, 한 번에 모든 노드를 삭제하며 free로 메모리 할당을 해제하는 함수 작성

동작과정

int main(void){
    // size는 0, head는 NULL로 초기화
    LinkedList ll = {0, NULL};
    
    // 순서대로 노드 삽입
    insertNode(&ll, ll.size, 41);
    insertNode(&ll, ll.size, 9);
    insertNode(&ll, ll.size, 33);
    printList(&ll); // 41 9 33

    // 노드 10을 1번 인덱스에 삽입
    insertNode(&ll, 1, 10);
    printList(&ll); // 41 10 9 33

    // 2번 인덱스의 노드를 삭제
    removeNode(&ll, 2);
    printList(&ll); // 41 10 33
    
    // 모든 노드 제거 및 free
    removeAllItems(&ll);

    return 0;
}
  • 연결 리스트의 크기는 0, 머리 노드는 NULL로 초기화
  • 연결 리스트 맨 끝에 노드를 삽입할 땐, ll.size번째 인덱스에 삽입할 수 있음
profile
방법이있지
뭔가 만드는 걸 좋아하는 개발자 지망생입니다. 프로야구단 LG 트윈스를 응원하고 있습니다.
이전 포스트

[C] 동적 할당 (2), 가변길이 배열

다음 포스트

[C] 스택 구현

0개의 댓글