자료구조) 단방향 연결 리스트

단방향 연결 리스트(Singly Linked List)는 노드(Node)라는 개체들이 한 방향으로만 연결된 데이터 구조다.

각각의 노드는 값(데이터)과 다음 노드를 가리키는 포인터를 포함하고 있다.

노드(Node) 구조

struct Node
{
    T item = T();      // 데이터 저장
    Node* next = nullptr; // 다음 노드를 가리키는 포인터
};

• item → 실제 저장되는 데이터

• next → 다음 노드를 가리키는 포인터

• 마지막 노드의 next는 nullptr이며, 리스트의 끝을 의미한다.

단방향 연결 리스트 핵심 연산

맨 앞에 삽입 (PushFront)

새로운 노드를 리스트의 맨 앞에 추가하는 연산이다.

예제코드

void PushFront(T item)
{
    // 새 노드 생성
    Node* newNode = new Node{item, nullptr};
    
    // 새로운 노드의 next가 현재의 first_를 가리키도록 설정
    newNode->next = first_;
    
    // first_를 새로운 노드로 변경
    first_ = newNode;
}

동작원리

• 새 노드를 동적으로 할당 (newNode)

• newNode->next를 기존 first_ 노드로 설정

• first_를 newNode로 변경하여 새 노드가 리스트의 시작이 됨

시간 복잡도: O(1) → 항상 맨 앞에 추가하므로 빠르다.

맨 뒤에 삽입 (PushBack)

새로운 노드를 리스트의 맨 끝에 추가하는 연산이다.

예제코드

void PushBack(T item)
{
    Node* newNode = new Node{ item, nullptr };

    if (first_ == nullptr)  // 리스트가 비어있는 경우
    {
        first_ = newNode;
        return;
    }

    Node* curNode = first_;
    
    // 마지막 노드까지 이동
    while (curNode->next)
    {
        curNode = curNode->next;
    }
    
    // 마지막 노드의 next를 새 노드로 설정
    curNode->next = newNode;
}

동작원리

• 새 노드를 생성
• 리스트가 비어있다면 first_를 newNode로 설정
• 마지막 노드까지 이동한 후, curNode->next를 newNode로 연결

시간 복잡도: O(n) → 마지막 노드를 찾기 위해 선형 탐색 필요

맨 앞의 노드 삭제 (PopFront)

리스트의 첫 번째 노드를 삭제하는 연산이다.

예제코드

void PopFront()
{
    if (IsEmpty()) return;

    Node* temp = first_;
    first_ = first_->next; // 첫 번째 노드를 다음 노드로 변경
    
    delete temp; // 이전 첫 번째 노드 삭제
}

동작원리

• first_를 temp에 저장 (삭제할 노드)
• first_를 다음 노드로 변경
• temp를 delete하여 메모리 해제

시간 복잡도: O(1) → 항상 첫 번째 노드만 삭제

맨 뒤의 노드 삭제 (PopBack)

리스트의 마지막 노드를 삭제하는 연산이다.

예제코드

void PopBack()
{
    if (IsEmpty()) return;

    if (first_->next == nullptr) // 노드가 하나뿐이라면
    {
        delete first_;
        first_ = nullptr;
        return;
    }

    Node* second_last = first_;
    
    // 마지막 노드의 이전 노드를 찾음
    while (second_last->next->next)
    {
        second_last = second_last->next;
    }

    delete second_last->next; // 마지막 노드 삭제
    second_last->next = nullptr;
}

동작원리

• 리스트가 비어있거나 노드가 하나뿐인지 확인
• 마지막에서 두 번째 노드를 찾음 (second_last)
• delete로 마지막 노드 제거 후 second_last->next = nullptr;

시간 복잡도: O(n) → 마지막 노드의 이전 노드를 찾기 위해 선형 탐색 필요

리스트 반전 (Reverse)

연결 리스트의 순서를 반대로 뒤집는 연산이다.

예제코드

void Reverse()
{
    Node* curNode = first_;
    Node* beforeNode = nullptr; // 이전 노드를 저장할 변수

    while (curNode)
    {
        Node* temp = curNode->next; // 다음 노드를 임시 저장
        curNode->next = beforeNode; // 현재 노드의 next를 이전 노드로 변경
        beforeNode = curNode;       // 이전 노드를 현재 노드로 업데이트
        curNode = temp;             // 다음 노드로 이동
    }
    
    first_ = beforeNode; // 마지막 노드가 리스트의 새로운 첫 번째 노드가 됨
}

동작원리

• curNode를 현재 노드로, beforeNode를 이전 노드로 사용
• 현재 노드의 next를 이전 노드로 변경 (방향을 뒤집음)
• 이전 노드와 현재 노드를 한 칸씩 이동하면서 반복
• 리스트가 끝나면 first_를 beforeNode로 변경

시간 복잡도: O(n) → 모든 노드를 한 번씩 방문하여 방향을 변경

단방향 연결 리스트의 한계

장점

• 메모리를 효율적으로 사용 (필요한 만큼만 동적 할당)
• 크기가 정해져 있지 않아 유연함
• 앞쪽 삽입/삭제가 빠름 (O(1))

단점

• 마지막 노드 접근이 느림 (O(n))
• 역방향 탐색이 불가능 (이전 노드를 찾으려면 처음부터 탐색해야 함)
• 메모리 관리 필요 (삭제 시 delete를 잊으면 메모리 누수 발생)

참고자료

https://www.geeksforgeeks.org/reverse-a-linked-list/