[자바로 배우는 핵심 자료구조와 알고리즘] 5장 이중 연결 리스트

이중 연결 리스트

성능 프로파일 결과

추정 기울기?

• 문제 크기와 실행시간 사이 관계의 지수 앞자리를 의미
• 예
  • ArrayList의 끝에 요소를 더하는 add 메서드를 사용하였을 때 n번 추가 연산의 전체 시간은 n에 비례
    • 추정 기울기 : 1에 가까움
  • n번 추가 연산은 O(n)
  • ArrayList의 시작에 새로운 요소를 추가하는 연산의문제 크기 대비 실행시간 그래프 
    • 이 그래프에서 직선은 알고리즘이 선형임을 의미하지 않음
    • 실행시간이 어떤 지수 k에 대해 n^k에 비례한다면 결과 그래프는 기울기 k인 직선이 됨
    • n번 추가하는 연산의 전체 시간이 n^2에 비례하므로 직선의 기울기는 2가 됨
    • 사실, 추정 기울기는 1.992인데, 데이터를 조작한 것처럼 너무나 정답에 가까움

LinkedList 메서드 프로파일하기

LinkedList 시작에 n번 추가하는 연산의 전체 시간은 선형
LinkedList 시작에 n개 요소를 추가하는 연산의 문제 크기 대비 실행시간 그래프

• 그래프가 직선이 아니고 기울기도 정확히 1이 아님
  • 최소제곱의 기울기도 1.23
• 결과는 LinkedList 시작에 n번 추가하는 연산의 전체 시간이 적어도 O(n)에 근사함을 나타내므로 각 add 메서드는 상수 시간

LinkedList 끝에 더하기

• 시작에 요소를 추가하는 연산 속도 = LinkedList > ArrayList
• 요소를 끝에 더하는 연산 속도 = ArrayList > LinkedList
  LinkedList 끝에 요소를 추가하는 연산의 문제 크기 대비 실행시간 그래프

• 측정값에는 잡음이 많고 선은 완벽한 직선이 아님
  • 추정 기울기 : 1.19
• 요소를 시작에 추가하는 연산과 비슷하지만, 분석에서 추정한 2에는 가깝지 않음
• 1에 가까우며 요소를 끝에 추가하는 각 연산이 상수 시간임을 시사

이중 연결 리스트

• LinkedList 클래스에 대한 문서
  • List와 Deque 인터페이스를 구현하는 이중 연결 리스트 구현
  • 모든 연산은 이중 연결 리스트와 같이 동작합니다.
  • 리스트의 인덱스를 활요하는 연산은 시작 또는 끝부터 리스트를 순회합니다.
  • 이때 어느 것이든 특정 인덱스에서 가까운 것을 선택합니다.

• 각 노드는 다음 노드와 이전 노드에 대한 참조를 포함
• LinkedList 객체는 첫 번째와 마지막 요소에 대한 참조를 포함

따라서, 리스트의 어느 한쪽 끝에서 시작하는 어느 방향으로든 순회할 수 있음
결과적으로 상수 시간으로 리스트의 시작과 끝에 요소를 추가하고 삭제할 수 있음

구분	ArrayList	MyLinkedList	LinkedList
add(끝)	1	n	1
add(시작)	n	1	1
add(일반적으로)	n	n	n
get/set	1	n	n
indexOf/lastIndexOf	n	n	n
isEmpty/size	1	1	1
remove(끝)	1	n	1
remove(시작)	n	1	1
remove(일반적으로)	n	n	n

자료구조 선택하기

이중 연결 리스트 구현은 ArrayList 클래스보다 시작에 요소를 추가하고 삭제하는 연산이 좋음

• 끝에 요소를 추가하고 제거하는 연산은 ArrayList 클래스와 동일

ArrayList 클래스의 유일한 이점은 get/set

• 연결 리스트는 심지어 이중 연결 리스트일 때도 선형 시간이 필요
• 실행시간이 시작이나 끝 근처에 요소를 추가하거나 제거하는 연산에 의존한다면 LinkedList 클래스가 좋음
  • 이러한 추천은 큰 문제의 증가 차수에 기반을 두고 있음

고려해야할 요소

• 이러한 연산이 응용 프로그램의 실행시간에 뚜렷한 영향을 미치지 않는다면, 즉 응용 프로그램이 다른 일을 하느라 대부분 시간을 소모하면 List 구현에 대한 선택은 큰 의미가 없음
• 작업하는 리스트가 매우 크지 않으면 기대하는 성능을 얻기 어려울지도 모름. 작은 문제에서는 이차 알고리즘이 선형 알고리즘보다 빠르기도 하고 또는 선형 알고리즘이 상수 시간보다 빠리곧 함. 작은 문제에서는 그 차이가 그리 중요하지 않음
• 공간에 대해서 잊지 마세요. 지금까지 실행시간에 초점을 맞추었지만, 다른 구현은 다른 양의 공간이 필요함. ArrayList에서 요소들은 한 덩이리의 메모리 안에 나란히 저장되어 거의 낭비되는 공간이 없고, 컴퓨터 하드웨어도 연속된 덩어리에서 종종 속도가 더 빠름. 연결 리스트에서 각 요소는 하나 또는 두 개의 참조가 있는 노드가 필요함. 참조는 공간을 차지.
  메모리 여기저기에 노드가 흩어져 있으면 하드웨어의 효율이 떨어질 수 있음

알고리즘 분석은 자료구조를 선택하는 지침을 제공하지만, 오직 다음 조건일 때만 유효

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