Array는 어떤 자료구조인가?
Array는 연관된 data를 메모리 상에 순차적으로 미리 할당된 크기 만큼 저장하는 자료 구조 이다.
특징
1. 고정된 저장 공간 (fixed - size) -> 미리 선언할떄 크기를 할당하고 선언해야한다. int array[4] = {1,2,3,4};
2. 순차적인 데이터 저장 (order) -> 순차적으로 데이터를 저장한다.
장점
Array의 장점은 lookup과 append가 빠르다.
단점
fixed-size 특성상 Array의 크기를 미리 정해야한다.
이는 메모리 낭비나 추가적인 overhead(간접적인 처리 시간)가 발생할수있다.
시간복잡도
| Array | |
| access(접근) | O(1) |
| append | O(1) |
| delete | O(1) |
| insertion | O(n) |
| deletion | O(n) |
| search | O(n) |
access -> 메모리에 순차적으로 데이터가 저장되어 있으므로, O(1)이 걸린다.
append -> 순차적인 메모리 데이터의 맨뒤에 추가 하므로 O(1)이 걸린다.
delete -> 순차적인 메모리 데이터 맨뒤를 삭제하므로 O(1)이 걸린다.
insertion -> 순차적인 메모리 데이터에서 중간에 값을 삽입하고 나면 뒤에있는 데이터를 밀어줘야하기때문에 O(n)
deletion -> 순차적인 메모리 데이터에서 중간에 값을 삭제하고 나면 뒤에있는 데이터를 땡겨줘야하기 때문에O(n)
search -> 순차적인 메모리 데이터에서 이 데이터가 맞는지 확인하려면 일일이 찾아봐야 하기때문에 O(n)
보통 Array의 자료구조가 나온다면 높은 확률로 Linked List가 나오는데,
둘의 차이는 크게 두가지로 나뉜다.
1. 메모리에 저장되는 방식과
2. 이에 따른 opertaion의 연산 속도 차이가 나뉜다.