ch5 이중 연결 리스트

[jeongabae]

5.1 성능 프로파일 결과

추정 기울기 - 문제크기와 실행시간 사이 관계의 지수 앞자리를 의미

개별 add메서드의 평균 시간은 상수 시간 또는 O(1)

프로파일 결과 예시 ->> ArrayList의 시작에 새로운 요소를 추가하는 연산의 문제 크기 대비 실행시간 그래프

[jeongabae]

5.2 LinkedList 메서드 프로파일하기

LinkedList 시작에 n번 추가하는 연산의 전체 시간 ---> 선형

[jeongabae]

5.3 LinkedList 끝에 더하기

[jeongabae]

5.4 이중 연결 리스트

이중 연결 리스트

• 각 노드는 다음 노드와 이전 노드에 대한 참조를 포함함
• LinkedList 객체는 첫 번째 마지막 요소에 대한 참조를 포함함 --> 리스트의 어느 한쪽 끝에서 시작하여 어느 방향으로든 순회할 수 있음 --> 상수 시간으로 리스트의 시작과 끝에 요소를 추가, 삭제 가능

[jeongabae]

5.5 자료구조 선택하기

• 이중 연결 리스트 구현은 ArrayList 클래스보다 시작에 요소를 추가, 삭제하는 연산이 좋음. -->따라서, ArrayList 클래스의 유일한 이점은 get과 set메서드(실행시간이 get,set 메서드에 의존시 좋음) -->LinkedList 클래스(실행시간이 시작이나 끝 근처에 요소 추가, 제거 연산에 의존시 좋음) ()의 추천 기준은 큰 문제의 증가 차수 if 연산이 실행시간에 영향 미치지 않는다면, 리스트 구현 선택은 의미 x if 작업하는 리스트가 매우 크지 않으면, 기대하는 성능 얻기 어려움 *** 공간을 잊지말기. 실행시간을 중점으로 봤지만, 다른 구현은 다른 양의 공간이 필요함. (메모리 여기저기에 노드가 흩어져 있으면 효율이 떨어질수 있음)

• 연결 리스트는 이중 연결 리스트 일때도 선형시간이 필요

알고리즘 분석은 자료 구조 선택하는 지침을 제공 !3가지 전제 조건이 성립할 때만!

1. 응용 프로그램의 실행시간이 중요
2. 응용프로그램의 실행시간이 선택한 자료구조에 의존
3. 증가 차수에 따라 어느 자료구조가 나은지 실제로 예측할 수 있을 만큼 문제 크기가 충분히 큼