[배열/array] 배열 자료구조

배열(Array)이란 ? 

-데이터를 나열하고, 각 데이터에 인덱스를 부여해서 관리하는 데이터 구조 

-파이썬에서는 리스트 자료구조가 배열에 해당 

 

배열의 사용 이유, 장점과 단점 

-배열은 같은 종류의 데이터를 순차적으로 저장해서 효율적으로 관리하려는 목적 !

-배열의 장점 : 인덱스를 알면 해당 구조로 빠른 접근이 가능하다 (배열을 생성할때 배열의 첫번째 위치의 메모리 address를 함께 저장하기때문에, 나머지 요소들의 인덱스만 알면 간단한 덧셈으로 다른메모리 address를 바로 알수있으므로 O(1)에 접근 가능 - 즉 다시한번 이게 가능하려면 순차적으로 저장되었을때 가능하다는 점!) => 해쉬테이블과 자주 비교해서 언급되므로 제대로 알아두기 

-배열의 단점: 데이터의 추가와 삭제시 자리를 만들거나/ 자리를 메우기 위해 많은 양의 shift를 해야하는 비효율적인 면이 있다. 

 

데이터의 순차적인 저장이라는 면에서 array와 string은 같은 개념으로 접근할 수 있다. 

(=> 코딩 인터뷰에서 string question은 array question으로 해석하자) 

 

배열의 시간복잡도 (time complexity)

=Analyzing the number of steps an operation takes is the heart of understanding the performance of data structures! 

 

Read : looks up what value is contained at a particular index inside the array.

-When a program declares an array, it allocates a contiguous set of empty cells in memory, and it also makes note at which memory address the array begins.

- A computer can read any index by jumping to any memory address in one step.

 

Search : looking to see whether a particular value exists within an array and if so, at which index it’s located.
- a computer has immediate access to all of its memory addresses, but it has no idea offhand what values are

contained at each memory address.

-for N cells in an array, linear search would take a maximum of N steps.

 

Insert : the process of inserting the value at a particular index.

-The efficiency of inserting a new piece of data into an array depends on where within the array you’re inserting it.

-insertions at the end of an array takes one step

-inserting at the beginning or in the middle of an array is a different story. In these cases, we need to shift pieces of data to make room for what we’re inserting, leading to additional steps.

-We can say that in a worst-case scenario - inserting at the beginning of the array can take N + 1 steps

 

Delete : the process of eliminating the value at a particular index.

- Like insertion, the worst-case scenario of deleting an element is deleting the very first element of the array. This is because index 0 would become empty, and we’d have to shift all the remaining elements to the left to fill the gap.