[자바 Do It! 알고리즘]Chapter08 리스트(포인터로 연결 리스트 만들기) (2)

이어서..

(연결리스트는 설명이 기네요.. 요즘 학원진도도 많이 나가서, 알고리즘은 천천히 나가겠습니다. 동빈나 게시판도 해야해서..)

​

연결 리스트가 비어 있는지 판단하는 방법

head == null // 연결 리스트가 비어 있는지 확인합니다.

​

노드가 1개인 연결리스트를 판단하는 방법

head.next == null // 노드가 1개인지 확인합니다.

​

노드가 2개인 연결리스트를 판단하는 방법

head.next.next == null // 노드가 2개인지 확인합니다.

​

꼬리 노드인지 판단하는 방법

p.next == null // p가 가리키는 노드가 꼬린 ㅗ드인지 확인합니다.

​

[검색을 수행하는 search 메서드]

1. search 메서드는 어떤 조건을 만족하는 노드를 검색합니다.

2. 검색에 사용하는 알고리즘은 선형 검색이고 검색할 노드를 만날 때 까지 머리 노드부터 스캔합니다.

3. 노드스캔은 아래의 조건 중 하나만 성립하면 종료됩니다.

조건 1) 검색 조건을 만족하는 노드를 찾지 못하고 꼬리 노드를 지나가기 직전인 경우

조건 2) 검색 조건을 만족하는 노드를 찾은 경우

4. 이 메서드가 전달받는 매개변수는 다음과 같습니다.

1) 첫 번째 매개변수 obj

(1) 검색할 때 key가 되는 데이터를 넣어둔 object

2) 두 번째 매개변수 c

(1) 첫 번째 매개변수와 연결 리스트의 개별 노드 안에 있는 데이터를 비교하기 위한 comparator.comparator c

에 의해 obj와 선택한 노드의 데이터를 비교하여 그 결과가 0이면 검색 조건이 성립하는 것으로 봅니다.

Linkedlist<E> 에 search 메서드 추가

☞ Node<E> ptr = head;

스캔하고 있는 노드를 가리키는 변수 ptr 을 head로 초기화합니다.

ptr이 가리키는 노드는 head가 가리키고 있는 머리 노드인 A입니다.

​

☞ while(ptr!=null) 부분

조건 1(검색 조건을 만족하는 노드를 찾지 못하고 꼬리 노드를 지나가기 직전의 경우)을 먼저 판단합니다.

ptr값이 널이 아니면 루프 본문을 실행합니다.

ptr 값이 널이면 스캔할 노드가 ㅇ벗음을 의미하기 때문에 while문을 빠져나와 return null'을 진행합니다.

​

☞ if(c.compare ~) 부분

조건 2(검색조건을 만족하는 노드를 찾는 경우)를 판단하기 위해 데이터 obj와 스캔하고 있는 노드의 데이터 ptr.data를 comparator c로 비교합니다.

compare 메서드가 반환하는 값이 0이면 종료 조건이 성립하여 검색 성공입니다. 곧바로 crnt에 ptr을 대입하고 찾은 노드의 데이터인 ptr.data를 반환합니다.

​

☞ ptr = ptr.next;

ptr에 ptr.next를 대입합니다. 이렇게 하면 ptr이 다음 노드를 가리키기 때문에 꼐속해서 스캔할 수 있습니다.

​

​