이중 연결 리스트

시작에 요소를 추가하는 연산은 LinkedList 클래스가 ArrayList 클래스보다 빠릅니다. 하지만 요소를 끝에 더하는 것은 LinkedList가 더 느립니다.

 

이중 연결 리스트

-각 노드는 다음 노드와 이전 노드에 대한 참조를 포함합니다.

-LinkedList 객체는 첫 번째와 마지막 요소에 대한 참조를 포함합니다.

따라서 리스트의 어느 한쪽 끝에서 시작하여 어느 방향으로든 순회할 수 있습니다.

 

<<자료구조 선택하기>>

이중 연결 리스트 구현은 ArrayList 클래스보다 시작에 요소를 추가하고 삭제하는 연산이 좋습니다. 끝에 요소를 추가하고 제거하는 연산은 ArrayList 클래스와 동일합니다. 따라서 ArrayList 클래스의 유일한 이점은 get과 set 메서드입니다. 연결 리스트는 심지어 이중 연결 리스트일 때도 선형 시간이 필요합니다. 

 

응용 프로그램의 실행시간이 get과 set 메서드에 의존한다면 ArrayList 클래스가 좋은 선택입니다. 실행시간이 시작이나 끝 근처에 요소를 추가하거나 제거하는 연산에 의존한다면 LinkedList 클래스가 좋습니다. 하지만 이러한 추천은 큰 문제의 증가 차수에 기반을 두고 있습니다. 

-작업하는 리스트가 매우 크지 않으면 기대하는 성능을 얻기 어려울지도 모릅니다. 

-공간에 대해서 잊지 마세요.  다른 구현은 다른 양의 공간이 필요합니다. 

 

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

1. 응용 프로그램의 실행시간이 중요하다.

2. 응용 프로그램의 실행시간이 선택한 자료구조에 의존한다. 

3. 증가 차수에 따라 어느 자료구조가 나은지 실제로 예측할 수 있을 만큼 문제 크기가 충분히 크다.