Array & Linked List

2019. 10. 6. 22:54Computer Science/자료구조

Linked List의 장단점 (Array와 비교)

장점1) 동적으로 사이즈 조절이 가능함.

장점2) 삽입 및 삭제 시 O(1)의 시간복잡도만 소요됨. Array는 O(N)

단점1) 랜덤 액세스가 불가능함. 순차적으로 데이터를 찾아가는 것만 허용되기 때문에 이진탐색 불가능. 
단점2) list의 각 요소별로 포인터를 담을 추가 메모리가 필요함. 
단점3) array보다 locality*가 좋지 않기 때문에 caching 성능이 떨어질 수 있음.

 

* 메모리 상의 가장 최근 영역에, 가장 접근하기 가까운 영역에 Data가 저장되어있는지 정도. CPU가 Memory로부터 Data를 가져올때 locality가 좋은 data가 cost가 낮겠지?