[Data Structure] 1. Array(List)

이병수·2020년 7월 6일
0

자료구조

목록 보기
2/4

1. Array(list)란?

  • JS에서는 Array, Python에서는 List
  • Array(List)는 가장 기초적이고 단순하면서도 가장 자주 사용되는 자료 구조

2. Array 특징

순차적으로 데이터를 저장하는 자료구조

  • 가장 큰 특징은 순차적(ordered)으로 데이터를 저장한다는 점
  • 자료구조에서 저장하는 데이터를 element라고 한다
  • Array는 주로 서로 연결된 데이터를 순차적으로 저장할 때 사용
  • 순서가 상관 없더라도 서로 연결된 데이터를 저장할 때 일반적으로 사용

그래서 array가 가장 자주 사용되는 자료구조중 하나가 된 것

기타특징

  • 삽입(insertion) 순서대로 저장됨
  • 이미 생성된 리스트도 수정 가능(mutable)
  • 동일한 값도 여러번 삽입 가능
  • Multi-dimensional Array (다중차원 배열)
    ex) Array의 요소가 array가 될 수 있음

3. Array의 내부구조

  • Array의 가장 큰 특징은 순차적으로 데이터를 저장하는 것 (순차적으로 번호를 지정함 이 번호를 index라고 함)
  • index는 0부터 시작하고 마이너스 부호도 가질 수 있음 (마이너스 index는 맨 마지막 요소부터 시작)

왜 array가 순차적으로 데이터를 저장할 수 밖에 없을까?

1) 실제 메모리 상에서 즉 물리적으로 데이터가 순차적으로 저장되기 때문
2) 데이터에 순서가 있기 때문
2-1) index가 존재
2-2) indexing (index를 사용해 특정 요소를 array부터 읽어 들이는 것이 가능)
2-3) Slicing (요소의 특정 부분을 따로 분리해 조작하는 것 가능)

4. 단점

1) Removing or Adding Elements

  • 순차적으로 담겨있는 데이터 중 특정 위체에 있는 중간의 요소가 삭제되는 경우

  • 삭제된 요소로 부터 뒤는 모든 요소들을 앞으로 한 칸씩 이동시켜야 한다.

    이뜻은 배열에서 요소를 삭제하는 것은 다른 자료구조에 비해 느릴 수 있다는 것!

  • 코드상에는 한 줄이지만 메모리상에서 이루어지는 작업(operation)은 훨씬 커진다(expensive operation)

  • 중간에 요소가 추가되는 경우도 마찬가지로 그 뒤의 요소가 하나씩 밀리게된다.

그렇기 때문에 Array는 정보가 자주 삭제되거나 추가되는 데이터를 담기에는 적절치 않음

2) Array Resizing

  • Resizing은 말그대로 사이즈를 다시 조정한다는 뜻

  • 배열은 메모리가 순차적으로 채워지기 때문에 배열이 처음 생성될 때 어느정도 메모리를 미리 할당 (pre-allocation)

  • pre-allocation 함으로써 새로 추가되는 요소들도 순차적으로 메모리에 저장될 수 있다

  • 하지만 요소들이 처음 할당한 메모리 이상으로 많아진다면 resizing이 필요

  • 즉 메모리를 더 할당해야 하며 추가적으로 할당된 메모리 또한 순차적이어야 한다.

    그럼으로 배열의 resizing은 상대적으로 오래걸리는 operation이다

    ex) 100개의 메모리 공간 다차서 100개를 추가해야하는 경우

  • 200개의 크기의 메모리 생성 후 -> 기존 100개 복사 -> 그 다음 101번 부터 데이터가 순차적으로 추가

그렇기 때문에 Array는 사이즈 예측이 잘 안되는 데이터를 다루기에는 적절치 않음

5. 언제 사용하면 좋을까?

  • 순차열적인 데이터를 저장할 때
    • ex) 주식 가격. 어제의 2만원과 오늘의 2만원이 다름 >>> 값보다는 순서가 중요한 데이터
  • 다차원 데이터를 다룰 때 >>> Multi-dimensional Array
  • 어떠한 특정 요소를 빠르게 읽어야 할 때 >> index를 통해 곧바로 읽을 수 있기 때문
  • 데이터의 사이즈가 급변하게 자주 변하지 않을 때
  • 요소가 자주 삭제 되거나 추가되지 않을 때

문제

Array를 적용 시키면 좋을 데이터의 예를 구체적으로 들어주세요. (ex. 주식 차트) 구체적 예시와 함께 Array를 적용하면 좋은 이유, 그리고 Array를 사용하지 않으면 어떻게 되는지 함께 서술해주세요. *

모범 답안 )
Array를 적용시키면 좋은 예로 주식 차트가 있습니다. 주식 차트에 대한 데이터는 요소가 중간에 새롭게 추가되거나 삭제되는 정보가 아니며, 날짜별로 주식 가격이 차례대로 저장되어야 하는 데이터입니다. 즉, 순서가 굉장히 중요한 데이터 이므로 Array 같이 순서를 보존 해주는 자료구조를 사용하는 것이 좋습니다. 이와 같은 데이터에 Array를 사용하지 않는 경우, 즉 순서가 없는 자료 구조를 사용하는 경우에는 날짜별 주식 가격을 확인하기 어려우며 매번 전체 자료를 읽어 들이고 비교해야 하는 번거로움이 발생합니다.

0개의 댓글