728x90
반응형
배열이란?
배열은 프로그래밍에서 데이터를 저장하는 데 사용되는 자료구조이다.
배열의 특징
- 동일한 타입의 데이터를 연속된 메모리의 공간에 순차적으로 저장하는 선형 자료구조 형태이다.
- 배열은 선언할 때 크기를 정하면 그 크기로 고정되며, 선언된 크기는 배열을 다시 선언하지 않으면 변경할 수 없다.
- 배열의 연산은 크게 접근, 추가, 삭제, 검색으로 이루어진다.
시간복잡도
- 접근(Access)
- 배열은 인덱스로 접근을 하게 된다.
- 배열의 첫 번째 인덱스의 주소는 기본적으로 알고 있기 때문에, 원하는 인덱스를 접근하는 방법은 [첫 번째 인덱스의 주소 + (자료형의 크기) * 접근하고자 하는 인덱스] 한 주소에 접근하면 된다.
- 따라서 시간복잡도는 O(1)이다.
- 삽입(Insertion)
- 배열의 시작 부분에 삽입을 할 때
- 배열이 꽉 차있을 경우 : 기존 배열보다 길이가 1이 더 긴 배열을 만든 뒤, 배열 처음에 값을 삽입한 후 기존에 있던 배열을 복사해야 한다.
- 배열이 꽉 차있지 않을 경우 : 모든 배열의 요소를 한 칸 씩 뒤로 미룬 뒤에 맨 앞에 값을 삽입한다.
- 따라서 시간복잡도는 O(n)이다.
- 배열의 중간 부분에 삽입을 할 때
- 배열이 꽉 차있을 경우 : 기존 배열보다 길이가 1이 더긴 배열을 만든 뒤, 원하는 위치 전까지 있는 요소들을 복사한 후 요소를 삽입한 뒤에 기존 배열의 나머지를 복사해야 한다.
- 배열이 꽉 차있지 않을 경우 : 원하는 인덱스의 요소부터 마지막 요소까지 한 칸씩 뒤로 미룬 뒤, 원하는 위치에 값을 삽입한다.
- 따라서 시간복잡도는 O(n)이다.
- 배열의 끝 부분에 삽입을 할 때
- 배열이 꽉 차있을 경우 : 기존 배열보다 길이가 1이 더 긴 배열을 만든 위, 기존 배열의 요소를 복사한 후 마지막에 값을 삽입한다.
- 배열이 꽉 차있지 않을 경우 : 기존 배열의 맨 끝에 값을 삽입하면 된다.
- 따라서 시간복잡도는 경우에 따라 O(n)이 될 수도, O(1)이 될 수도 있다.
- 배열의 시작 부분에 삽입을 할 때
- 삭제(Deletion)
- 배열의 시작 부분을 삭제 할 때
- 기존 배열에서 맨 처음의 요소를 삭제한 뒤, 기존에 있던 요소들을 한 칸씩 앞으로 당긴다.
- 따라서 시간복잡도는 O(n)이다.
- 배열의 중간 부분을 삭제 할 때
- 기존 배열에서 특정 인덱스에 있는 요소를 삭제한 뒤, 인덱스 뒤로 있는 요소들을 한 칸씩 앞으로 당긴다.
- 따라서 시간복잡도는 O(n)이다.
- 배열의 끝 부분을 삭제 할 때
- 기존 배열에서 마지막 인덱스만 삭제한다.
- 따라서 시간복잡도는 O(1)이다.
- 배열의 시작 부분을 삭제 할 때
- 검색(Search)
- 배열은 순차검색이므로, 원하는 요소를 찾을 때까지 배열을 순회해야 한다.
- 따라서 시간복잡도는 O(n)이다.
장단점
- 장점
- 구현이 쉽다.
- 연속적이므로 메모리 관리가 편하고, 참조를 위한 추가적인 메모리가 필요하지 않는다.
- 인덱스를 통해 접근하면 시간복잡도가 O(1)으로 빠르게 접근이 가능하다.
- 단점
- 새로운 요소를 삽입하거나 삭제할 때 다른 요소들을 이동시켜야 해서 시간복잡도가 O(n)으로 비효율적이다.
- 배열은 선언할 때 고정된 크기를 할당하므로, 선언한 만큼 사용하는게 아니라면 메모리 낭비가 될 수 있다.
예제
var array1 = emptyArray<Int>() //빈 int 배열 생성
var array2 = arrayOf(1, 2, 3) //요소가 1, 2, 3이 들어간 배열 생성
var array3 = arrayOfNulls<Int>() //요소가 null로 채워진 배열 생성
var array4 = Array<Int>(3) { i -> i } // 크기가 3인 배열을 생성하여 람다로 요소를 1, 2, 3을 넣음
출처 : https://jjoonleo.tistory.com/8, https://moonsu.tistory.com/58, https://itandhumanities.tistory.com/2
728x90
반응형
'개념정리 > 자료구조' 카테고리의 다른 글
[자료구조] 큐(Queue)란? (0) | 2023.11.15 |
---|---|
[자료구조] 스택(Stack)이란? (1) | 2023.10.30 |
[자료구조] 비선형 자료구조란 무엇인가? (0) | 2023.06.30 |
[자료구조] 자료구조란 무엇인가? (0) | 2023.06.30 |
[자료구조] 선형자료구조란 무엇인가? (0) | 2023.06.30 |