LinkedList 클래스

보통 다음 Node가 null이 아닌지 확인해야 하지만, 이 경우에는 리스트 끝까지 가면 반복문이 종료되므로 안전합니다. (size 변수는 리스트의 실제 노드 개수와 일치한다고 가정합니다.) 목적 값을 찾지 못하면 -1을 반환합니다. 

 

이 메서드의 실행시간은 리스트의 크기에 비례 (O(n)) 합니다.

add 메서드의 증가 차수는?

1. getNode 메서드가 indexOf 메서드와 유사하므로 같은 이유로 선형입니다.

2. add메서드에서 getNode 메서드 전과 후 모두가 상수 시간입니다. 

 

remofw 메서드의 모든 것은 선형인 get과 getNode 메서드를 제외하면 상수 시간입니다.

따라서 remove 메서드는 선형입니다. 

 

두 개의 선형 메서드를 보면 때때로 결과를 이차로 생각하지만, 이것은 어떤 연산이 다른 연산 내부에 중첩되었을 때만 해당합니다. 어떤 연산에 이어 다른 연산을 호출하면 실행시간은 더해집니다. 이 연산이 둘 다 O(n)이라면 합 또한 O(n)이 됩니다.