[CS50] 자료구조 - 연결 리스트 개념과 구현

복잡한 프로그램을 구현하다 보면 기본적인 포인터 구조만 이용해서 메모리를 관리하기에는 다소 번거로울 때가 많다.

메모리를 좀 더 효율적으로 관리하고 사용할 수 있는 데이터 구조의 개념과 연결 리스트를 알아보자.

데이터 구조란

데이터 구조(Data Structure)는 우리가 컴퓨터 메모리를 더 효율적으로 관리하기 위해 새로 정의하는 구조체다.

일종의 메모리 레이아웃, 또는 지도라고 생각할 수 있다. 데이터 구조 중 하나인 연결 리스트에 대해 알아보자.

 

연결 리스트의 개념

배열의 한계

배열에서는 각 인덱스의 값이 메모리상에서 연이어 저장되어 있다.

배열: [1][2][3]
주소:  100 104 108  ← 연속된 메모리

하지만 꼭 그럴 필요가 있을까?

 

연결 리스트의 아이디어

각 값이 메모리상의 여러 군데 나뉘어져 있다고 하더라도 바로 다음 값의 메모리 주소만 기억하고 있다면 여전히 값을 연이어서 읽어들일 수 있다.

 

이를 연결 리스트(Linked List)라고 한다.

크기가 3인 연결 리스트는 각 인덱스의 메모리 주소에서 자신의 값과 함께 바로 다음 값의 주소(포인터)를 저장한다.

 

메모리 구조

주소 0x123: [1 | 0x456 →]
주소 0x456: [2 | 0x789 →]
주소 0x789: [3 | NULL  ]

 

특징

• 연결 리스트의 가장 첫 번째 값인 1은 2의 메모리 주소를 저장
• 2는 3의 메모리 주소를 함께 저장
• 3은 다음 값이 없기 때문에 NULL(\0, 즉 0으로 채워진 값)을 다음 값의 주소로 저장

 

연결 리스트 구조체 정의

연결 리스트는 다음과 같이 간단한 구조체로 정의할 수 있다.

typedef struct node
{
    int number;
    struct node *next;
}
node;

• node라는 이름의 구조체
• number: 각 node가 가지는 값
• *next: 다음 node를 가리키는 포인터

 

typedef struct node를 사용하는 이유

typedef struct 대신에 typedef struct node라고 node를 함께 명시해 주는 것은, 구조체 안에서 node를 사용하기 위함이다.

// 잘못된 예
typedef struct
{
    int number;
    struct node *next;  // ❌ node가 정의되지 않음
}
node;

// 올바른 예
typedef struct node
{
    int number;
    struct node *next;  // ✅ node 사용 가능
}
node;

 

연결 리스트 구현

구조체를 이용하여 연결 리스트를 구현하고 사용해보자.

전체 코드

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

// 연결 리스트의 기본 단위가 되는 node 구조체를 정의
typedef struct node
{
    // node 안에서 정수형 값이 저장되는 변수를 number로 지정
    int number;

    // 다음 node의 주소를 가리키는 포인터를 *next로 지정
    struct node *next;
}
node;

int main(void)
{
    // list라는 이름의 node 포인터를 정의
    // 연결 리스트의 가장 첫 번째 node를 가리킬 것
    // 현재 아무것도 가리키고 있지 않기 때문에 NULL로 초기화
    node *list = NULL;

    // 새로운 node를 위해 메모리를 할당하고 포인터 *n으로 가리킴
    node *n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }

    // n의 number 필드에 1의 값을 저장
    // n->number는 (*n).number와 동일한 의미
    // 즉, n이 가리키는 node의 number 필드를 의미
    // 간단하게 화살표 표시 `->`로 사용할 수 있음
    n->number = 1;

    // n 다음에 정의된 node가 없으므로 NULL로 초기화
    n->next = NULL;

    // 이제 첫 번째 node를 정의했기 때문에 list 포인터를 n 포인터로 바꿈
    list = n;

    // 이제 list에 다른 node를 더 연결하기 위해 n에 새로운 메모리를 다시 할당
    n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }

    // n의 number와 next의 값을 각각 저장
    n->number = 2;
    n->next = NULL;

    // list가 가리키는 것은 첫 번째 node
    // 이 node의 다음 node를 n 포인터로 지정
    list->next = n;

    // 다시 한 번 n 포인터에 새로운 메모리를 할당하고 number와 next의 값을 저장
    n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }

    n->number = 3;
    n->next = NULL;

    // 현재 list는 첫 번째 node를 가리키고, 이는 두 번째 node와 연결되어 있음
    // 따라서 세 번째 node를 더 연결하기 위해 첫 번째 node(list)의
    // 다음 node(list->next)의 다음 node(list->next->next)를 n 포인터로 지정
    list->next->next = n;

    // 이제 list에 연결된 node를 처음부터 방문하면서 각 number 값을 출력
    // 마지막 node의 next에는 NULL이 저장되어 있을 것이기 때문에
    // 이것이 for 루프의 종료 조건이 됨
    for (node *tmp = list; tmp != NULL; tmp = tmp->next)
    {
        printf("%i\n", tmp->number);
    }

    // 메모리를 해제해주기 위해 list에 연결된 node들을 처음부터 방문하면서 free
    while (list != NULL)
    {
        node *tmp = list->next;
        free(list);
        list = tmp;
    }
}

 

