O(1)
이다.O(n)
이다.O(n)
의 시간이 걸리는 것을 보완하기 위해 나왔다.O(n)
이다.O(1)
이지만, 해당 요소를 찾기 위해 O(n)
이 요소되므로 결국 O(n)
이다.위에서 Array와 Linked List의 접근, 삽입, 삭제에 걸리는 시간 복잡도를 알아봤는데 이는 사실 어느 상황이냐에 따라 조금씩 다르다. 다음 표를 첨부할테니 살펴보고 왜 그런지에 대해서도 한 번 생각해보면 좋을 것 같다.
Array List | Linked List | |
---|---|---|
접근 | ⍬(1) | ⍬(n) |
맨 앞에서의 삽입/삭제 | ⍬(n) | ⍬(1) |
맨 뒤에서의 삽입/삭제 | ⍬(1) | 마지막 요소를 알고 있을 때 ⍬(1) 마지막 요소를 모르고 있을 때 ⍬(n) |
임의의 위치에서 삭입/삭제 | ⍬(n) | 탐색시간 + ⍬(1) |
최악의 경우 | ⍬(n) | ⍬(n) |
(출처: https://sdesigner.tistory.com/73)