이중 연결 리스트 & List 자료구조 선택하기

>>>>>>> 소스코드.git

이중 연결 리스트

이중 연결 리스트를 구현한 MyLinkedList 클래스는 단일 연결 리스트를 사용한다. 즉, 각 요소는 다음 요소에 대한 참조만 포함하고 MyLinkedList 객체 자체는 첫 번째 노드에 대한 참조만 가지고 있다.

 

하지만 여기에서 LinkedList 클래스에 대한 문서를 읽어보면 다음과 같은 내용이 나온다.

 

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

 

이중 연결 리스트를 잘 모른다면 요약한 다음 내용을 확인하자.

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

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

 

다음 표는 ArrayList와 MyLinkedList(단일 연결), 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 메서드이다. 연결 리스트는 심지어 이중 연결 리스트일 때도 선형 시간이 필요하다.

 

응용 프로그램의 실행시간이 get과 set 메서드에 의존한다면 ArrayList 클래스가 좋은 선택이다. 실행시간이 시작이나 끝 근처에 요소를 추가하거나 제거하는 연산에 의존한다면 LinkedList 클래스가 좋다.

 

하지만 이러한 추천은 큰 문제의 증가 차수에 기반을 두고 있다. 이 외에 고려해야 할 요소는 다음과 같다.

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

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

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