Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 이중 연결 리스트(Doubly Linked List)의 크기 구하기

이번 글에서는 이중 연결 리스트(Doubly Linked List)가 주어졌을 때, 그 크기(size)를 구하는 프로그램을 C++로 작성해 보겠습니다.

이중 연결 리스트란?

이중 연결 리스트는 단일 연결 리스트(Singly Linked List)와 달리 양방향 탐색이 가능한 특수한 형태의 연결 리스트입니다. 즉, 앞쪽으로도 뒤쪽으로도 자유롭게 이동할 수 있어 데이터 삽입과 삭제가 더 유연합니다.

이중 연결 리스트의 개념을 이해하려면 다음과 같은 핵심 용어를 먼저 알아야 합니다.

  • Link(링크) – 연결 리스트의 각 노드는 '요소(element)'라 불리는 데이터를 저장할 수 있습니다.
  • Next(다음) – 각 노드는 바로 다음 노드를 가리키는 포인터인 Next를 포함합니다.
  • Prev(이전) – 각 노드는 바로 앞 노드를 가리키는 포인터인 Prev를 포함합니다.
  • LinkedList(연결 리스트) – 연결 리스트 전체는 첫 번째 노드를 가리키는 First와 마지막 노드를 가리키는 Last 포인터로 관리됩니다.

이중 연결 리스트의 구조

각 노드는 데이터 값(value), 다음 노드를 가리키는 next 포인터, 그리고 이전 노드를 가리키는 prev 포인터를 함께 가지고 있습니다.

A <-> B <-> C <-> D ...

문제 설명

위와 같은 형태의 이중 연결 리스트가 주어졌을 때, 해당 리스트의 길이(노드 개수)를 계산하는 것이 목표입니다.

예시

입력:

A <-> B <-> C

출력:

3

리스트에 A, B, C 세 개의 노드가 존재하므로 결과는 3이 됩니다.

해결 접근 방법

이중 연결 리스트의 크기를 구하려면 리스트를 처음부터 끝까지 순회(traverse)하면서 방문한 노드의 개수를 카운트 변수에 기록하면 됩니다.

알고리즘

초기화: length = 0, *temp = head

  1. 1단계 – temp가 NULL이 아닐 때까지 리스트를 순회합니다.
    • 1.1단계 – 길이를 증가시킵니다. (length++)
    • 1.2단계 – 포인터를 다음 노드로 이동시킵니다. (temp = temp->next)
  2. 2단계 – 최종 길이(length)를 반환하거나 출력합니다.

C++ 구현 코드

아래는 위 알고리즘의 동작을 보여주는 전체 프로그램입니다.

#include <iostream>
using namespace std;

struct doublyLL {
    char val;
    struct doublyLL *next;
    struct doublyLL *prev;
};

void insertNode(struct doublyLL** head_ref, int value){
    struct doublyLL* new_node = new doublyLL;
    new_node->val = value;
    new_node->next = (*head_ref);
    new_node->prev = NULL;
    if ((*head_ref) != NULL)
        (*head_ref)->prev = new_node;
    (*head_ref) = new_node;
}

int calcDLLSize(struct doublyLL *temp) {
    int length = 0;
    while (temp != NULL){
        temp = temp->next;
        length++;
    }
    return length;
}

int main(){
    struct doublyLL* head = NULL;
    insertNode(&head, 'A');
    insertNode(&head, 'H');
    insertNode(&head, 'E');
    insertNode(&head, 'K');
    insertNode(&head, 'M');
    insertNode(&head, 'S');

    cout<<"이중 연결 리스트의 크기는 "<<calcDLLSize(head);

    return 0;
}

실행 결과

이중 연결 리스트의 크기는 6

코드 설명

  • insertNode 함수 – 새 노드를 리스트 맨 앞에 삽입하는 함수입니다. 새 노드의 next를 기존 head에 연결하고, 기존 head의 prev를 새 노드로 설정하여 양방향 연결을 유지합니다.
  • calcDLLSize 함수 – head부터 시작해 next 포인터를 따라 끝까지 이동하면서 노드 개수를 세는 함수입니다. 시간 복잡도는 O(n)입니다.

이처럼 이중 연결 리스트의 크기 구하기는 단일 연결 리스트와 동일하게 선형 순회 방식으로 해결할 수 있으며, 추가적으로 prev 포인터를 활용하면 역방향 순회도 손쉽게 구현할 수 있다는 장점이 있습니다.