읽고 나면 진짜 쉬워지는 자료 구조 - 3. 동적 자료 구조

데이터가 변경될 때 구조를 변경하는 동적 자료 구조

🔖 3.1 배열의 한계

배열은 정적이다?

• 책에서는 '배열' 이라는 용어를 단순히 정적 배열을 가리키는 용어로 사용한다. 물론 애플리케이션에 따라 변할 수 있는 동적 자료 구조보다는 덜 동적이긴 하지만, 구현 방식에 따라 배열도 동적으로 될 수 있다는 점을 기억하자.

• 예를 들어, JavaScript에서는 배열이 push()나 pop()에 따라 크기가 동적으로 변한다. 따라서 배열은 무조건 정적이다 라고 하기엔 어렵다.

• 이처럼 배열은 요소의 추가/삭제가 가능하긴 하지만 메모리 사용이 예측하기 어려울 수 있고, 무엇보다 배열을 재할당하고 요소를 복사하는 과정에 시간복잡도가 커질 수 있다.

책에서 말하는 배열의 한계

• 메모리 레이아웃이 고정된, 즉 크기가 고정된 자료 구조의 근본적인 한계다.

• 이렇게 고정된 자료 구조는 데이터에 따라 자료 구조의 크기가 늘어날 수 없다. 이 한계로 몇 가지 일반적인 작업이 비싸진다.

• 배열 크기는 배열을 생성할 때 고정되므로 배열을 확장해 더 많은 데이터를 저장하려면 새로운 더 큰 메모리 블록을 만들어야 한다. 이는 큰 부가 비용이다.

배열이 중간에 새로운 항목을 쉽게 삽입할 수 없는 이유

• 배열은 메모리 상에서 연속된 공간에 저장된다. 앞 장에서 이야기했듯 배열의 각 요소는 서로 인접한 메모리 위치에 저장되어 고정된 인덱스를 통해 빠르게 접근할 수 있다.

• 중간에 요소를 삽입하려면 기존의 요소를 밀어내야 한다. 따라서 O(N)의 시간 복잡도를 가진다.

• 연결 리스트는 노드 간의 포인터를 조정하면 데이터 이동이 필요 없으므로 O(1)이지만, 배열은 연속된 메모리 구조로 인해 요소를 밀어내야 한다.

🔖 3.2 포인터와 참조

포인터의 개념

• 평소 포인터 개념을 잘 이해하지 못했다. 그리고 변수에 "나 여기 있어" 라는 정보를 아예 저장하면 되지 않나? 생각했는데, 책에서 든 비유가 찰떡이다.

• 프로젝트 폴더에 있는 여러 서류를 열린 공간에 두지 않고, 동료들에게 "3층 기록 보관실 두 번째 서류함에 있다" 라는 메모를 남긴다. 이것이 포인터 역할이다.

• 또한 이 단일 주소를 여러 동료들과 공유할 수 있어 파일 전체 복사본을 만들 필요가 없다.

• 이 포인터는 연결 리스트에 쓰이는 메모리 블록을 연결하는 매커니즘을 제공한다.

🔖 3.3 연결 리스트

배열과 닮은 연결 리스트

• 연결 리스트는 배열과 마찬가지로 여러 값을 저장하는 자료 구조다.

• 그러나 배열과 달리 연결 리스트는 포인터로 연결된 노드의 사슬로 구성된다.

• 연결 리스트의 기본 노드는 어떤 타입의 값이든 포함할 수 있는 값, 그리고 리스트의 다음 노드를 가리키는 포인터로 구성된다.

• 각 원소를 저장하기 위해 값과 포인터를 함께 포함하므로 배열보다 더 많은 메모리를 사용한다. 하지만 포인터가 가진 유연성을 위해 메모리 사용 증가를 감수할만한 가치가 있다.

• 그리고 배열과는 다르게 노드가 인접하지 않아도 된다. 즉, 포인터 덕분에 연속적인 메모리 블록에 위치해야 할 필요가 없다.

🔖 3.4 연결 리스트에 대한 연산

음..

• 이 부분은 요약하기 어려워 책을 직접 읽어보는 게 낫겠다.