Chapter 1. DataStructure Intro

1. 자료구조란?

자료구조는 데이터들의 집합을 의미한다. 

'적절한' 자료구조란 데이터들을 효율적으로 저장을 하고, 필요 연산을 빠른 시간내에 처리함을 의미한다. 여기서 말하는 연산이란 보통 삽입/삭제/탐색을 의미하며 상황에 따라 자주 사용하는 연산들이 존재한다.

 

예를 들어, 로그 파일과 같이 삽입의 연산을  많이 하고 삭제, 탐색의 연산을 적게 한다면 Unsorted Array와 같이 삽입이 O(1)인 방식을 사용하면 좋다.

혹은, 교통망과 같이 네트워크 상의 현실 문제를 모델링 할 때 그래프와 같은 방식으로 자료를 저장하면 된다.

2. 자료구조의 분류

[그림 1] 자료구조 분류

여기서 말하는 선형구조란 데이터들을 선의 형태로 일렬로 저장하는 방식을 말하며, 비선형 구조는 데이터를 나란히 저장하지 않는 구조를 의미 한다.

3. ADT - Abstract Data Type

'제품 설명서'

구체적인 기능의 완성을 언급하지 않고, 순수하게 기능이 무엇인지를 나열한다. 즉, 내부에서 어떠한 복잡한 일이 일어나는지는 관심이 없고 기능과 사용방법을 정의 한다. ADT를 보면 "이 자료구조는 어떤 기능들이 있고 어떻게 사용하는구나"를 알 수 있다.

4. Array

같은 종류의 데이터 타입을 가진 데이터들을 주소상에 연속되게 모은 자료구조이다.

 

처음 데이터 선언 시 원소들의 갯수를 정해야 한다. 즉 공간을 미리 확보해야 한다. 만약 공간을 너무 크게 잡으면 메모리 낭비가 심하고, 공간을 적게 잡을 경우 중간에 배열의 크기를 수정하여 다시 재할당하는 상황이 발생한다. 이를 해결한 방식이 Vector ADT이다. [동적 자료구조]

 

또한, Array는 캐싱 기능 때문에 좋은 자료구조이다. 연속된 메모리 주소를 갖고 있어 구역성 이론에 따라 엑세스 메모리 근처에 값들을 캐싱하는 좋은 기술을 사용하기 때문이다.

이는 구역성 이론과도 밀접한 관계가 있다. 구역성 이론에는 공간 구역성 이론과 시간 구역성 이론이 있다.

공간 구역성 이론 : 메모리의 한 곳을 일단 엑세스하면 그 주변 데이터도 곧 이어 사용할 확률이 높다.

시간 구역성 이론 : 시간적인 관점에서 한 번 엑세스된 데이터는 곧 이어 다시 엑세스 될 확률이 높다.

 

삽입 : O(N) : 중간에 삽입을 하더라도 연속된 메모리 주소의 특징을 갖기 위해 원소를 Transfer 하는 Cost가 필요하다.
삭제 : O(N) : 데이터 끝에 값을 넣고 원소를 지우면, 배열의 원소를 Transfer해야 하므로 O(N)이다.
탐색 : 원하는 Index에 한 번에 접근할 수 있다. O(1)

 

※ 만약 Key값을 기준으로 탐색 하고 싶다면 O(n)이 소요 된다. 만약 메모리의 공간이 충분히 크다면 Hashing을 이용하여 기댓 값 O(1)에 수행 가능 하다.

 

※ Binary Search : Sorted Array에서 Key값을 O(log n)만에 탐색 할 수 있는 Search 방법이다. 이는 분할 정복과 비슷하게 데이터 크기를 1/2씩 줄여나가며 이를 그림으로 표현하면 높이가 O(log n)으로 나타낼 수 있다.

 

[그림 2] BST 시각화

5. Linked List

배열은 물리적 순서로 데이터를 할당하지만 링크드리스트는 논리적 순서로 데이터를 할당한다. 각 노드는 다음 노드를 가리키는 포인터를 가진다. 왜냐하면 연속된 메모리 주소를 갖지 않는 특징 때문이다.
배열은 원하는 데이터에 index로 한번에 접근 할 수 있지만 링크드 리스트는 O(1)에 element로 접근이 불가하여 Index로 탐색이 잦을 경우 비효율적이다.
하지만 데이터를 필요할때마다 동적으로 추가하여 데이터 크기를 변경할 수 있는 장점이 있다. 또한 데이터들 중간에 element를 삽입 혹은 삭제시 배열은 element들을 transfer하는 cost가 들지만 링크드 리스트는 변경할 item의 위치를 알고 있으면 O(1)에 데이터를 수정할 수 있다.

 

※ 배열, 링크드 리스트 모두 탐색 시 O(n)이지만 배열은 transfer cost이고 링크드 리스트는 탐색만 하면되므로 리스트가 속도면에서 조금 더 효율적이다.

삽입 : O(n) + O(1) : item의 위치를 찾는 O(n) + 삽입 O(1)
삭제 : O(n) + O(1) : item의 위치를 찾는 O(n) + 삭제 O(1)
탐색 : O(n) : Iterator 순환

만약 Hashing을 사용할 경우 O(1)에 수행된다. 혹은 Red Black Tree를 이용하면 OI(logn)에 수행된다.

 

※ 구현 방법

Singly Linked List

 

Doubleed Linked List

※ Array vs Linked List

메모리 관점

데이터의 갯수를 알고 미리 알고 있으면 배열이 좋다. 만약 데이터의 갯수를 잘 모른다면 링크드 리스트가 좋다. 데이터 1개의 크기는 다음 노드를 가리키는 포인터가 추가로 필요하기 떄문에 때문에 배열이 링크드리스트보다 좋다. 

 

연산 관점

중간에 삽입 / 삭제가 많을 경우 배열은 데이터를 Transfer하는 Cost O(n)이 필요하다. 링크드 리스트는 데이터를 탐색하는 과정에서 O(n)이 필요하다.

Transfer하는 비용보다 포인터를 이용한 탐색 연산의 Cost가 더욱 작기 때문에 중간에 삽입/삭제가 많을 경우 링크드 리스트가 효율적이다.

배열은 링크드리스트와 달리 Random Access가 O(1)이며 캐싱에 좋은 자료구조이다.

 

우리가 앞으로 배울 ADT들은 모두 배열 혹은 링크드리스트로 구현 한다.