연속된 자료 구조와 연결된 자료구조

https://www.aladin.co.kr/shop/wproduct.aspx?ItemId=257288899

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

본 책을 사용하여 공부하는 내용이고 해당 글은 상업적으로 배포하고자 하지 않고 개인 공부용입니다

 

• 자료구조를 제대로 이해하고 있으면 응용 프로그램의 성능 향상, 표준화, 가독성, 유지 보수 등의 관점에서 유리하게 데이터를 관리할 수 있음
• 선형 자료 구조(linear data structure)를 다루고 크게 연속된 구조와 연결된 구조로 나뉨

 

연속된 자료 구조와 연결된 자료 구조

 

• 시간복잡도를 통해 특정 작업을 수행하는 데 걸리는 시간을 데이터 크기에 대한 수식으로 표현함으로써 데이터 크기가 변경되면 연산 시간이 어떻게 변하는지 보여줌
• 즉, 내부에서 데이터를 어떻게 저장하여 사용하는가에 따라 연산의 시간 복잡도가 달라짐

 

연속된 자료 구조(Contiguous data structures)

• 모든 원소를 단일 메모리 청크에 저장함

• 4개의 상자를 곧 단일메모리 청크로 생각하면 되고 각 상자는 각 원소가 저장된 메모리 공간을 의미함
• 각 원소는 모두 같은 데이터 타입으로 이루어짐
• 같은 데이터 타입은 같은 크기의 메모리를 사용하므로 i번째 원소에 접근하고자 하면 BA+i * sizeof(type) 수식을 사용함
• 배열의 크기에 상관없이 접근할 수 있어서 데이터 접근 시간은 항상 일정하고 이 경우 빅오(Big-O)표기법에 의해 O(1)로 표시함
• 한편, 배열은 정적배열과 동적배열로 나눌수 있음
• 정적 배열은 선언된 블록이 끝나면 소멸되는 반면, 동적 배열은 프로그래머가 생성할 시점과 해제할 시점을 자유롭게 결정할 수 있음
• 두 배열의 유형 모두 다양한 연산에서 동일한 성능을 나타냄
• 정적배열 int arr[size];
• 동적배열 int* arr=new int[size];
• cf) 정적배열은 스택(stack)메모리 영역에 할당되기 때문에 함수를 벗어날 때 자동으로 해제되지만, 동적배열은 힙(heap) 영역에 할당되기 때문에 사용자가 직접 해제하기 전까지 유지됨
• 배열과 같은 연속된 자료 구조에서 각각의 원소는 인접하여 있어서 한 원소에 접근할 때 그 옆에 있는 원소 몇 개도 함께 캐시(cache)로 가져옴 -> 캐시 지역성(cache locality)
• 이는 연산의 점근적 시간 복잡도(asympototic time complexity) 계산에는 영향을 주지 않지만 실제 동작에서 배열처럼 연속된 원소에 매우 빠르게 접근할 수 있다는 점이 큰 장점으로 작용함
• 배열에서 모든 원소에 순차적으로 접근한다면 인접 원소에 바로 참조할 수 있어서 배열 자료형은 캐시지역성이 좋다고 말할 수 있음

 

연결된 자료 구조(Linked data structure)

 

 

• 노드라고 하는 여러 개의 메모리 청크에 데이터를 저장하고 서로 다른 메모리 위치에 저장됨
• 아마, 연속된 자료구조에서 +로 수식화된다는 것과는 다르다고 말하는 것 같음
• 위 그림과 같은 형태를 연결 리스트(linked list)라고 함
• 연결 리스트의 기본 구조에서 각 노드는 저장하는 데이터와 다음 노드를 가리키는 포인터(next)를 가지고 있음
• 맨 마지막 노드는 NULL을 가짐
• 따라서 앞서와 다르게 i번째에 접근하기 위해서는 연결 리스트 내부에서 i 번 이동하는 작업이 필요하고 원소 접근 시간은 노드 개수에 비례하며, 시간 복잡도로 표현하면 O(i)임
• i-1번 이동하는게 아닌가?
• 만약 연결 리스트에 새로운 원소를 추가하고 싶다면? 포인터를 이용하면 매우빠르게 삽입(그리고 삭제) 수행할 수 있음

• 새로운 원소를 삽입하기 위해서 일단 새로운 노드(박스)를 먼저 생성해야 함
• 각 노드의 next 포인터를 수정해야 함
• 새로 추가한 노드의 포인터가 다음 노드를 가리키게 하고
• 이전의 1=3 관계를 제거하고
• 1이 2를 가리키도록 설정함
• 추가가 아니고 제거라면 비슷한 과정으로 진행하면 됨
• 연결 리스트는 연속적으로 저장되지 않기 때문에 캐시 지역성을 기대할 수 없음
• 인접성을 보장할 수 없고 다음 노드에 방문하기 위해서는 이전 노드에 방문을 해야한다는 뜻이지
• 배열과 같은 연결 리스트에서 모든 원소를 차례대로 방문하는 작업은 이론상 같은 시간복잡도를 가지지만 실제로는 연결 리스트의 성능이 떨어지는 것임

연속된 자료 구조	연결된 자료 구조
모든 데이터가 메모리에 연속적으로 저장됩니다.	데이터는 노드에 저장되고, 노드는 메모리 곳곳에 흩어져 있을 수 있습니다.
임의 원소에 즉각적으로 접근할 수 있습니다.	임의 원소에 접근하는 것은 선형 시간 복잡도를 가지며 느린 편입니다.
데이터가 연속적으로 저장되어 있고, 캐시 지역성 효과로 인해 모든 데이터를 순회하는 것이 매우 빠릅니다.	캐시 지역성 효과가 없으므로 모든 데이터를 순회하는 것이 느린 편입니다.
데이터 저장을 위해 정확하게 데이터 크기만큼의 메모리를 사용합니다.	각 노드에서 포인터 저장을 위해 여분의 메모리를 사용합니다.

▲ 그림 1-4 연속된 자료 구조와 연결된 자료 구조의 비교

 

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

▲ 그림 1-5 다양한 연산에 대한 배열과 연결 리스트의 시간 복잡도