IT

[C] 연결리스트 Linked List

HIUDevLog 2025. 3. 20. 18:10
반응형


1. 연결 리스트란?

연결 리스트(Linked List)는 포인터를 이용해서 데이터를 동적으로 연결하는 자료구조예요.
배열(Array)과 달리 크기가 고정되지 않고, 필요할 때마다 메모리를 할당해서 사용할 수 있어요.

배열은 인덱스를 이용해서 빠르게 접근할 수 있는 장점이 있지만, 크기가 고정적이고 삽입/삭제가 어려운 단점이 있어요.
반면, 연결 리스트는 필요할 때마다 노드를 추가할 수 있어서 크기가 유동적이고 삽입/삭제가 쉬운 구조예요.

⸻

2. 단일 연결 리스트(Singly Linked List)

단일 연결 리스트는 각 노드가 다음 노드를 가리키는 포인터를 가지고 있는 구조예요.
즉, 한 방향으로만 이동할 수 있어요.

노드(Node) 구조

C 언어에서는 struct를 사용해서 연결 리스트의 노드를 만들어요.

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

// 노드 구조 정의
typedef struct Node {
    int data;          // 데이터 저장
    struct Node* next; // 다음 노드를 가리키는 포인터
} Node;



각 노드는 data 값을 가지고 있고, 다음 노드를 가리키는 next 포인터를 가지고 있어요.

노드 생성 및 추가

새로운 노드를 생성하려면 malloc을 사용해서 동적으로 메모리를 할당해야 해요.

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node)); // 새 노드 할당
    newNode->data = data;  // 데이터 저장
    newNode->next = NULL;  // 다음 노드 없음
    return newNode;
}



이제 노드를 연결 리스트에 추가하는 함수를 만들어볼게요.

void appendNode(Node** head, int data) {
    Node* newNode = createNode(data);  // 새 노드 생성
    if (*head == NULL) {  // 리스트가 비어 있으면 새로운 노드를 첫 번째 노드로 설정
        *head = newNode;
        return;
    }

    Node* temp = *head;
    while (temp->next != NULL) {  // 마지막 노드까지 이동
        temp = temp->next;
    }
    temp->next = newNode;  // 마지막 노드의 next를 새로운 노드로 연결
}




⸻

3. 연결 리스트 출력 함수

연결 리스트의 모든 데이터를 출력하는 함수도 만들어볼게요.

void printList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}



이제 우리가 만든 함수를 사용해서 연결 리스트를 테스트해볼게요.

int main() {
    Node* head = NULL;  // 초기 리스트는 비어 있음

    appendNode(&head, 10);
    appendNode(&head, 20);
    appendNode(&head, 30);

    printList(head);  // 출력: 10 -> 20 -> 30 -> NULL

    return 0;
}




⸻

4. 노드 삭제

연결 리스트에서 특정 노드를 삭제하는 방법도 알아볼게요.

void deleteNode(Node** head, int key) {
    Node* temp = *head, *prev = NULL;

    // 삭제할 노드가 첫 번째 노드인 경우
    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        return;
    }

    // 삭제할 노드를 찾을 때까지 이동
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    // 노드를 찾지 못한 경우
    if (temp == NULL) return;

    // 이전 노드와 다음 노드를 연결
    prev->next = temp->next;
    free(temp);
}



테스트 코드:

int main() {
    Node* head = NULL;

    appendNode(&head, 10);
    appendNode(&head, 20);
    appendNode(&head, 30);
    printList(head);  // 출력: 10 -> 20 -> 30 -> NULL

    deleteNode(&head, 20);
    printList(head);  // 출력: 10 -> 30 -> NULL

    return 0;
}




⸻

5. 연결 리스트의 활용과 한계

✅ 장점:
• 크기 제한 없이 노드를 추가할 수 있어요.
• 삽입/삭제가 배열보다 효율적이에요.

❌ 단점:
• 랜덤 접근이 불가능해서 특정 노드를 찾으려면 처음부터 순차 탐색해야 해요.
• 포인터를 관리해야 해서 코드가 더 복잡해질 수 있어요.

⸻

정리
1. 연결 리스트는 동적으로 크기를 조절할 수 있는 자료구조예요.
2. 배열보다 삽입/삭제가 효율적이지만, 접근 속도는 느려요.
3. C 언어에서는 struct와 malloc을 사용해서 구현해요.
4. 단일 연결 리스트를 직접 구현하면서 추가, 삭제, 출력 기능을 연습해보면 좋아요.

⸻

이제 연결 리스트의 기본 개념과 구현을 정리했어요.
2학년때 배웠던 내용이라 엄청 어려웠던 기억이 남네요😅

반응형