싱글리 링크드 리스트 연산의 시간 복잡도

싱글리 링크드 리스트의 접근, 탐색, 삽입, 삭제 연산에 대하여 시간 복잡도를 알아보자 싱글리 링크드 리스트의 접근 연산 링크드 리스트의 접근 연산은 해당 노드에 바로 접근이 불가하다 head에서부터 차근차근 다음 노드로 가서 원하는 노드에 접근을 해야 한다 인덱스 x에 있는 노드에 접근하려면 head에서부터 x번 가야 한다 원하는 노드에 접근하는데 걸리는 시간이 몇 번째 인덱스인지에 비례하는 것이다 링크드 리스트 안에 있는 노드의 수를 n이라고 하면 마지막 노드에 접근하려면 head에서부터 총 n-1번을 가야 한다 그러므로 접근 연산은 최악의 경우 O(n)의 시간 복잡도를 갖는다 싱글리 링크드 리스트의 탐색 연산 링크드 리스트의 탐색 연산은 선형 탐색을 이용한다 가장 앞에서부터 다음 노드를 하나씩 보면..