선형 자료구조 - 배열(Array)

배열의 기본 구조

• 배열 생성시, 크기가 고정된다.
• 배열의 인덱스는 0부터 시작된다.
• 위 예시는 int(정수) 배열을 나타낸다.
• 정수 배열은 4바이트 단위로 이루어ㅊ져 있어, 메모리 주소(memory address)의 시작 위치를 1000, 1004, ..., 1020로 나타낸다.

배열의 특징

• 연속된 메모리의 공간에 순차적으로 데이터를 저장하는 선형 자료구조이다.
• 많은 수의 데이터를 다룰 때 사용하는 자료구조
• 각 데이터를 인덱스와 1:1 대응
• 데이터가 메모리상에 연속적으로 저장
• 배열 생성시 크기를 미리 설정해야함
• 메모리는 배열이 선언될 때(컴파일 할 때) Stack영역에 할당한다.

배열의 장점

• 인덱스를 이용하여 데이터에 빠른 접근
• 시간 복잡도; O(1)
• 자료 구조의 크기가 클수록 더 강력한 장점
• 연속된 메모리 공간에 존재하기 때문에 관리 편리

배열의 단점

Search, Insertion, Deletion시의 시간복잡도

• 데이터의 추가(=삽입), 삭제가 번거로움
  • 배열 중간 지점의 데이터 삭제시, 다음 항목의 모든 값을 앞으로 시프트 시켜야한다 (위 그림 참고).
  • 이때 for문을 사용하므로 시간복잡도 O(n)을 가진다.
• 배열 생성시 크기를 예측 생성해야함
  • 만약 딱 맞게 생성하게 되면 크기가 변함에 따라 새로운 배열을 할당해서 옮겨줘야하는 번거로움이 있음
  • 예측 보다 크게 생성하면, 사용되지 않는 공간은 메모리의 낭비로 이어짐
• 따라서, 정적 자료(삽입, 삭제가 별로 없고 검색이 위주인)에 사용되는 경우 유리하다.

배열의 시간 복잡도

• Access: O(1)
• Search: O(n)
• Insertion: O(n)
• Deletion: O(n)

데이터 접근은 O(1)이며 random access라고 표현한다. 즉, 어느 위치에 있더라도 동일한 시간에 접근이 가능하다는 것을 의미한다. 나머지의 연산들은 worst와 average모두 O(n)으로 모든 요소들을 순회해야한다는 것을 의미한다.

 

배열을 사용하기 좋은 경우

• 데이터의 수가 확실하게 정해진 경우.
• 데이터의 삭제와 삽입이 적은 경우.
• 데이터의 탐색이 많이 이루어지는 경우.

References

1. https://velog.io/@codenmh0822/%EC%84%A0%ED%98%95-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EB%B0%B0%EC%97%B4Array

선형 자료구조 - 배열(Array)

https://gukin.tistory.com/9

선형 자료구조 - 배열(Array)