[자료구조 in C++] 연속된 자료구조와 연결된 자료구조

자료구조의 중요성

응용 프로그램을 설계할 때 데이터 관리는 필수적 요소이다. 특히, 요즘 빅데이터 시대라고 불리는 만큼 데이터 관리는 더욱더 중요하게 고려되어야 할 항목이다.

 

프로그래머는 데이터를 메모리에 저장하기 위해 여러 자료 구조를 활용할 수 있다. 프로그램에서 필요한 기능을 구현하고, 동작 성능과 안정성을 확보하려면 적절한 자료구조$($Data Structure$)$ 를 선택하여야 한다.

 

자료구조는 크게 연속된 자료구조와 연결된 자료구조로 분류할 수 있다.

 

시간 복잡성$($Time Complexity$)$

 

데이터를 처리하기에 앞서 데이터를 어떠한 형태로 저장할 것인가가 결정되어야 한다. 이를 결정하기 위한 적합한 지표들이 몇 가지 있는데, 대표적으로 알고리즘 복잡도 혹은 시간복잡도$($Time Complexity$)$ 가 있다.

 

시간 복잡도란 특정 작업을 수행하는 데 소요되는 시간을 데이터 크기에 대한 함수로 표현한 것이다. 표기법으로는 빅-오 함수를 사용한다.$$O(n)\ (n: Data\ Size)$$

 

 

1. 연속된 자료구조

연속된 자료구조는 모든 원소를 단일 메모리에 저장한다.

 

출처: https://0xd00d00.github.io/2021/08/26/coding_test_cpp_2.html

 

 

위 그림을 예시로 들자면,

• 크기가 4인 메모리 
• 배열이므로 모두 동일한 데이터 타입
• 첫번째 원소의 메모리 주소: BA
• $i$ 번째 주소에 접근하고자 한다면 BA + sizeof$($type$)$ $\times i$
• 이 경우, 배열 크기에 상관없이 위 수식을 이용해 모든 원소에 접근 가능하므로 시간복잡도는 $O(1)$ 로 일정

 

여기서 잠깐, 배열에 관해 간단히 설명하자면,

 

배열에는 정적 배열과 동적 배열이 존재한다. 정적배열은 선언된 블록이 끝나면 소멸되기 때문에 함수를 벗어나는 순간 자동으로 해제되는 반면, 동적 배열은 프로그래머가 생성과 소멸 시점을 자유롭게 결정할 수 있다.

 

▶C/C++ 에서 배열을 선언하는 방법

• 정적 배열: 

int arr[size];

 

• C언어 동적 배열:

int* arr = (int*)malloc(size * sizeof(int));

 

• C++ 동적 배열

int* arr = new int[size];

 

 

배열과 같은 연속된 자료구조에서 각 원소는 서로 인접해 있기 때문에 하나의 원소에 접근할 때 그 옆에 있는 원소 몇 개도 함께 캐시$($cache$)$로 가져온다. 그러므로 다시 주변 원소에 접근할 때, 해당 원소를 캐시에서 가져오게 되며, 이 작업은 매우 빠르게 동작한다.  

 

이는 연산의 점근적 시간 복잡도$($asympototic time complexity$)$ 계산에는 영향을 주지 않지만 실제 동작에서 배열처럼 연속된 원소에 매우 빠르게 접근할 수 있다는 장점이 있다.

 

그러나 배열의 경우, 단일 메모리 청크로 되어 있기 때문에 데이터를 삽입하거나 삭제하는 경우, 배열 전체를 밀어내거나 앞당겨야 하는 문제점이 있다. 이러한 문제점을 해결할 수 있는 것이 연결된 자료구조이다.

 

 

2. 연결된 자료구조

연결된 자료구조는 노드$($node$)$라고 하는 여러 개의 메모리 청크에 데이터를 저장한다. 이 경우, 서로 다른 메모리 위치에 데이터가 저장된다.

 

출처: https://0xd00d00.github.io/2021/08/26/coding_test_cpp_2.html

 

위 그림을 보면,

• 위와 같은 형태를 연결 리스트라고 한다
• 연결 리스트에서 각 노드는 저장할 데이터$($data$)$와 다음 노드를 가리키는 포인터$($next$)$를 가지고 있다
• 맨 마지막 노드는 포인터 대신 NULL을 가지고 있다
• 연속된 자료구조와 달리, 원소 개수만큼 메모리가 존재하므로, $i$번째 원소에 접근하려면 $i$ 번 이동해야 한다
• 시간 복잡도는 $O(n)$이다.

 

만약 연결리스트에 새로운 노드를 추가하고자 한다면, 

 

출처: https://0xd00d00.github.io/2021/08/26/coding_test_cpp_2.html

 

1. 우선, 새로운 노드 생성
2. 각 노드의 next 포인터 수정
3. 새로 추가한 노드$($i=2$)$의 next 포인터가 다음 노드 $($i=3$)$ 를 가리키도록 함
4. 이전 노드 $($i=1$)$ 가 가리키던 것 $($i=3$)$ 을 제거하고, 새로운 노드 $($i=2$)$ 를 가리키도록 설정함

 

노드를 삭제할 때도 비슷한 방식으로 진행하면 된다.

 

 

최종 정리 

연속된 자료구조	연결된 자료구조
모든 데이터가 메모리에 연속적으로 저장	데이터는 노드에 저장, 노드는 메모리 곳곳에 흩어져 있음
임의의 원소에 즉각적으로 접근 가능	임의의 원소에 접근하는 것이 선형 복잡도를 가지며, 속도가 느릴 수 있음
캐시 지역성 효과로 인해 모든 데이터를 순회하는 것이 빠름	캐시 지역성 효과가 없으므로 모든 데이터를 순회하는 것이 느림
데이터 저장 시 정확히 데이터 크기 만큼의 메모리를 사용	각 노드에서 포인터 사용을 위해 여분의 메모리 사용

 

 

파라미터	배열	연결 리스트
임의 접근	$O(1)$	$O(n)$
맨 뒤에 원소 삽입	$O(1)$	$O(1)$
중간에 원소 삽입	$O(n)$	$O(1)$
캐시 지역성	있음	없음

 

 

참고 문헌

<a href="https://www.yes24.com/Product/Goods/95863013" > 코딩 테스트를 위한 자료 구조와 알고리즘 with C++ </a>

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ - 예스24