[알고리즘] 배열( 순차 리스트)

1. 배열

연관된 데이터를 연속적인 형태로 구성된 구조를 가진다. 

배열에 포함된 원소는 순서대로 번호(index)가 붙는다. 

특징 

• 고정된 크기를 가지며 일반적으론 동적으로 크기를 늘릴 수 없다.
  - 자바스크립트처럼 스크립트 언어의 경우 동적으로 크기가 증감되어진다. 
• 원하는 원소의 index를 알고 있다면 O(1)로 원소를 찾을 수 있다. 
• 원소를 삭제하면 해당 index에 빈자리가 생긴다. 

2. 배열의 요소 삭제

[1, 1, 2, 3, 5, 7, 10, 13, 34] 인 배열이 있다. 여기서 7을 제거할 경우 진행되는 방법을 보자면 

 

1.  7이 삭제된다. 

 => [1, 1, 2, 3, 5, `  `, 10, 13, 34]

 

2. 10이 앞으로 한칸 이동한다. 

 => [1, 1, 2, 3, 5, 10, `  `, 13, 34]

 

3. 13이 앞으로 한칸 이동한다. 

 => [1, 1, 2, 3, 5, 10, 13, `  `, 34]

 

4. 34가 앞으로 한칸 이동한다.

 => [1, 1, 2, 3, 5, 10, 13,  34,`  `]

 

총 4번의 작업이 진행되었는데, 만약 첫 번째 인자가 삭제되는 최악의 경우엔 O(n)의 시간 복잡도를 가지게 된다. 

 

3. 배열의 중간에 요소 추가

마찬가지로 [1, 1, 2, 3, 5, 7, 10, 13, 34] 인 배열이 있다. 여기서 7 앞에 요소 50을 추가할 경우 진행을 보자면

 

1. 34가 뒤로 한칸 이동한다. 

=> [1, 1, 2, 3, 5, 7, 10, 13, ` ` , 34] 

 

2.  13이 뒤로 한칸 이동한다. 

=> [1, 1, 2, 3, 5, 7, 10, ` `, 13 , 34] 

 

3. 10이 뒤로 한칸 이동한다.

=> [1, 1, 2, 3, 5, 7, ` `, 10, 13 , 34] 

 

4. 7이 뒤로 한칸 이동한다. 

=> [1, 1, 2, 3, 5, 50, 7, 10, 13 , 34] 

 

만약 첫 번째 인자에 요소를 추가할 경우 O(n)의 시간 복잡도를 가지게 된다.

 

따라서 추가와 삭제가 반복되는 로직이라면 배열 사용을 권장하지 않는다.

배열은 탐색이 많은 경우 유리하다. 

 

 

4. 배열 생성

5. 배열 요소 추가, 삭제 

6. 배열의 특이점

특이점으로 자바스크립트의 배열은 HashMap에 가깝다. 

index가 number가 아닌 string, boolean이더라고 key값이 string을 둔 속성값으로 선언할 수 있다.