배열 - JS

배열이란?

1. 가장 일반적인 구조
2. 메모리 상에 같은 타입의 자료가 연속적으로 저장됨
3. 자료값을 나타내는 가장 작은 단위가 자료를 다루는 단위

특징

• 같은 타입의 데이터를 나열한 선형 자료구조
• 연속된 메모리 공간에 순차적으로 저장
• 배열의 크기는 고정, 선언할 때에 배열의 크기를 정하고 변경할 수 없다(정적 표현)
• 인덱스를 이용하여 표현
• 지역성을 가지고 있음

시간복잡도

(1) 삽입/삭제

• 배열의 맨 앞에 삽입/삭제하는 경우: O(n)
• 배열의 맨 뒤에 삽입/삭제하는 경우: O(1)
• 배열의 중간에 삽입/삭제하는 경우: O(n)

(2)탐색

• O(1)

장점

• 인덱스를 가지고 있어 바로 접근 가능(시간복잡도 O(1))
• -자료구조의 크기가 클수록 더 강력한 장점
• 연속된 메모리 공간에 존재하기 때문에 관리하기가 편하다

단점

• 삽입과 삭제가 어렵고 오래 걸린다
• -원소를 삽입하거나 삭제할 경우, 해당 원소 이후의 모은 원소들을 한칸씩 밀거나 당겨야한다(연속된 메모리 공간에 저장되기 때문)
• 배열의 크기를 바꿀 수 없다-크기를 변경하기 위해서는원하는 크기의 새로운 배열을 선언한 뒤 값을 복사해야 함
• -배열은 처음 생성할 때 크기를 설정함
• 연속된 메모리라서 공간낭비가 발생
• -중간에 데이터가 삭제되면 공간낭비가 발생할 수 있음 또 처음에 배열 크기를 100으로 생성했는데 10정도밖에 쓰지 않으면 나머지 공간은 빈 공간으로 낭비가 발생함
• 연속적인 메모리 할당이 필요하다
• -메모리 공간을 많이 사용하게 될 수 있다

언제사용?

• 데이터 개수가 확실히 정해져 있을 때
• 데이터의 삭제와 삽입이 적을 때
• 검색을 해야될 때

---

배열의 사용

student = new Array();
student[0] = '최진혁';
student[1] = '한이람';
student[2] = '최유빈';
student[3] = '한이은';
student[4] = '김주한';

index로 데이터 가져오기

console.log(student[3])

for문을 이용해 데이터 출력

for (let i = 0; i < student.length; i++) {
	console.log(student[i])
}

배열의 한계

예제

student[3] = null
for(i = 0; i < student.length; i++){
  console.log(student[i]);
}

최진혁
한이람
최유빈
null
김주한

null을 제외 하고 출력 : 조건문 사용

for(i = 0; i < student.length; i++){
  if(student[i] != null) {
     console.log(student[i]); 
  }
}

하지만 위와 같은 반복문이 수십 개 등장한다면 그만큼 조건문도 많아질 것임 이것이 배열의 단점.

배열은 인덱스에 따라서 값을 유지하기 때문에 엘리먼트가 삭제돼도 빈자리가 남게됨

student[3] = '김주한'
student.pop()

 

즉 삭제한 자리를 뒤에 위치한 엘리먼트로 메꾸기

이렇게 데이터가 순서에 따라서 빈틈없이 연속적으로 위치하는 자료구조를 리스트라고함

그런데 이렇게 되면 문제발생 ⇒ 김주한 학생의 식별자인 인덱스 값이 4에서 3이됨 만약 인덱스 4를 이용해 김주한 학생의 값을 가져오는 프로그램이 있다면 문제 생김

이럴때 프로그래머가 선택을 하면 되는데 인덱스가 중요한 경우에는 배열을 사용하면 됨. 인덱스가 중요하지 않은 경우에는 리스트 사용

결론

배열은 거의 모든 언어에 포함된 자료구조.

배열을 잘 다루는 것은 프로그래머에게 기본적인 소양