원형 이중 연결 리스트 만들기

지난 글 : [알고리즘/Do it 알고리즘] - 배열 커서로 연결 리스트 만들기

 

원형 리스트 살펴보기

head
 ↓
 A → B → C → D → E → F
 ↑                   ↓
 ↑←←←←←←←←←←←←←←←←←←←←

위 그림처럼 꼬리 노드가 머리 노드를 가리키는 연결 리스트를 원형 리스트(circular list)라 한다. 원형 리스트는 고리 모양으로 나열된 데이터를 저장할 때 알맞은 자료구조다.

 

보통의 연결 리스트와 다른 점은 꼬리 노드의 다음 노드를 가리키는 포인터가 null이 아니라 머리 노드의 포인터라는 점이다. 개별 노드의 자료형은 보통의 연결 리스트와 같다.

 

이중 연결 리스트 살펴보기

연결 리스트의 가장 큰 단점은 다음 노드는 찾기 쉽지만 앞쪽 노드는 찾기 어렵다는 것이다. 이런 단점을 개선한 자료구조가 이중 연결 리스트(doubly linked list)다. 아래처럼 각 노드에는 다음 노드에 대한 포인터와 앞쪽 노드에 대한 포인터가 주어진다.

head
 ↓
 A → B → C → D → E → F
    ←   ←   ←   ←   ←

이중 연결 리스트의 노드는 3개의 필드가 있는 클래스 Node<E>로 구현할 수 있다.

- data : 데이터(데이터 참조 : 형(type)은 E)
- prev : 앞쪽 포인터(앞쪽 노드 참조 : 형(type)은 Node<E>)
- next : 뒤쪽 포인터(뒤쪽 노드 참조 : 형(type)은 Node<E>)

 

원형 이중 연결 리스트 만들기

원형 리스트와 이중 연결 리스트를 조합한 원형 이중 연결 리스트를 구현해보자.

 

노드 클래스 Node<E>

노드 클래스는 리스트 클래스 안에서 선언한다. 노드 클래스 Node<E>에는 위에서 설명한 3개의 필드 data, prev, next 외에 아래와 같은 2개의 생성자가 있다.

1. Node()
   데이터 data가 null이고 앞쪽 포인터와 뒤쪽 포인터가 모두 this인 노드를 생성한다. 자기 자신의 노드가
   앞쪽 노드이면서 동시에 다음 노드가 된다.
2. Node(E obj, Node<E> prev, Node<E> next)
   데이터 data가 obj고 앞쪽 포인터가 prev, 뒤쪽 포인터가 next인 노드를 생성한다.

 

원형 이중 연결 리스트 클래스 DoubleLinkedList<E>

원형 이중 연결 리스트를 나타내는 클래스다. 이전에 배운 연결 리스트 클래스 LinkedList<E>와 마찬가지로 2개의 필드를 갖는다.

- head : 머리 포인터(머리 노드 참조 : 자료형은 Node<E>)
- crnt : 선택 포인터(선택 노드 참조 : 자료형은 Node<E>)

 

생성자 DoubleLinkedList 메서드

생성자는 비어 있는 원형 이중 연결 리스트를 생성한다. 이때 데이터를 갖지 않는 노드를 1개만 만든다. 이 노드는 노드의 삽입과 삭제를 원할하게 처리하기 위해 리스트의 머리에 계속 존재하는 더미 노드다.

 

노드를 생성할 때 new Node<E>()로 생성자(Node())를 호출하므로 더미 노드의 prev와 next는 자기 자신의 노드를 가리키도록 초기화된다. 그리고 head와 crnt 또한 이때 생성한 더미 노드를 가리킨다.

 

리스트가 비어 있는지 조사하는 메서드 isEmpty

리스트가 비어 있는지(더미 노드만 있는지)를 조사하는 메서드다. 더미 노드의 뒤쪽 포인터 head.next가 더미 노드인 head를 가리키고 있으면 리스트는 비어 있는 것이다. 만약 비어 있는 리스트라면 head, head.next, head.prev 모두 더미 노드를 가리킨다(모두 head와 같은 값이 된다). 리스트가 비어 있으면 true, 그렇지 않으면 false를 반환한다.

 

노드를 검색하는 메서드 search

노드를 선형 검색하는 메서드다.

머리 노드부터 시작해 뒤쪽 포인터를 차례로 따라가며 스캔하는 과정은 연결 리스트 클래스 LinkedList<E>의 search 메서드와 거의 같다. 다만 실제 머리 노드가 더미 노드의 다음 노드이므로 검색을 시작하는 곳이 다르다. head는 더미 노드를 가리키고 있고, 더미 노드의 뒤쪽 포인터가 가리키는 노드가 진짜 머리 노드이기에 검색은 head가 아닌 head.next에서 시작한다.

 

Node<E>인 변수 a, b, c, d, e가 각각 노드 A, 노드 B, ..., 노드 E를 가리키고 있을 때 각 노드를 가리키는 식은 아래와 같다. 여기서 같은 줄의 참조식은 모두 같은 노드를 가리킨다.

