그림으로 봅시다.

▲ 그림 4-5 연결 리스트의 탐색

그림 4-5를 보면, 먼저 cur 변수를 두어 리스트의 첫 노드를 가리키게 합니다. 그리고 찾고자 하는 값 4와 노드 값을 비교합니다. 첫 번째 노드 값은 1이므로 4가 아닙니다. 그럼 link를 통해 다음 노드로 이동해서 다시 비교합니다. 이 과정을 4를 찾을 때까지 진행합니다. 최악의 경우 리스트 마지막까지 비교해야겠지요. 데이터 개수가 n개라면 n번 비교해야 합니다. 그래서 빅오는 O(n)입니다.

지금까지 연결 리스트를 간단히 알아보았습니다. 다음 절에서는 동적 배열과 연결 리스트를 간단히 비교해 보겠습니다.