3. 프로젝트를 진행하면서 얻은 인사이트 정리.md

1. 왜 여러 자료구조는 포인터 값을 저장하는가?

배경

• 과거에는 동적 배열을 구현할 때 구조체나 여러 배열을 포인터 없이 한 줄로 구현했습니다.
  • 간접 참조가 없으면 더 빠르고 메모리 효율적이라고 생각했습니다.
  • 그러나 여러 문제를 겪으며 다른 언어들이 자료구조를 저장할 때 포인터 값을 사용하는 이유를 알게 되었습니다.

문제점

1. 1차원의 큰 메모리 공간 문제
   • 큰 데이터를 사용하는 배열은 연속된 큰 메모리 공간이 필요함.
   • 구조체가 매우 클 경우, 연속된 공간을 할당받기 어려울 수 있다.
2. 데이터 반환 문제 (get 연산)
   • 배열에 연속된 구조를 저장하면 해당 부분의 포인터 값을 반환하는 방식으로 구현함.
   • 이 경우 배열이 변경되면 get으로 참조하는 데이터가 손상될 수 있습니다.
   • 동적 할당을 통해 새로운 공간을 만들어 반환하는 방법도 있는데, 이는 get 연산마다 새로운 공간을 할당해야 하며, 큰 구조체의 경우 비효율적이다. (메모리 할당 낭비?와 할당으로 인한 오버헤드)
3. 이해하기 어렵다.
   • 요소 추가 시, 기존 데이터를 그대로 두고 복사하는 방식을 사용했는데, 이렇게 데이터가 복사되는 방식은 직관적이지 않고 복잡하다.

• 포인터 값 사용 시 장점
  • 관리 편리성
    • 항상 같은 크기(포인터 크기)를 사용하므로 관리가 편리함.
    • 원본 데이터를
  • 메모리 분리
    • 값 반환 후에도 자료구조가 변경되어도 유효하다.
    • get 등을 사용하여 요소를 반환할 때 항상 같은 데이터(포인터)를 반환한다.
    • 메모리 파편화가 있는 환경에서도 잘 동작한다. 큰 연속된 메모리 공간이 필요하지 않다.
• 단점
  • 간접 참조로 인한 성능 감소
    • 그러나 다양한 타입(크기)의 데이터를 받는 범용 자료구조에서는 메모리 문제를 고려할 때 포인터 값을 저장하는 것이 합리적이다.

인사이트

• 포인터(참조)를 왜 사용하는지 더 이해할 수 있었다.
  • 메모리 효율성, 데이터 일관성(여러 곳에서 같은 데이터 참조), 관리 편의성(어떤 타입이든 동일한 크기)
  • 자료구조가 포인터 값을 사용하면 간접 참조로 인해 약간 느려질 수 있지만, 데이터 관리와 메모리 관리 면에서 더 편리하다.
    • Java나 C++ 같은 언어가 간접 참조를 사용하는 이유도 아마 비슷하지 않을까?
    • 단, Java의 AtomicReference<Integer>와 AtomicInteger의 성능 차이를 보면 간접 참조와 직접 참조의 성능 차이는 무시할 정도는 아닌 것 같다. (물론 이건 간접참조와 직접참조의 정확한 비교는 아니다. ==와 equals의 비교지)
    • 관련 된 이슈
  • 또 이해하기도 더 쉽다고 생각한다.
    • 데이터가 복사되거나 통채로 메모리가 이동되는 방식보다는 참조(포인터)를 저장하는게 사용하는 입장에서 더 편리하고 좋다.
• 자료구조의 요소의 효율적인 메모리 해제에 관해서 이해하였다.
  • C++에서는 자료구조를 delete하면, 자료구조가 가지고 있는 포인터 주소를 free 해버린다.
    • 이러면, 이전 시점에 get해서 가져온 데이터를 자료구조가 delete 된 시점 이후에 읽으면 에러가 발생한다. (막기 위해선 값을 복사해야 한다.)
      • managed 언어(Java)에 익숙한 나는 이게 이상하다고 생각해서 다른 식으로 구현하려고 했는데, 메모리 관리 관점에서는 이게 더 명확하다고 생각하게 되었다.
  • 자료구조를 구현하면서 이런 메모리 관리를 고민했는데, 고민한 내용은 다음과 같다.
    • 반환 시 복사한 객체 반환: get 시마다 데이터가 복제됨. 1억번 하면 데이터 1억게
    • 포인터 값 반환: free이후 시점에 접근하면 에러
    • 위에서 말했다시피, 후자가 C++에서도 채택하고 있고, 메모리 관리 관점에서 더 자연스럽다.