개발/신입개발자 기술면접
[신입개발자 기술면접] 배열 (Array)과 연결 리스트 (Linked List)의 장단점
소금집사
2024. 1. 8. 13:17
반응형
배열(Array)과 연결 리스트(Linked List)는 프로그래밍에서 주요 데이터 구조 중 두 가지입니다.
각각의 구조에는 장단점이 있습니다.
다음은 배열과 연결 리스트의 주요 장단점입니다:
배열 (Array)
장점:
- 빠른 접근: 인덱스를 사용하여 배열 내의 특정 요소에 빠르게 접근할 수 있습니다. O(1)의 시간 복잡도로 요소에 접근할 수 있습니다.
- 메모리 사용: 배열은 연속된 메모리 공간에 요소를 저장하므로, 캐시 효율성이 높을 수 있습니다.
- 간단한 구조: 배열은 간단하고 직관적인 구조를 가지고 있습니다.
단점:
- 크기 제한: 배열의 크기는 고정되어 있으므로, 크기를 동적으로 변경하기 어렵습니다.
- 메모리 할당 문제: 배열의 크기가 고정되어 있어, 초기에 큰 배열을 할당하더라도 실제로 사용되는 메모리가 적을 수 있습니다.
- 삽입 및 삭제의 어려움: 중간에 요소를 삽입하거나 삭제할 때 다른 요소들을 이동시켜야 하므로, 시간 복잡도가 O(n)이 될 수 있습니다.
연결 리스트 (Linked List)
장점:
- 동적 크기: 연결 리스트는 동적으로 크기를 변경할 수 있습니다.
- 삽입 및 삭제: 특정 위치에 요소를 삽입하거나 삭제할 때, 인접한 요소들의 이동이 필요하지 않습니다. 삽입 및 삭제 연산이 상대적으로 빠를 수 있습니다.
- 메모리 효율성: 필요한 만큼의 메모리만 할당하므로, 메모리의 효율적인 사용이 가능합니다.
단점:
- 접근 시간: 특정 요소에 접근하기 위해서는 전체 리스트를 순회해야 할 수도 있습니다. 최악의 경우, O(n)의 시간 복잡도를 가질 수 있습니다.
- 추가적인 메모리 사용: 각 요소마다 다음 요소를 가리키는 포인터가 필요하므로, 추가적인 메모리 사용이 발생합니다.
- 캐시 비효율성: 연결 리스트는 포인터를 통해 다음 요소를 참조하므로, 캐시 효율성이 떨어질 수 있습니다.
요약하면, 배열은 빠른 접근과 간단한 구조를 가지고 있지만, 크기 제한과 삽입/삭제 연산의 어려움이 있습니다. 반면, 연결 리스트는 동적 크기와 삽입/삭제의 효율성을 가지고 있지만, 접근 시간과 메모리 사용에 대한 단점이 있습니다. 선택하는 자료 구조는 사용하는 상황과 요구 사항에 따라 달라질 수 있습니다.
Array
장점 : 메모리에 연속된 공간으로 저장. RandomAccess 가능.
단점 : 중간 삽입하거나, 배열의 데이터가 다 찬 상태에서 삽입이 이루어질 때 복사 비용 발생
Linked List
장점 : 삽입과 삭제가 빠르다.
단점 : RandomAccess 불가, 접근속도가 느림
반응형