Array vs Linked List

🤓오늘의 공부 주제: Array와 Linked List 비교🤓

Q. Array와 Linked List는 어떤 차이가 있는 자료구조인가?

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

시간 복잡도가 다름. 데이터 조회의 경우 Array는 O(1), Linked List는 O(n)의 복잡도. 삽입 및 삭제의 경우 Array는 O(n), Linked List는 O(1)의 복잡도.

🔑key point!

따라서 데이터의 크기를 알고 조회를 많이 사용하면 Array가 적합. 반면 데이터 크기가 불확실하고 삽입 및 삭제가 잦다면 Linked List를 사용.

Q. 어느 상황에 Linked List를 쓰는게 나은가요?

A. O(1)으로 삽입/삭제를 자주 해야할때, 얼마만큼의 데이터가 들어올지 예측할 수 없을 때, 조회 작업이 적을때

Q. 어느 상황에 Array를 쓰는게 나은가요?

A. 조회 작업이 많을때, Array 선언시에 데이터 갯수를 미리 알고 있을때, 데이터를 반복문을 통해서 빠르게 순회할때, 메모리를 적게 쓰는게 중요한 상황일때.(Array가 Linked List보다 메모리를 적게 차지. 미리 데이터 양을 안다면 Array가 효율적.)

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

A. Array는 컴파일 단계에서 메모리 할당이 일어남. 이를 static memory allocation이라고 함. 이때 스택 메모리 영역에 할당됨. 반면 Linked List의 경우 런타임 단계에서 새로운 노드가 추가될 때마다 메모리 할당이 일어남. 이를 동적 메모리 할당이라고 하고 힙 영역에 할당됨.

출처 : 인프런 - 기출로 대비하는 개발자 전공면접 [CS 완전정복]