CS공부 12일차 : Array & LinkedList CS문제 모음
❓ Array는 어떤 자료구조인가요?
Array는 연관된 데이터를 메모리상에 연속적이고 순차적으로 미리 할당된 크기만큼 저장하는 자료구조
❓ Array와 LinkedList의 가장 큰 차이점은?
메모리에 저장되는 방식과 이에 따른 Operation의 연산속도이다.
❓ Array의 TimeComplexity는?
조회 (random Access) : O(1)
마지막 인덱스에 추가,삭제 : O(1)
삽입,삭제 : O(n)
탐색 : O(n)
❓ Array의 장단점은?
조회를 자주 해야하는 작업에서는 유리하지만 fixed size인 특성상 배열의 크기를 미리 정해야하기 때문에 메모리의 낭비나 추가적인 overhead가 발생할 수 있다.
❓ 미리 예상한 것보다 더 많은 수의 Data를 저장하느라 Array의 Size를 넘어서게 되었다면?
기존의 Size보다 더 큰 Array를 선언하여 데이터를 옮겨 할당한다. 모든 데이터를 옮기면 기존 Array를 삭제하는데 이러한 방식으로 동작하는 배열을 동적배열이라고 한다.
❓ Dynamic Array는 어떤 자료구조인가요?
Array의 경우 Size가 고정되어 있지만 Dynamic Array는 Size를 Resize하여 유동적으로 Size를 조절하여 데이터를 저장하는 자료구조이다.
❓ Dynamic Array와 Linked-List를 비교
Dynamic Array의 장점은 데이터 접근과 할당이 매우 빠르다는 것이다. 이는 시간복잡도 O(1)을 갖는다. 이는 index로 접근하는 산술적인 연산 [배열의 첫 data 주소값] + [offset값] 으로 이루어져있기 때문이다.
하지만 맨 끝이 아닌 곳에 데이터를 삽입하거나 삭제할 때 공간을 만들거나 없애기 위해서 데이터들을 모두 Shift해야하기 때문에 시간복잡도 O(n)을 갖기 때문에 비교적으로 느리다.
❓ Linked-List에 대해서 설명해주세요
Linked List는 Node라는 구성체로 이루어져 있는데 Node는 데이터값과 다음 Node의 Address값을 저장하고있는 Pointer로 이루어져 있따. 물리적인 메모리상에는 비연속적으로 저장되지만 Linked-List를 구성하는 각각의 Node가 다음 Node의 주소를 가리킴으로 논리적인 연속성을 가지는 자료구조이다.
❓ Linked-List의 시간복잡도는?
Access : O(n)
Search : O(n)
insertion : O(1)
deletion : O(1)
❓ Array와 Linked-List를 비교하여 설명해주세요
Array는 메모리상에서 연속적으로 데이터를 저장하는 자료구조이고 Linked-list는 메모리상에서는 연속적이지는 않지만 각각의 원소가 다음 원소의 메모리값을 저장해 놓음으로써 논리적인 연속성을 가지는 자료구조이다.
이에 각 Operaiton의 시간복잡도가 다른데 데이터를 조회하는 경우 Array는 O(1), Linked-List는 O(n)의 시간복잡도를 갖는다. 삽입과 삭제는 각각 O(n)과 O(1)을 갖는다.
따라서 얼마만큼 데이터를 저장할 지 알고 있고, 조회를 많이 한다면 Array를 사용하는 것이 좋고, 몇개의 데이터를 저장할 지 불확실하고 삽입 삭제가 잦다면 Linked List를 사용하는 것이 유리하다.
❓ 어느 상황에서 Linked-List를 사용해아 하나요?
O(1)으로 삽입/삭제를 해야할때
얼마만큼 데이터가 들어올 지 예측할 수 없을 때
조회 작업을 별로 하지 않을 때
❓ 어느 상황에서 Array를 사용해야 하나요?
조회 작업을 해야할 때
Array를 선언할 당시에 데이터 개수를 알 수 있을 때
데이터를 반복문을 통해서 빠르게 순회할 때
양을 알고 데이터를 적게 쓰는게 중요한 상황일 때
(Node의 메모리자체는 큼 (data + address)
❓ Array와 Linked-list의 메모리 할당은 언제 일어나며 어느 영역을 할당하나요?
Array는 Compile단계에서 메모리 할당이 일어난다. 이를 Static Allocation이라고 하고 Static Memory에 할당된다.
Linked-list는 Runtime단계에서 메모리 할당이 일어난다. 이를 Dynamic Memory Allocation이라고 하고 Heap Memory에 할단된다.
