C++로 다시 구현하는 자료구조 #0 DataStructure

갑자기 왜 이짓거리 다시하고 있냐 싶을 순 있는데 내가 배웟던 것들좀 다시 정리할려고 한다. 

이전에 만들어놓은거 보니까 성능이고 나발이고 전부다 연결 리스트로 구현해놨더라고?

참고하는 자료는 다음과 같다.

자바로 배우는 쉬운 자료구조

자바로 배우는 쉬운 자료구조 | 이지영 - 교보문고

널널한 개발자 - 자료구조

자료구조(DataStructure)란?

우리가 다루는 데이터는 항상 같은 형태로 존재하지 않는다.  

어떤 건 단순히 숫자 몇 개를 나열하는 것만으로 충분하고,  

어떤 건 다양한 속성들이 얽힌 복합적인 구조를 필요로 한다.

예를 들어, 게임 속 캐릭터를 생각해보자.  

캐릭터는 HP, MP, 이동속도와 같은 여러 수치들을 갖고 있다.  
이 각각의 수치는 `int`, `float` 같은 기본 자료형으로 표현될 수 있지만,  
그 캐릭터 하나를 온전히 정의하려면 이 수치들을 어떤 구조로 묶을지를 결정해야 한다.

이 복잡하고 다양한 데이터를 어떻게 정의하고 나열하여 찾아내어 사용할 것에 대한 것이 바로 자료구조의 시작이다.

자료구조를 어떻게 구성하느냐에 따라 프로그램의 실행 속도가 천차만별로 차이가 나게 되는데,

그 이유는 메모리 구조와 데이터에 대한 접근 방식, 그리고 캐시 효율성에 있다.

그리고 내가 이 스터디 섹션을 다시 공부하게 된 이유도 여기 이 성능에 관한 고려가 필요해져서 그렇다.

예전에는 모두 연결 리스트로 구현해 놓았다고 했다. 

연결 리스트는 뒤에서 다시 이야기 하겠지만, 성능이 그렇게 좋지는 못하다.

CPU가 데이터를 처리하는 방식은, 단순히 메모리에 접근해서 값을 가져오는 게 아니라,
캐시 → RAM → 디스크라는 계층적 구조를 따라 점점 느려지는 저장 장치를 순차적으로 조회하는 방식으로 동작한다.

예를 들어, 배열처럼 메모리 상에 연속된 공간에 데이터를 저장하는 구조는
**CPU의 캐시 지역성(Locality of Reference)**에 매우 유리하다.
같은 주소 근처의 데이터를 연속적으로 접근할 가능성이 높아 캐시 히트율이 상승하고,
이는 곧 메모리 접근 시간의 비약적 단축으로 이어진다.

반면, 연결 리스트는 삽입과 삭제에는 유리하지만,
노드들이 메모리 상에서 불연속적으로 배치되기 때문에 캐시 효율이 매우 떨어진다.
실제로 반복적인 캐시 미스가 발생하면, CPU는 L1 → L2 → L3 캐시를 거쳐 RAM까지 조회하게 되는데,
RAM 접근조차 실패하면 OS는 페이지 폴트(Page Fault)를 발생시켜 디스크(I/O 장치)에서 데이터를 불러오게 된다.
이 단계에 도달하면 속도는 수십~수천 배까지 느려질 수 있다.

보통 이런 경우는 Loading이라는 시퀀스를 통해 제어되거나 부족한 메모리를 사용하기 위해 가상 메모리를 사용하고 있는 경우가 해당된다. 

이렇듯, 자료구조는 단순히 논리적 구조를 넘어서 하드웨어 계층 구조와 깊은 연관을 갖는다.

때문에 이번 스터디에서는 단순한 동작 구현이 아니라,

"어떻게 메모리와 캐시를 효율적으로 활용할 것인가"를 고려한 관점에서 자료구조를 다시 정비하고자 한다.

자료구조를 공부할 때 가장 먼저 접하는 분류는 바로
선형(Linear) vs 비선형(Non-linear) 구조의 구분이다.

이 분류는 단순히 ‘모양’만을 기준으로 한 것이 아니라, 데이터 간 관계와 접근 방식의 구조적 차이를 의미한다.

선형 자료구조 (Linear Data Structure)

선형 자료구조는 데이터를 메모리 상에 일렬로 나열한다.

선형 자료는 대부분의 자료가 배열의 형태로 구현된다.

때문에 필연적으로 다음 데이터가 항상 바로 옆에 존재하고, 캐시 히트율이 상승한다.

 

• 배열 (Array)
• 스택 (Stack)
• 큐 (Queue)
• 연결 리스트

 

비선형 자료구조 (Non-Linear Data Structure)

비선형 자료구조는 데이터를 메모리의 어떤 공간 내에 임의 할당한다.

주소를 기반으로 논리적으로 연결하는 형식으로 구현된다.

때문에 다음 데이터가 항상 이전 데이터와 인접한 한것이 보장되지 않기 때문에 캐시 미스율이 상승한다.

주로 데이터간의 관계를 표현하는 것이 중요할 때 사용되는 자료구조이며,

데이터간 관계가 일대일이 아닌 일대다 혹은 다대다의 관계를 갖는 복잡한 자료를 표현할 때 사용한다.

 

• 트리 (Tree)
• 힙 (Heap)
• 그래프 (Graph)
• 트라이 (Trie)
• 해시

이렇게 선형 구조와 비선형 구조를 논리적으로 나눠 놨지만...

실제 구현은 대부분 배열 기반이다

논리적으로는 선형/비선형으로 나누지만, 실제 구현 단계에서는 배열이 가장 많이 사용된다.
이는 메모리 지역성과 성능 최적화 때문이다.

예를 들어:

• 스택, 큐, 리스트는 당연히 배열로 쉽게 구현 가능하며,
• 트리나 힙도 완전 이진 트리 구조일 경우, 인덱스 규칙(i, 2i+1, 2i+2)을 기반으로 배열에 순차적으로 배치할 수 있다.
• 그래프 역시 인접 행렬(2차원 배열) 또는 인접 리스트(배열 + 연결 리스트) 형태로 표현 가능하다.

즉, 논리적 구조는 비선형일지라도,
메모리 지역성과 성능을 위해 실제 구현은 선형적 메모리 구조(배열)로 선택되는 경우가 많다.

실습 코드는 제 깃허브에 있습니다.

Workspace/자료구조 at main · cyphen156/Workspace · GitHub

Workspace/자료구조 at main · cyphen156/Workspace