단계별 설명

1단계: 첫 번째 노드 생성

node *list = NULL;
node *n = malloc(sizeof(node));
n->number = 1;
n->next = NULL;
list = n;

 

메모리 상태

list → [1 | NULL]

 

2단계: 두 번째 노드 추가

n = malloc(sizeof(node));
n->number = 2;
n->next = NULL;
list->next = n;

 

메모리 상태

list → [1 | →] → [2 | NULL]

 

3단계: 세 번째 노드 추가

n = malloc(sizeof(node));
n->number = 3;
n->next = NULL;
list->next->next = n;

 

메모리 상태

list → [1 | →] → [2 | →] → [3 | NULL]

 

4단계: 리스트 순회

for (node *tmp = list; tmp != NULL; tmp = tmp->next)
{
    printf("%i\n", tmp->number);
}

 

출력

1
2
3

 

5단계: 메모리 해제

while (list != NULL)
{
    node *tmp = list->next;
    free(list);
    list = tmp;
}

 

해제 과정

1. tmp = [2 | →], free([1])
2. tmp = [3 | NULL], free([2])
3. tmp = NULL, free([3])

 

화살표 연산자 (->)

n->number는 (*n).number와 동일한 의미다.

// 두 가지 표현 방식
(*n).number = 1;  // 방법 1
n->number = 1;    // 방법 2 (더 간단)

 

화살표 연산자의 장점

• 코드가 더 간결하고 읽기 쉬움
• 포인터를 통한 구조체 접근에 특화

 

노드 추가와 삭제

중간에 노드 추가하기

// 중간에 노드를 추가하는 함수
void insert_after(node *prev, int value)
{
    // 새로운 노드를 위한 메모리를 할당
    node *n = malloc(sizeof(node));
    if (n == NULL)
    {
        exit(1);
    }

    // 새로운 노드에 값과 다음 포인터를 설정
    n->number = value;
    n->next = prev->next;

    // 이전 노드의 다음 포인터를 새로운 노드로 설정
    prev->next = n;
}

 

동작 과정

기존: [1] → [2] → NULL

추가 (1 뒤에 3):
1. 새 노드: [3] → [2]
2. 연결: [1] → [3] → [2] → NULL

 

사용 예시

int main(void)
{
    // 초기 연결 리스트 생성
    node *list = malloc(sizeof(node));
    list->number = 1;
    list->next = malloc(sizeof(node));
    list->next->number = 2;
    list->next->next = NULL;

    // 첫 번째 노드 뒤에 3을 추가
    insert_after(list, 3);

    // 리스트 출력: 1, 3, 2
    for (node *tmp = list; tmp != NULL; tmp = tmp->next)
    {
        printf("%d\n", tmp->number);
    }

    // 메모리 해제
    while (list != NULL)
    {
        node *tmp = list->next;
        free(list);
        list = tmp;
    }
    return 0;
}

 

중간에서 노드 삭제하기

// 중간에 노드를 삭제하는 함수
void delete_node(node *prev)
{
    if (prev == NULL || prev->next == NULL)
    {
        return;
    }

    // 삭제할 노드를 가리키는 포인터
    node *temp = prev->next;

    // 이전 노드의 다음 포인터를 삭제할 노드의 다음 노드로 설정
    prev->next = temp->next;

    // 삭제할 노드의 메모리를 해제
    free(temp);
}

 

동작 과정

기존: [1] → [2] → [3] → NULL

삭제 (2 삭제):
1. temp = [2]
2. [1]의 next = [3]
3. free([2])
결과: [1] → [3] → NULL

 

사용 예시

int main(void)
{
    // 초기 연결 리스트 생성
    node *list = malloc(sizeof(node));
    list->number = 1;
    list->next = malloc(sizeof(node));
    list->next->number = 2;
    list->next->next = malloc(sizeof(node));
    list->next->next->number = 3;
    list->next->next->next = NULL;

    // 두 번째 노드 삭제
    delete_node(list);

    // 리스트 출력: 1, 3
    for (node *tmp = list; tmp != NULL; tmp = tmp->next)
    {
        printf("%d\n", tmp->number);
    }

    // 메모리 해제
    while (list != NULL)
    {
        node *tmp = list->next;
        free(list);
        list = tmp;
    }
    return 0;
}

 

연결 리스트 vs 배열

장단점 비교

특성	배열	연결 리스트
메모리	연속적	분산적
크기 조정	어려움 (재할당 필요)	쉬움 (노드 추가)
임의 접근	O(1)	O(n)
삽입/삭제	O(n)	O(1) (포인터만 변경)
메모리 사용	효율적	추가 메모리 필요 (포인터)

 

언제 사용할까?

배열이 유리한 경우

• 크기가 고정적
• 인덱스를 통한 빠른 접근이 필요
• 메모리 효율이 중요

 

연결 리스트가 유리한 경우

• 크기가 동적으로 변함
• 삽입/삭제가 빈번함
• 순차적 접근만 필요