[일반] 링크드 리스트 삭제연산의 시간복잡도는 O(n)임? 아니면 O(1)임?

[익명(222.118)]

삭제하는 것 자체는 O(1) 이지만 삭제하는 것 찾는 데까지 걸리는 시간복잡도가 O(n) 이잖아

만약 링크드 리스트의 시간복잡도를 물어보면 뭐라고 대답해야함?

[익명(222.118)]

찾는것도 어떻게 찾느냐에따라서 logn이 될수도 있기도 하니까 삭제 자체에 포커스를 둬야하나

[익명(182.172)]

답 자체는 O(1)인데, 조금 더 명확하게 이야기하려면 iterator 기반으로 리스트 내에서 이미 삭제할 위치 정보를 알고 있는 상황이면 O(1)이고, 그게 아니라 리스트 자체를 접근해서 삭제하는 경우는 O(N)이라고 답하면 돼

[익명(182.172)]

그리고 링크드리스트 찾는건 logn이 될 수 없어. O(N)이 맞아

[백갤러 1(182.172)]

https://colorscripter.com/s/KaDQFKE

[백갤러 1(182.172)]

list.remove 부분은 매번 head에서부터 10번째 위치를 탐색하고 해당 위치를 지워줘서 O(N)이고, Iterator 선언해서 head로부터 10번째 위치로 움직인 다음에 list.next()와 list.remove()로 지워주는 부분은 O(1)이야

[익명(222.118)]

생각해보니까 logn은 안되네 정렬된 배열의 탐색같은거로 생각해서 오해햇엇음

[익명(222.118)]

첫번째 댓글로 명확하게 알게된듯

[익명(222.99)]

삭제 연산 시간복잡도는 삭제라는 연산 자체의 행위와 그 후 재배열 연산에 관계함. 링크드 리스트의 경우 삭제 후 다른 재배열 연산이 없기 때문에 O(1)임. 탐색+삭제 연산이 O(N)인거지, 삭제연산 자체는 O(1)시간에 이루어지는게 맞음