3.2.1 단순 연결리스트 만들기

이번에는 간단하게 단순(단일) 연결리스트를 만들어 보아요. 여기에서 만드는 단순 연결리스트는 개념을 잡기 위해 만드는 것으로 노드에 보관할 자료 형식을 정수로 한정할게요. 뒤에서 STL을 모델로 list를 만들 때 어떠한 자료 형식도 보관할 수 있게 만들거예요. 

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

단순 연결리스트를 정의할 클래스 이름을 SimpleLinkedList라 정합시다.

단순 연결리스트의 노드는 데이터와 다음 노드의 위치 정보를 기억하는 링크로 구성합니다.

노드는 데이터와 링크로 구성

노드는 연결리스트에서 접근하기 쉽게 구조체로 정의합시다. 사용하는 개발자는 노드 형식을 알 필요가 없습니다. 따라서 Node 형식은 디폴트 가시성인 private으로 접근 지정할게요.

여기에서는 연결리스트의 맨 앞의 노드의 위치 정보와 맨 마지막 노드의 위치 정보를 기억하는 멤버 head와 tail이 있는 구조로 정의하기로 해요.단순 연결리스트의 맨 앞 노드 위치 정보를 head, 마지막 노드위 위치 정보를 tail이라 정의합시다.

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

생성할 때 노드가 없으므로 head와 tail을 0으로 초기화합니다.

단일 연결리스트를 생성할 때 head와 tail은 0으로 초기화

맨 앞의 노드부터 순차적으로 소멸합시다. 그런데 노드를 소멸한 후에 다음 노드의 위치를 알 수 없기 때문에 노드의 위치를 이동한 후에 이전 노드를 지우는 형태로 작성해야 합니다.연결리스트를 소멸할 때는 맨 앞 노드부터 소멸하세요.

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

비어있는 상태라면 head와 tail이 새로 생성한 노드를 가리키게 설정하세요.

비어있는 상태에서 PushBack 하면 head와 tail이 같은 노드를 가리킵니다.

보관한 자료가 있을 때는 tail의 next 링크를 새로운 노드를 가리키게 하고 tail을 새로운 노드로 설정합니다.

보관한 자료가 있을 때는 tail의 next 링크를 새로운 노드를 가리키게 하고 tail은 새로운 노드로 설정하세요.

맨 앞에 보관하는 PushFront 메서드를 구현합시다.

이미 자료가 있을 때 맨 앞에 보관하려면 새로운 노드의 next와 head를 변경해 주어야 합니다.자료가 있을 때 맨 앞에 보관할 때는 새로운 노드의 next 링크를 head로 설정하고 head를 새로운 노드로 설정합니다.

특정 노드 뒤에 자료를 보관하는 기능을 구현합시다. 사용하는 개발자는 반복자를 이용하여 원하는 위치를 찾은 후에 반복자와 보관할 자료를 전달합니다.

이전 노드가 있을 때 새로운 노드의 next와 이전 노드의 next를 변경해 주어야 합니다.이전 노드가 있을 때 InsertNext

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

자료를 삭제하는 Erase 메서드를 구현합시다. 노드를 삭제하려면 이전 노드의 링크를 변경해야죠.

노드를 링크에서 제거하기

만약 원하는 자료가 없다면 seek는 0이므로 메서드를 반환합니다.

이전 노드가 있다면 이전 노드의 next 링크를 seek의 next로 설정합니다.

prev가 참일 때

prev가 0이라는 것은 seek가 head라는 것입니다. 따라서 head를 seek의 다음 노드를 가리키게 설정하세요.

prev가 0일 때

만약 삭제할 노드가 맨 마지막 노드일 때는 tail을 이전 노드를 가리키게 설정해야겠죠. prev의 next 링크를 설정하는 것은 if(prev) 조건문에서 수행하였기 때문에 여기에서는 tail 만 변경하세요.맨 마지막 노드 삭제

seek를 소멸하세요.

존재하는지 확인하는 메서드는 삭제할 때 삭제할 노드를 찾는 부분과 흡사합니다.

전체 보기 기능도 head가 가리키는 노드부터 순차적으로 방문하여 출력합니다.

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

 

간단하게 정상적으로 동작하는지 테스트 하세요.

▷ 실행 결과