Linked List의 삽입/삭제 시간 복잡도에 관해서

Question

안녕하세요!데이터를 삽입 및 삭제할 때, Linked List 의 최악의 시간복잡도에 대해서... 헷갈려서 질문드립니다. 제가 알고 있는 것을 말해보자면- Linked List 는 각 원소들은 자기 다음이 어떤 원소인지만 기억하고 있고, 삽입/삭제를 O(1) 만에 할수있다.- 근데 Linked List는 순차접근(무조건 처음부터 접근) 방식이기 때문에- 삽입/삭제를 하려는 위치를 찾기위해 첨부터 탐색해야 하므로, 그 원소를 찾기 위해 추가적으로 시간이 들어서 결국 O(n) 이 된다.- 그래서 결국 Linked List의 삽입/삭제의 worst case는 O(n)이다. 로 알고있습니다. 근데 http://bigocheatsheet.com/ 싸이트에 내용을 보면, Singly-Linked-List의 삽입/삭제 부분이 O(1)로 되어있더라고요. 이것을 어떻게 이해를 해야 할까요..? 헷갈리네요 ㅠㅠ

yeori · Accepted Answer

- 근데 Linked List는 순차접근(무조건 처음부터 접근) 방식이기 때문에 - 삽입/삭제를 하려는 위치를 찾기위해 첨부터 탐색해야 하므로, 그 원소를 찾기 위해 추가적으로 시간이 들어서 결국 O(n) 이 된다.이거는 탐색&#43; 수정(삽입, 삭제)을 한꺼번에 합쳐서 말하는거구요...아래의 문장은....근데 http://bigocheatsheet.com/ 싸이트에 내용을 보면, Singly-Linked-List의 삽입/삭제 부분이 O(1)로 되어있더라고요.수정(삽입,삭제)에 대해서만 말하는겁니다.만일 탐색이 필요없는 경우, 예를 들어서 맨 앞에 추가하고 맨 앞에서만 삭제하는 경우라면 탐색 비용이 없기때문에 탐색&#43;수정은 O(1)이 됩니다.

Hide_D · Answer

말씀하신 방법으로라면 O(n)이 맞습니다. 그러니 보통 Singly-Linked List는 Queue로만 쓰게 되고, 대부분 Doubly-Linked List만 쓰게 되죠. 다만 삭제하려는 원소의 이전 노드가 무엇인지 확인하는 것은 Access에 해당하는 것이고,이전, 현재, 다음 노드를 알고 있을 때 삭제하는 것 자체만 따질 때 O(1)로 보는 듯 하네요.

noter · Answer

이해했어요. :) 답변 감사드립니다. 좋은 하루 되세용^_^

Linked List의 삽입/삭제 시간 복잡도에 관해서

3개의 답변

#linkedlist 목록