자료구조 단일 연결리스트 구현

데이터를 체인 형태로 관리하는 단일 연결 리스트(Singly Linked List)의 구조와 구현 원리를 정리했다.

데이터와 다음 노드의 주소를 결합하여 관리하는 방식이다.

노드 구조 설계

연결 리스트의 기본 단위인 노드를 다음과 같이 정의한다.

typedef struct Node {
    int data;           // 데이터 저장 필드
    struct Node* next;  // 다음 노드 주소 필드
} Node;

각 노드는 데이터와 함께 다음 데이터의 위치를 가리키는 포인터(next)를 포함한다.

노드들의 연결을 통해 리스트 구조가 형성된다.

데이터 삽입 프로세스 (Append)

리스트 후입단에 데이터를 추가하는 과정은 다음과 같다.

void append(Node** head, int data) {
    // 1. 신규 노드 생성 및 초기화
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;

    // 2. 리스트 공백 시 헤드 지정
    if (*head == NULL) {
        *head = newNode;
        return;
    }

    // 3. 종단 노드 탐색 및 연결
    Node* last = *head;
    while (last->next) last = last->next;
    last->next = newNode;
}

인덱스 기반 접근이 불가능하므로 종단 노드 탐색을 위해 순차적 접근이 필요하다.

이로 인해 탐색 시간 복잡도는 O(N)이다.

구조적 특징 분석

단일 연결 리스트는 동적 메모리 할당을 통해 크기를 유연하게 조절할 수 있다.

탐색 속도는 배열 대비 느리나, 삽입과 삭제가 빈번한 환경에서는 효율적인 도구이다.

기본 자료구조에 대한 이해는 복잡한 시스템 설계의 기초가 되는 것 같다.

웨이호프