탐색은 목표를 찾거나 None에 닿을 때까지 비교하고 이동한다
목표값이 리스트의 어디에 있는지에 따라 멈추는 위치와 비교 횟수가 달라진다.
current = headwhile current is not Noneif current.data == target: return Truecurrent = current.nextreturn False
현재 상태
목표값
비교 횟수
현재 결과
목표가 뒤에 있을수록 비교 횟수가 늘고 없으면 항상 n회다
노드 수를 바꾸면 각 위치를 찾는 데 필요한 비교 횟수도 함께 바뀐다. 평균은 목표가 리스트 안의 각 위치에 같은 확률로 있다고 가정한 값이다.
목표가 있을 때 평균 비교 횟수
노드 수
목표가 있는 경우의 평균 비교 횟수는 (n + 1) / 2이다. 목표가 없으면 항상 n회 비교한다. 첫 노드에서 찾는 최선의 경우는 Θ(1)이다. 마지막 노드나 없는 값을 확인하는 최악의 경우는 Θ(n)이다.