DataStructure - Array(배열)

Array(배열)

메모리 상에 원소를 연속하게 배치한 자료구조

1.. 배열의 성질

1. O(1)에 k번째 원소를 확인/변경 가능

• Index를 통해 직접 조회가 가능하며, Time Complexity = O(1)

2. 추가적으로 소모되는 메모리의 양(=overhead)가 거의 없음

3. Cache hit rate가 높음(메모리 상에 데이터들이 붙어있어서)

• Cache hit rate(=ratio)는 말 그대로 캐시가 적중되는 정도를 뜻함
• 배열의 경우, 기억장치 내에 인접하여 저장된 데이터들이 연속적으로 엑세스될 가능성(공간 지역성)이 높기때문에 Cache hit rate이 높다.

4. 메모리 상에 연속한 구간을 잡아야해서 할당에 제약이 걸림

2.. 배열의 기능

• 임의의 위치에 있는 원소를 확인/변경, O(1)
• 원소를 끝에 추가, O(1)
• 마지막 원소를 제거, O(1)
• 임의의 위치에 원소를 추가 or 임의의 위치에 있는 원소를 제거, O(N)

lst = []

lst.append(x)
# 리스트 맨 뒤에 x 삽입
# Time Complexity -> O(1)

lst.insert(i,x)
# 리스트의 i 번째 위치에 x 삽입
# Time Complexity -> O(n)
# ex) 책장에 책이 연속해서 꽂혀있을때 중간에 책을 넣기 위해서는 나머지 책들을 밀어야하는 상황과 동일

lst.pop()
# 리스트 마지막 원소 제거
# Time complexity -> O(1)

lst.pop(i)
# 리스트의 i 번째 원소 제거
# Time Complexity -> O(n)

lst.remove(x)
# 리스트에서 x 원소 제거
# Time Complexity -> O(n)

lst.index(x)
# 리스트를 맨 앞부터 검색해서 x 원소를 찾고 index를 반환
# Time Complexity -> O(n)