인프런 커뮤니티 질문&답변
작성한 질문수
연결리스트 삭제 중 시간 복잡도 계산
해결된 질문
작성
·
27
0
public E remove(int index) {
Node<E> removeNode = getNode(index);
E removedItem = removeNode.item;
if (index == 0) {
head = removeNode.next;
} else {
Node<E> prev = getNode(index - 1);
prev.next = removeNode.next;
}
removeNode.item = null;
removeNode.next = null;
size--;
return removedItem;
}
private Node<E> getNode(int index) {
Node<E> curr = head;
for (int i = 0; i < index; i++) {
curr = curr.next;
}
return curr;
}MyLinkedList 클래스에 정의된 메서드 중 일부입니다.
링크드리스트의 경우 맨 앞 노드를 삭제하는 경우 참조의 조정만으로 삭제할 수 있어 O(1)이 소요된다고 배웠습니다.
연결리스트 내부의 필드로 가지고 있는 first를 활용해 바로 참조하지 않고 getNode()를 사용하면 메서드가 갖는 시간 복잡도를 따르지 않나요?
getNode()는 평균적으로 O(n)이 걸리는 메서드라 생각해서 이 메서드가 사용되는 remove()의 경우 마찬가지로 O(n)인지, 어차피 getNode()를 사용해도 인덱스 1이니 O(1)로 간주하는지 궁금합니다.
답변 1
0
안녕하세요. 티티티님, 공식 서포터즈 y2gcoder입니다.
말씀하신 것이 맞습니다. 인덱스가 0인 경우에는 getNode(0)이 단 한 번의 접근만 하기 때문에 실제로 O(1) 시간에 첫 번째 노드를 반환합니다. 그래서 첫 번째 노드를 삭제할 때는 getNode()를 호출해도 O(1) 작업만 수행되고, 찾은 노드에 대한 참조를 조정하는 작업 또한 또한 O(1)이므로 첫번째 노드 추가 연산에 대한 시간복잡도 O(1)입니다.
다만, 임의의 인덱스에 대해 삭제하는 경우에는 getNode()가 해당 인덱스까지 노드를 순차적으로 탐색하므로 평균적으로 O(n)의 시간복잡도가 됩니다. 따라서 삭제하려는 노드의 위치에 따라 시간복잡도가 달라진다는 점을 이해하는 것이 중요합니다.
결론적으로, 첫번째 노드를 삭제할 때는 O(1)로 간주하는 것이 맞습니다.
감사합니다.
잘 접근했었군요! 감사합니다!