[CS] 자료구조 1. 배열

선형 자료구조란?

선형 자료구조는 데이터가 저장되고 만들어지는 구조가 일직선상으로 존재하기에 붙은 이름이다. 

크게 배열, 벡터, 리스트, 스택, 큐 정도를 다뤄보려고 한다. 

---

배열

배열은 인덱스를 가지고 각 인덱스마다 값을 하나씩 저장하는 구조이다. 

같은 타입의 변수를 가지고, 크기가 정해져 있으며, 데이터를 인접한 메모리 위치에 저장한다. 중복을 허용하며 순서(인덱스)를 가진다. 

특징으로는 랜덤 접근이 가능하다. 즉, 랜덤으로 인덱스를 주었을 때 이를 바로 찾아올 수 있다는 뜻이다.

(이렇게 말하는 것은 이러지 못하는 녀석이 있다는 뜻!)

추가 

위에서 배열의 크기가 정해져 있다고 했다. 

그러면 데이터를 추가할 때에는 어떻게 해야할까?

새로운 배열을 만들고, 내가 집어넣으려는 인덱스 이전까지의 배열을 복제한다. 

넣을 데이터를 해당 인덱스에 넣고, 그 다음 인덱스부터 끝까지는 이전 배열에서 복제해와야 한다. 

길이가 n인 배열에 하나의 값을 추가하려면, 배열을 n+1의 길이로 초기화시키고 n개를 전부 복사해오고 추가하는 것 하나가 존재한다. 

결국 O(n)의 시간 복잡도가 발생한다. 

 

조회 

데이터를 조회할 때에는 위에서 말했던 대로 랜덤 접근이 가능하다. 

즉, 보려고 하는 인덱스가 있다면 바로 찾아올 수 있다. 

O(1)의 시간 복잡도를 가진다. 

 

삭제

한 인덱스에서 값을 지우고, 배열이 줄어들기 위해서 n-1개의 배열을 만든 후, 여기에 지우려는 값을 제외하고 모두를 하나씩 인덱스마다 초기화시켜주어야 한다. 

O(n)의 시간복잡도가 발생한다. 

 

총평

조회에 최적화되고, 추가와 삭제에 시간이 많이 쓰이는 구조인 것 같다. 

알고리즘을 풀 때, 크기가 정해져 있고 인덱스의 값을 사용하거나 수정하는 경우에 쓰기 좋은 자료구조같다.