배열(array) 정리

- 배열 (Array)

 

 배열은 생성할 때 크기를 정해주어야하며 (python, js는 예외) , 랜덤의 위치에 들어간다. 

 컴퓨터는 배열의 시작 위치를 알고 있고, random access 덕분이다.

배열의 크기와 상관없이 인덱스에서 요소를 읽어내는 속도는 같다.

 

읽기

 배열에서 읽는 것은 매우 빠르게 이루어진다. 수요일을 읽고싶다면 익덱스2번을 요청하면 되는 것이다.

 

 

사진 출처 : https://wikidocs.net/206

 

검색

 검색은 읽기와 다르게 시간 복잡도가 O(n)이다. 즉, 최악의 경우 배열을 끝까지 돈 것이다.

예를 들어 '목'을 검색한다고 하자. 우리는 배열에 '목'이 어디에 있는지, 존재하는지도 알 수 없다.

순차검색을 통해 인덱스 0번부터 검색하기 시작한다. 그러고 인덱스 3에서 '목'을 찾을 수 있다.

만약 '일'이나 배열에 없는 것을 찾는다면 인덱스 0부터 6까지 모두 돌아야 할 것이다.

 

추가

추가의 핵심은 '어디에' 위치 시킬 것인가 이다. 추가는 어디에 위치 시킬 것인지에 따라 속도가 결정된다. 가장 빠른 것은 배열의 남은 부분의 마지막 부분에 쓰는 것이다. 가장 효율적이다. 만약 배열의 중간이나 앞에 적고 싶다면 위치 시키고 싶은 위치 뒤에 있는 데이터는 모두 뒤로 한 칸 씩 움직여야 할 것이다. 

예를 들어 '라'라는 글자를 인덱스2에 넣고 싶다고 하자. 그럼 '수'부터 '일'까지는 모두 뒤로 한칸 씩 움직여야 하는 비효율이 있다. 

가장 비효율적인 것은 데이터를 넣고자 하는 배열이 꽉차있을 때이다. 앞에서 말했다시피 배열의 사이즈는 처음 만들 때 정해진다. 그러므로 배열이 꽉 차있다면 새로운 배열을 만들어 기존의 배열에 있던 데이터를 옮기고 새로운 데이터를 추가할 수 있다.

 

삭제

 삭제도 추가와 비슷하다. 배열의 어디에 위치한 데이터를 삭제하냐에 따라 속도가 달라진다. 배열의 맨 마지막에 있는 데이터를 삭제한다면 수월하게 수행할 수 있다. 하지만, 배열의 가운데, 맨 앞에 위치한 데이터를 삭제하고자 한다면 해당 데이터를 삭제하고 빈 공간의 뒤에 있는 데이터들이 한 칸씩 앞으로 움직여 채워줘야 한다.