자바로 배우는 핵심 자료구조와 알고리즘: 기술 면접에 필요한 실용주의 자료구조와 알고리즘

55

5

장

이중 연결 리스트

이 장에서는 앞 장의 실습 결과를 살펴보고

List

인터페이스를 구현하는 또 다른 클래스인 이

중 연결 리스트

doubly

linked

list

에 대해 알아봅니다.

5.1

성능 프로파일 결과

앞 장의 실습에서

Profiler.java

파일로 다양한

ArrayList

와

LinkedList

자료구조의 연

산을 문제 크기별로 실행해 보았습니다. 그리고

log

-

log

스케일로 문제 크기 대비 실행시간의

그래프를 그리고 결과 곡선의 기울기를 추정하였습니다. 추정 기울기는 문제 크기와 실행시간

사이 관계의 지수 앞자리를 의미합니다.

예를 들어,

ArrayList

의 끝에 요소를 더하는

add

메서드를 사용하였을 때

n

번 추가 연산의 전

체 시간은

n

에 비례하였습니다. 즉, 추정 기울기는

1

에 가까웠습니다. 결국,

n

번 추가 연산은

O

(

n

)으로 결론지었습니다. 따라서 개별

add

메서드의 평균 시간은 상수 시간 또는

O

(

1

)이

고, 이것은 알고리즘 분석을 기반으로 예상한 내용과 일치합니다.

이 실습은

profileArrayListAddBeginning

메서드를 작성하여

ArrayList

의 시작에 새로운

요소를 추가하는 연산의 성능을 테스트합니다. 앞의 분석에 근거하여 각

add

메서드는 선형이

어야 합니다. 이는 다른 요소들을 오른쪽으로 시프트하기 ...