[자료구조] 정적 배열 Static Arrays

배열에서 읽기

각 배열 인덱스는 RAM의 주소에 매핑되기 때문에, 요소의 액세스는 즉시 이루어진다.

요소에 액세스하는 데 걸리는 시간은 입력 배열의 크기 영향을 받지 않는다.

* O(1)은 항상 빠른가?
그렇지않다. O(1)이 실제로 의미하는 것은 작업 수가 입력 크기에 비해 일정하다는 것이다.

배열 순회

 크기 배열 순회 작업수가 선형이다.( O(N) )

for i in range(len(myArray)):
   print(myArray[i])

# OR

i = 0
while i < len(myArray):
   print(myArray[i])
   i += 1

배열에서 삭제

배열 끝에서 삭제

엄격한 형식의 언어에서는 모든 배열 인덱스가 초기화 시 빈 배열을 나타내는 기본값으로 채워진다 (0, null, -1).

그 자체로는 삭제되지 않지만, 덮어쓰기는 빈 인덱스를 나타낸다.

def removeEnd(arr, length):
    if length > 0:
        arr[length - 1] = 0

특정 인덱스 삭제

배열 삭제시 연속 순서를 유지해야 하는것을 고려해야 한다.

각 요소의 위치를 왼쪽으로 이동한다. 최악의 경우 모든 요소를 왼쪽으로 이동해야한다( O(N) ).

def removeMiddle(arr, i, length):
    for index in range(i + 1, length):
        arr[index - 1] = arr[index]

삽입

배열 끝에 삽입

항상 배열의 마지막 인덱스에 접근할 수 있으므로 배열 끝에 요소를 삽입하는 것은 O(1)이다.

def insertEnd(arr, n, length, capacity):
    if length < capacity:
        arr[length] = n

 

특정 인덱스에 삽입

삽입하려면, 삽입하기 전에 모든 값을 오른쪽으로 위치 이동해야한다.

void insertMiddle(int arr[], int i, int n, int length) {
    for (int index = length - 1; index >= i; index--) {
        arr[index + 1] = arr[index];
    }
    # Insert at i
    arr[i] = n;
}

 

Operation	Big-O Time	Notes
Reading	O(1)
Insertion	O(n)*	배열 끝에서 삽입시 O(1)
Deletion	O(n)*	배열 끝에서 삭제시 O(1)