Array와 Linked List의 차이점

Array

논리적 저장 순서와 물리적 저장 순서가 일치한다. 따라서 index로 해당 원소에 접근할 수 있다. 그렇기 때문에 찾고자 하는 인덱스 값을 알고 있으면 O(1)에 해당 원소로 접근할 수 있다. 즉, 랜덤 접근이 가능하다.

삽입과 삭제는 빈 공간이 생기면 안되기 때문에, 최악의 경우 O(N)이 된다.

Linked List

각각의 원소들은 자기 자신 다음에 어떤 원소가 오는지 기억하고 있다. 따라서 삽입과 삭제는 O(1)만에 해결할 수 있다.

하지만 원하는 위치에 삽입을 하려고 하면 첫번째 원소부터 확인해야 하기 때문에 O(N)의 시간 복잡도가 걸린다.