-
Array vs LinkedList
- Array
- 논리 저장 순서랑 물리 저장 순서가 일치함
- 인덱스로 원소에 접근이 가능하기 때문에, O(1)로 엑세스 가능
- 삭제 or 삽입은 해당 원소에 접근하여 작업을 완료한 뒤(O(1)), 또 한 가지의 작업을 추가적으로 해줘야 하기 때문에, 시간이 더 걸린다.
- 맨 뒤에 요소를 추가하는 것은 O(1)이지만, 원래 존재하던 요소의 앞쪽에 삽입한다면 뒤에 있는 요소들의 인덱스를 +1씩 해줘야함
- 삭제의 경우도 뒤에 있는 요소들을 한칸씩 땡겨줘야함 (인덱스 -1)
- 위의 두 경우 모두 O(n)의 작업이 추가적으로 필요하다
- LinkedList
- 논리 저장 순서와 물리 저장 순서가 일치하지 않음
- 논리 저장에는 실제 저장되어있는 요소의 주소 값이 들어있다.
- 각 원소들은 자신의 다음 원소를 기억하고 있기 때문에, 삭제와 삽입이 O(1)에 이루어진다.
- 하지만, LinkedList는 중간에 값을 넣어줘야하는 경우에 처음 요소부터 위치를 찾아가야한다는 단점이 있다. ~> 원소 삽입 / 삭제 시 O(n)의 시간이 추가 발생 (Search가 O(n))
- 따라서, 어떠한 값에 대한 access가 주로 이루어진다면 Array가, 단순 삽입 삭제 시에는 LinkedList가 용이하다.