자료구조 - 배열

짧은 서론 : 

11월은 자료구조와 알고리즘에 충실하게 공부해보자는 의미의 달로 정했다. 

이번주부터 시작한 자료구조 스터디에서 배운 내용을 블로그에 최대한 나의 언어로 잘 정리하는 것이 목표.

 

배열

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

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

 

배열의 특징

- 고정된 크기를 가지며 일반적으론 동적으로 크기를 늘릴 수 없다.

(다만, 내가 주로 사용하는 자바스크립트처럼 대부분의 스크립트 언어는 동적으로 크기가 증감되도록 만들어졌다.

내가 자바를 배웠을 때는 어레이의 크기와 어레이에 들어갈 타입을 미리 지정해서 선언했던 걸로 기억한다.
자바스크립트에선 한 어레이에 스트링, 넘버 다 들어갈 수 있다.)

 

- 원하는 원소의 index를 알고 있다면 O(1)로 원소를 찾을 수 있다. (인덱스 넘버만 알면 바로 탐색이 가능하니까)

 

- 원소를 삭제하면 해당 index에 빈자리가 생긴다. 

 

 

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

이유는, 배열은 중간 중간 삭제나 추가를 하기위해서 뒷 혹은 앞 요소를 하나씩 옮기는 작업 시간이 필요하기 때문이다.

JS에서의 배열의 특이점

- JS에서 배열의 index는 꼭 숫자가 아니어도 된다. (const arr = ["key" : 3])

- 단 숫자가 아닌 값을 배열의 index로 넣었을 경우 length에 포함되지 않는다는 특이점이 존재한다.

- ex) arr['key'] = 3

- arr.length = 0 (길이에 포함되지 않으므로)

- ex) [1, 2, 3, 'key' : 4] // 해당 배열의 lenght는 3으로 나옴

 

 

코드로 보는 배열 요소 추가, 삭제

const arr = [1, 2, 3]
console.log(arr);

// 4가 끝에 추가됨
arr.push(4); // O(1)

// 여러 개를 한 번에 추가할 수 있음
arr.push(5, 6) // [1, 2, 3, 4, 5, 6]
console.log(arr); 

// 3번 인덱스에 128을 추가한다.
arr.splice(3, 0, 128); // [1, 2, 3, 128, 4, 5, 6]

 

코드로 보는 JS 배열의 특징

// 자바스크립트의 Array는 다른 언어의 Array와 조금 다르다
// 자바스크립트의 Array는 동적이다.
const arr = [];
console.log(arr);
arr.push(1);
arr.push(1);
arr.push(2);
arr.push(3);
console.log(arr); // [1, 1, 2, 3]

arr.length // 4
// index가 number가 아니어도 된다.
arr["string"] = 10;
arr[false] = 0;

[1, 1, 2, 3, string: 10, false : 0]
arr.length // 4 (단 길이에 포함되지 않는다.)