3.2.2 이중 연결리스트 만들기

이번에는 노드에 링크가 두 개 있는 이중 연결리스트를 만듭시다. 그리고 연결리스트의 head와 tail이 가리키는 노드를 초기에 만들기로 할게요.

링크가 두 개 있으면 이전 노드의 위치 정보를 갖고 있으므로 삭제나 추가할 때 이전 노드의 위치를 기억하는 변수를 별도로 선언할 필요가 없습니다.

그리고 연결리스트 초기화 과정에서 head와 tail이 가리키는 각 노드를 초기에 만들면 자료를 보관하는 노드를 맨 앞이나 맨 뒤에 보관하지 않아 연산을 단순하게 표현할 수 있습니다. 이 부분은 실제 구현하면서 설명하기로 할게요.

참고로 자료를 보관할 목적이 아닌 연결리스트를 운영하기 쉽게 생성한 노드를 더미 노드(Dummy Node)라 부릅니다. 여기서 만들 이중 연결리스트는 head와 tail이 더미 노드를 가리키게 할 거예요.

제공할 기능은 생성자, 해제화, 맨 뒤에 보관, 맨 앞에 보관, 원하는 위치에 보관, 탐색 가능한 반복자 제공, 데이터 제거, 데이터 보관 유무 확인, 전체 보기 기능입니다.이중 연결리스트

이제 연결리스트를 구현합시다. 클래스 이름은 DoubledLinkedList로 정하기로 해요.

먼저 노드를 정의합시다. 이번에는 노드에 링크가 두 개 있어야겠죠.이중 연결리스트의 노드

맨 앞의 노드의 위치와 맨 뒤의 노드의 위치를 기억할 멤버 필드를 선언하세요.

연결리스트에 보관한 데이터를 탐색하기 위한 반복자를 제공합시다. 클래스 이름은 Iterator로 할게요.

생성자를 구현합시다.

생성자에서는 더미 노드를 생성하여 head와 tail에 설정하고 링크를 조절합니다.이중 연결리스트 초기화

소멸자를 구현합시다.

순차 보관하는 PushBack 메서드를 구현합시다.

순차 보관은 tail 앞에 새로운 노드를 연결해야겠죠. 연결하는 메서드는 별도로 정의하기로 해요. 더미있는 이중 연결리스트에서는 언제나 head와 tail은 더미 노드를 가리키고 있습니다. 따라서 새로 추가하는 노드는 연렬리스트 중간에 보관하는 것을 보장해요.

여기에서는 순차 보관, 맨 앞 보관, 특정 위치 앞에 보관하는 기능을 제공할 것이며 새로 생성한 노드를 연결하는 논리는 같아서 별도의 메서드로 정의하는 것입니다.

맨 앞에 보관하는 PushFront 메서드를 구현합시다. HangNode는 맨 마지막에 작성할게요.

특정 노드 앞에 보관하는 Insert 메서드를 구현합시다.

탐색에 사용할 반복자를 구하는 기능을 제공해야 합니다. 탐색을 시작하는 반복자와 탐색을 끝낼 조건의 반복자를 제공하세요.

탐색에 사용할 마지막 반복자를 구하는 기능을 제공합시다.

탐색에 사용할 마지막 반복자는 tail입니다. tail이 가리키는 노드가 더미 노드임을 주의하세요. 여기에서 End는 탐색하는 로직에서 반복문을 탈출할 조건에 사용할 것이므로 실제 자료를 보관하는 마지막 노드의 다음 위치를 의미합니다.

보관한 자료를 찾아 노드를 제거하는 Erase 메서드를 구현합시다.

이 곳에 도달하였다면 pos가 tail이 아니므로 삭제할 노드를 탐색하였을 때입니다. 이중 연결리스트에서 노드 삭제

존재하는지 확인하는 기능에서도 head의 다음 노드부터 tail 이전까지 확인하세요.

전체 자료를 출력하는 메서드를 구현합시다.

여기서부터 내부에서 사용할 멤버입니다.

특정 노드 앞에 노드를 연결하는 메서드를 구현합시다.노드 연결하기

사용하기 편하게 타입 재지정하세요.

테스트 코드를 작성하고 테스트 해 보세요.

▷ 실행 결과