Array & Linked List

1. Array는 어떤 자료구조 인가요?

Array는 연관된 data를 메모리상에 연속적이며 순차적으로 미리 할당된 크기만큼 저장하는 자료구조 입니다.

 

 

2. 미리 예상한 것보다 더 많은 수의 data를 저장하느라 Array의 size를 넘어서게 됐습니다. 이 때, 어떻게 해결할 수 있을까요?

기존의 size보다 더 큰 Array를 선언하여 데이터를 옮겨 할당합니다. 모든 데이터를 옮 겼다면 기존 Array는 메모리에서 삭제하면 됩니다. 이런식으로 동적으로 배열의 크기를 조절하는 자료구조를 Dynamic array라고 합니다.

 

 

3. Dynamic Array는 어떤 자료구조 인가요?

Array의 경우 size가 고정되었기 때문에 선언시에 설정한 size보다 많은 갯수의 data가 추 가되면 저장할 수 없습니다. 이에 반해 Dynamic Array는 저장공간이 가득 차게 되면 resize 를 하여 유동적으로 size를 조절하여 데이터를 저장하는 자료구조 입니다.

 

 

4. Dynamic Array를 Linked list와 비교하여 장단점을 설명해 주세요.

Linked List와 비교했을 때, Dynamic Array의 장점은

• 데이터 **접근과 할당이 O(1)**로 굉장히 빠릅니다. 이는 index 접근하는 방법이 산술 적인 연산 [배열 첫 data의 주소값] + [offset]으로 이루어져 있기 때문입니다. (randam access)
• Dynamic Array의 맨 뒤에 데이터를 추가하거나 삭제하는 것이 상대적으로 빠릅니 다.(O(1))

Linked List와 비교했을 때, Dynamic Array의 단점은

• Dynamic Array의 맨 끝이 아닌 곳에 data를 insert or remove할 때, 느린 편입니다 ( ). 느린 이유는 메모리상에서 연속적으로 데이터들이 저장되어 있기 때문에, 데이터를 추가 삭제할 때 뒤에 있는 data들을 모두 한칸씩 shift 해야되기 때문입니 다.
• resize를 해야할 때, 예상치 못하게 현저히 낮은 performance가 발생합니다. resize에 시간이 많이 걸리므로 필요한 것 이상 memory공간을 할당받습니다. 따라 서 사용하지 않고 있는 낭비되는 메모리공간이 발생합니다.

 

 

5. Linked List에 대해서 설명해 주세요.

Linked List는 Node라는 구조체로 이루어져 있는데, Node는 데이터 값과 다음 Node의 address를 저장합니다. Linked List는 물리적인 메모리상에서는 비연속적으로 저장이 되지 만 Linked list를 구성하는 각각의 Node가 next Node의 address를 가리킴으로써 논리적인 연속성을 가진 자료구조입니다.

 

 

 

6. ⭐ Array vs Linked list를 비교해서 설명해주세요.

Array는 메모리 상에서 연속적으로 데이터를 저장하는 자료구조 입니다. Linked List는 메모리상에서는 연속적이지 않지만, 각각의 원소가 다음 원소의 메모리 주소값을 저장해 놓음으로써 논리적 연속성을 유지합니다.

그래서 각 operation의 시간복잡도가 다릅니다. **데이터 조회는 Array의 경우 O(1), Linked list는 O(n)**의 시간복잡도를 갖습니다. **삽입/삭제는 Array O(n), Linked list O(1)**의 시간 복잡도를 갖습니다. 따라서 얼마만큼의 데이터를 저장할지 미리 알고있고, 조회를 많이 한다면 Array를 사용하는 것이 좋습니다. 반면에 몇개의 데이터를 저장할 지 불확실하고 삽입 삭제가 잦다면 Linked list를 사용하는 것이 유리합니다.

 

 

7. Array와 Linked List의 memory allocation은 언제 일어나며, 메모리의 어느 영역을 할당 받나요?

Array는 compile 단계에서 memory allocation이 일어납니다. 이를 Static Memory Allocation이라고 합니다. 이 경우 Stack memory영역에 할당됩니다. Linked List의 경우 runtime 단계에서 새로운 node가 추가될 때마다 memory allocation이 일어납니다. 이를 Dynamic Memory Allocation이라고 부릅니다. Heap메모리 영역에 할당됩니다.