[배열/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.