Array vs Linked list

 

조회

Array는 데이터가 물리적으로 연속해서 저장되어있기 때문에 즉시접근(random access)가 가능하다. O(1)

반면에 Linked list는 물리적으로 연속되어있지 않기 때문에 Head부터 순차적으로 살펴봐야한다. O(n)

 

삽입/삭제

Array는 index 맨 뒤 삽입/삭제의 경우 단순히 추가만하면되기 때문에 O(1)이다. 배열 중간 삽입/삭제의 경우 해당 index보다 큰 index의 데이터를 한 칸씩 옮겨야 하므로 시간 복잡도는 O(n)이 된다.

Linked list의 경우 각 Node가 가리키는 next node address만 변경해주면 되기 때문에 O(1)이다.

 

유리한 상황

1. 입력할 데이터의 개수를 정확히 알고있고 조회가 많이 필요한 상황이면 Array가 유리하다.

2. 입력할 데이터의 개수를 정확히 알지못하고 삽입과 삭제가 많이 필요한 상황이면 Linked list가 유리하다.