while문으로 스캔하는 과정에서 comparator c의 compare 메서드로 비교한 결과가 0이면 검색 성공이다. ptr이 가리키는 노드의 데이터 data를 반환한다. 이때 선택 포인터 crnt가 찾은 노드 ptr을 가리키도록 업데이트한다. 원하는 노드를 찾지 못하고 스캔이 한 바퀴 돌아 다시 머리 노드로 돌아올 때(ptr이 head가 되었을 때) while문이 끝난다. 검색에 실패했으므로 null을 반환한다. 

 

빈 리스트를 검색할 때 이 메서드가 정말 검색에 실패하는지(null을 반환하는지) 알아보자. 메서드의 첫 머리에서 ptr에 대입하는 head.next가 더미 노드를 가리킨다. 다시말해 head와 같은 값이 ptr에 대입된다. 그럼 while문의 제어식 ptr != head가 성립되지 않아 while문의 본문을 실행하지 않고 바로 null을 반환해 메서드를 종료한다.

 

 

선택 노드를 출력하는 메서드 printCurrentNode

선택 노드를 출력하는 메서드로, 선택 노드의 데이터 crnt.data를 출력한다. 리스트가 비어 있으면 '선택 노드가 없습니다.'라 출력한다.

 

모든 노드를 출력하는 메서드 dump

리스트에 있는 모든 노드를 머리부터 꼬리까지 순서대로 출력하는 메서드다. head.next부터 스캔을 시작해 뒤쪽 포인터를 따라가며 각 노드의 데이터를 출력한다. 한 바퀴 돌아 head로 돌아오면 스캔을 끝낸다.

 

모든 노드를 거꾸로 출력하는 메서드 dumpReverse

리스트의 모든 노드를 꼬리부터 머리까지 거꾸로 출력하는 메서드다. head.prev부터 스캔을 시작해 앞쪽 포인터를 따라가며 각 노드의 데이터를 출력한다. 한 바퀴 돌아 head로 되돌아오면 스캔을 끝낸다. 

 

선택 노드를 뒤쪽으로 진행하는 메서드 next

선택 노드를 하나 뒤쪽의 노드로 나아가도록 하는 메서드다. 리스트가 비어 있지 않고 선택 노드에 다음 노드가 있을 때만 선택 노드가 진행한다. 선택 노드가 진행하면 true, 그렇지 않으면 false를 반환한다.

 

선택 노드를 앞쪽으로 진행하는 메서드 prev

선택 노드를 하나 앞쪽의 노드로 나아가도록 하는 메서드다. 리스트가 비어 있지 않고 선택 노드에 앞쪽 노드가 있을 때만 선택 노드가 진행한다. 선택 노드가 진행하면 true, 그렇지 않으면 false를 반환한다.

 

 

노드를 삽입하는 메서드 add

선택 노드의 바로 뒤에 노드를 삽입하는 메서드로, 다른 메서드의 요청을 받아 삽입을 대신 처리하기도 한다. 

 

머리에 노드를 삽입하는 메서드 addFirst

리스트의 머리에 노드를 삽입하는 메서드다. 더미 노드의 바로 뒤에 노드를 삽입하므로 선택 포인터 crnt가 가리키는 곳을 head로 업데이트한 후에 add 메서드를 호출한다.

 

꼬리에 노드를 삽입하는 메서드 addLast

리스트의 꼬리에 노드를 삽입하는 메서드다. 꼬리 노드 바로 뒤에 있는 더미 노드의 바로 앞에 노드를 삽입하므로 선택 포인터 crnt가 가리키는 곳을 head.prev로 업데이트 한 후 add 메서드를 호출한다.

 

 

선택 노드를 삭제하는 메서드 removeCurrentNode

선택 노드를 삭제하는 메서드로, 다른 삭제 관련 메서드가 삭제를 요청하면 대신 처리하기도 한다. 더미 노드는 삭제할 수 없으므로 먼저 리스트가 비어 있는지 확인하고 리스트가 비어 있이 않을 때만 삭제한다. 

 

임의의 노드를 삭제하는 메서드 remove

p가 참조하는 노드를 삭제하는 메서드다. 삭제는 리스트가 비어 있지 않고 인수가 가리키는 노드 p가 있을 때만 처리한다. while문으로 모든 노드를 스캔하는 과정에서 노드 p를 찾으면 crnt가 가리키는 곳을 p로 업데이트하고 removeCurrentNode 메서드를 호출한다.

 

머리 노드를 삭제하는 메서드 removeFirst

머리 노드를 삭제하는 메서드다. crnt가 가리키는 곳을 실질적인 머리노드 head.next로 업데이트하고 removeCurrentNode 메서드를 호출한다.

 

꼬리 노드를 삭제하는 메서드 removeLast

꼬리 노드를 삭제하는 메서드다. crnt가 가리키는 곳은 꼬리 노드 head.prev로 업데이트하고 removeCurrentNode 메서드를 호출한다.

 

모든 노드를 삭제하는 메서드 clear

더미 노드를 제외한 모든 노드를 삭제하는 메서드다. removeFirst로 리스트가 빌 때까지 반복해 머리 노드를 삭제한다. 그 결과 crnt가 가리키는 곤은 더미 노드 head로 업데이트된다.

 

원형 이중 연결 리스트를 사용하는 프로그램 만들기

아래는 원형 이중 리스트를 사용하는 프로그램이다.

 

참고 서적 :