[면접 준비] Array와 LinkedList의 차이

학습 키워드: Array, LinkedList, fixed size, dynamic size, memory allocation, node, pointer, reference

 

2024-07-25 면접 카타 질문

Array과 LinkedList를 비교설명해주세요:

 일반적으로 Array는 고정된 크기를 가지며 메모리에 저장될 때 배열의 모든 항목이 연속된 공간에 할당되기 때문에 메모리 접근 효율이 좋습니다. Array의 각 항목을 access할 때 항목의 index를 알면 O(1)의 시간 복잡도로 접근이 가능하다는 특징이 있습니다. JS에서는 Array가 가변크기를 가지기 때문에 처음 언급한 연속된 메모리 공간이라는 특징이 유효하지 않습니다.

 

LinkedList의 경우 Node와 Pointer를 기반으로 하는 자료 구조로, Array와는 다르게 메모리의 크기가 정해져있지 않고 새 항목을 자유롭게 추가할 수 있어서 크기를 정확하게 알 수 없는 경우에 유용합니다. 메모리에 저장될 때 인접 공간이 아닌 별도의 위치에 저장되고 해당 위치를 참조하는 구조로 되어 있어서 Array와 비교하면 약간의 오버헤드가 있습니다. 특정 노드를 access하려면 리스트의 첫 번째 항목부터 차례대로 탐색하여 찾아야하기 때문에 O(n)의 시간 복잡도를 가집니다. 다만 Array가 크기를 변경할 때 O(n)의 시간 복잡도를 가지는 것과 반대로 LinkedList에 새 항목을 추가하는 것은 리스트의 tail에 새 노드를 이어 붙이기만 하면 되기 때문에 O(1)의 시간 복잡도를 가집니다.

 

 

--