단일 연결 리스트 개념

단일 연결 리스트(Singly Linked List)는 노드(Node)라 불리는 요소들이 포인터로 연결된 선형 자료구조입니다. 각 노드는 두 가지 핵심 요소로 구성됩니다:

• 데이터 영역: 실제 값을 저장하는 공간
• 포인터 영역: 다음 노드의 주소를 저장하는 공간

리스트의 시작을 헤드 노드(Head)라 하며, 마지막 노드의 포인터는 NULL 값을 가집니다. 리스트 탐색은 단방향으로만 이루어집니다.

배열과의 비교 분석

• 접근 속도: 배열은 인덱스로 직접 접근 가능(O(1)), 연결 리스트는 순차 탐색 필요(O(n))
• 삽입/삭제: 배열은 요소 이동이 필요하나(O(n)), 연결 리스트는 포인터 조정만으로 가능(O(1))
• 메모리 활용: 배열은 연속된 메모리 공간이 필요하나, 연결 리스트는 분산 메모리 활용 가능

구조체 기반 구현

typedef struct ListNode {
    int value;           // 데이터 저장
    ListNode* next_ptr;  // 다음 노드 포인터
} ListNode;

ListNode* list_head = NULL;  // 헤드 포인터 초기화

헤드에 노드 추가

void insert_front(int val) {
    ListNode* new_node = new ListNode;
    new_node->value = val;
    new_node->next_ptr = list_head;
    list_head = new_node;
}

특정 위치에 노드 삽입

void insert_after(int position, int val) {
    ListNode* new_node = new ListNode;
    new_node->value = val;
    
    ListNode* current = list_head;
    for (int i = 0; i < position; i++) {
        current = current->next_ptr;
    }
    
    new_node->next_ptr = current->next_ptr;
    current->next_ptr = new_node;
}

노드 삭제

void remove_node(int position) {
    ListNode* current = list_head;
    for (int i = 0; i < position; i++) {
        current = current->next_ptr;
    }
    
    ListNode* target = current->next_ptr;
    current->next_ptr = target->next_ptr;
    delete target;  // 메모리 해제
}

메모리 관리 주의사항

new 연산자로 할당된 노드는 반드시 delete로 해제해야 메모리 누수를 방지할 수 있습니다. 특히 노드 삭제 시 할당된 메모리를 해제하는 것을 잊지 않아야 합니다.

핵심 학습 포인트

연결 리스트 구현의 핵심은 물리적 메모리 배치보다 포인터 연결 관계에 집중하는 것입니다. 빈 리스트, 단일 노드, 마지막 노드 처리 같은 경계 조건을 정확히 이해하고, 모든 연산 후 포인터 상태를 검증하는 습관이 필요합니다.