본문 바로가기

자료구조

Array

| 배열(Array) 이란?

선형 자료구조(Data Structure)중 하나로, 동일한 타입의 연관된 데이터를 메모리에 연속적으로 저장하여 하나의 변수에 묶어서 관리하기 위한 자료 구조

 

  • Java 에서는 ??개 크기의 배열 선언하겠다고 적어줘야 함.
  • JS, Python 은 곧바로 선언.
// Java 방식
String strArray = String[10]; // 10개 짜리 String 배열을 선언

// JS 방식
var jbAry = new Array();

// Py 방식
a = []

그림을 통해 Array를 이해해 보자.

Array를 생성하면 보통 선언된 크기만큼 [메모리 = RAM]에 할당 된다. (위의 그림에서 예시로 10개 설정함)

 

Array에서 가장 중요한 핵심개념은 랜덤엑세스(Random Access) 이다.

 

## RAM : Random Access Memory

Random Access : 데이터의 위치가 어디든 빠르게 데이터에 접근하는 기술

(ex: 우리 집이 서울인데, 부산을 가든 샌프란시스코를 가든 거의 동일한 빠른시간 내에 도착한다는 의미)

(ex: 10000개 데이터.  array[0] 접근속도 = array[9999] 접근속도 )

 

랜덤엑세스 개념은 Array 에도 중요하지만, 추후에 배울지도 모르겠지만, 데이터베이스(DB)에서도 중요한 개념이다. (데이터 읽기에 대한 이해)

 

Case 별 성능 확인

Reading (읽기)

데이터 1개를 빈번하게 읽어와야 한다면 Array가 좋다.

Random Access 덕분에 읽기 속도가 빠르다.


Searching (검색)

Array는 Data Box 들이 순서대로 나열되어 있는 것이다.

데이터는 밖에 표시되어 있지 않으며, 찾아가서 그 박스를 직접 열어봐야 어떤 데이터가 있는지 알 수 있다.

그 말인 즉슨, 데이터가 어디에 있는지 몰라서 하나하나 뒤져서 탐색해 봐야한다는 것이다.

 

Case

  1. (best)내가 찾는 아이템이 Array의 앞에 있으면 빨리 찾는다. (검색은 0번째 인덱스 부터 시작)
  2. (worst)내가 찾는 아이템이 Array의 맨 뒤에 있으면 찾는데 한참 걸린다.
  3. (worst)내가 찾는 아이템이 Array에 없어?? ⇒ 끝까지 다 뒤졌는데 없다는 것이다.

⇒ Linear Search (선형 검색) : 검색능력은 빠르지 않다


Insert (삽입)

Case

  1. (best)Array의 맨뒤에 넣는건 빠르다 (Array 의 마지막 index를 찾아서 그 뒤에만 추가해 주면 됨)
  2. (average)Array의 중간에 넣는다. 그냥 보통속도다. (넣고 싶은 자리의 뒤 데이터를 1개씩 밀어낸다.)
  3. (worst)Array의 맨 앞에 넣는건 엄청 느리다. (Array 의 모든 데이터를 1자리씩 밀어내야 한다.)
  4. (worst)이미 Array가 꽉 찼는데 데이터를 넣어야 하는 경우 (더 큰 Array를 만들어서, 데이터를 복제 후 이전 시키고 그전의 Array를 삭제해야함… 복잡함..)

⇒ 삽입 능력은 좋지 않다


Delete

Case

  1. (best)Array의 맨뒤있는 데이터를 삭제 (Array 의 마지막 index를 찾아서 그 뒤에만 삭제해 주면 됨)
  2. (average)Array의 중간데이터 삭제 (넣고 싶은 자리의 뒤 데이터를 1개씩 당긴다.)
  3. (worst)Array의 맨 앞에 데이터 삭제 (Array 의 모든 데이터를 1자리씩 당긴다.)

⇒ 삭제 능력은 좋지 않다

'자료구조' 카테고리의 다른 글

Queue(선형 큐)  (0) 2022.12.11
Stack  (0) 2022.12.11
Double LinkedList  (0) 2022.12.11
Single LinkedList  (0) 2022.12.10
ArrayList  (0) 2022.12.10