[자료구조] 1-1. 배열, 순차 리스트(Array, Sequential List)

배열

배열은 같은 자료형의 변수들을 각각 순차적으로 이은 자료구조이다.

 

배열이 가지고있는 자료의 순서와 메모리상에 저장된 자료의 순서가 일치한다.

 

배열을 각각 구성하는 값을 요소(element)라고 하고, 배열 내에서 요소의 위치값을 인덱스(index)라 한다.

 

배열 A에서의 인덱스 i값은 A[i]로 표기한다.

 

일반적으로 배열이라 하면, 크기가 정해진 정적 배열(Static Array)라고 한다.

 

순차 리스트

순차 리스트는 배열과 같은 개념이나, 하나 다른 점이 있다.

 

크기가 정해지지 않은 동적 배열(Dynamic Array)라는 것이다.

 

기존 배열보다 더 많은 요소들을 받아야 할 때,

크기가 더 큰 새로운 배열을 만들어 기존 배열을 복사하고, 새로 받는 값들을 추가시킨다.

 

C언어의 벡터, 파이썬의 리스트에서 대표적으로 사용되고있다.

 

접근

주어진 인덱스 값에 대한 데이터를 찾는 연산이다.

 

(찾으려는 메모리주소의 값) = (배열/리스트의 시작 메모리 주소 값) + (인덱스)*(자료형의 크기) 으로,

 

만약 인덱스[3]의 데이터를 찾으려면, 0 - 1 - 2 - 3 순차적으로 검색하는것이 아닌,

 

시작 메모리 주소 값에서 목표 인덱스까지 점프해서 데이터를 찾는다.

 

계산이 한 번 뿐이니 시간복잡도는 O(1)이다.

 

추가

배열/순차 리스트에서 맨 뒤에 새로운 변수를 추가하는 연산이다.

 

배열/순차리스트에서 맨 뒤에 공간만 있다면 마지막 다음 칸에 값을 삽입하면 된다.

 

시간복잡도는 O(1)이다.

 

만약, 순차 리스트가 더 이상 공간이 없을 경우, 새로운 배열을 생성하여 기존 배열을 옮기고 추가해야한다.

옮기는 연산 자체는 O(1)이나, 이 과정을 n번 반복해야 하므로 시간 복잡도는 O(N)이다.

 

삽입

배열의 중간에 요소를 추가하는 연산이다.

 

삽입을 하려면, 그 인덱스 뒤의 모든 값들을 밀어내야 한다. 요소 하나를 밀어내는데 O(1)이 걸리고,

최악의 경우(맨 앞에 삽입하는경우), N-1개의 요소를 밀어내야 하므로 시간복잡도는 O(N)이다.

 

삭제

삽입의 반대순이다. 뒤 인덱스의 값들을 모두 앞으로 당겨와야 하므로, O(N)의 시간복잡도가 걸린다.

만약, 맨 뒤의 인덱스값을 삭제하는경우, O(1)의 시간이 걸린다.

 

탐색

정렬되지 않은 배열에서 찾으려는 값을 처음부터 찾는 것이다.

최악의 경우, 0번에서 N번까지 탐색하므로 시간 복잡도는 O(N)이다.