Array vs LinkedList

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

같은 타입의 요소들이 연속하여 저장된 자료구조로 타입 T와 배열의 크기 N이 주어졌을 때, 배열의 각 요소가 0부터 N-1까지 인덱스에 의해 참조됩니다.

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

Array 특성상 한 번 정한 크기는 변경할 수 없으므로 더 큰 크기의 배열을 생성한 후, 기존 array의 데이터를 옮겨야 합니다.

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

일반 배열과 달리 동적 배열은 초기에 정해진 크기를 넘어서는 데이터를 저장할 수 있고 필요에 따라 크기를 조절할 수 있는 배열입니다. Python에 list, Java의 ArrayList가 대표적인 Dynamic Array입니다.

[꼬꼬무 1] Dynamic Array를 Linked List와 비교하여 장단점을 설명해 주세요.

동적 배열은 인덱스를 이용해 상수 시간에 원하는 데이터를 찾을 수 있다는 장점이 있으나 미리 지정한 메모리 크기를 초과하는 경우 내부적으로 메모리 재할당, 데이터 복사가 이루어진다는 단점이 있습니다. Linked List 같은 경우 노드를 계속 이어주는 방식이라 데이터 크기의 제한이 없다는 장점이 있으나 원하는 데이터를 찾을 때 노드의 맨 앞부터 순차적으로 탐색해야 된다는 단점이 있습니다.

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

데이터 필드와 링크 필드로 이루어진 노드를 계속 연결하여 데이터를 저장하는 방식입니다. 

[꼬꼬무 1] 어느 상황에 Linked List를 쓰는 게 Array보다 더 나을까요?

Linked List 같은 경우 데이터 크기의 제한이 없기 때문에 저장해야 할 데이터의 크기를 예측할 수 없을 경우 Linked List가 유리합니다.

[꼬꼬무 2] 어느 상황에 Array를 쓰는 게 Linked List보다 더 나을까요?

Linked List 같은 경우 원하는 데이터를 찾으려면 첫 번째 노드부터 순차적으로 탐색해야 하기 때문에 인덱스를 통해 상수시간에 데이터를 찾는 Array보다 데이터 탐색이 느립니다. 때문에 데이터 탐색 연산이 많이 필요한 경우 Array가 유리합니다.

[꼬꼬무 3] Array와 Linked List의 Memory allocation은 언제 일어나며, 메모리의 어느 영역을 할당받나요?

배열은 컴파일 타임에 크기가 결정되며 함수 내에서 선언된 경우 메모리의 stack영역을 할당받습니다. Linked List는 런타임 단계에서 새로운 노드를 추가할 때마다 동적으로 할당되며 주로 heap영역을 할당 받습니다.

Compile time - 소스코드가 컴파일러를 통해 기계가 이해할 수 있는 기계어로 변환되는 과정
Run time - exe를 통해 프로그램이 동작되는 때

Array vs Linked List를 비교해서 설명해 주세요.

Array는 같은 타입의 요소들이 연속적으로 저장된 자료구조이고 Linked List는 데이터 필드와 링크 필드로 이루어진 노드를 계속 연결하여 데이터를 저장하는 방식입니다.