Java-자료구조 2주차 연결리스트 - 2-8 ~10

2주차. 연결리스트

2-8. remove와 find

• find 메소드 - Comparable 인터페이스를 통해 노드 찾기
  -Remove에서 파생(경계조건 신경X)
  -현재 코드가 null이 아닌지 파악 후 존재 여부를 반환한다
  참고)Comparable 인터페이스 - compareTo()
  https://mine-it-record.tistory.com/133

<find 메소드>
-찾는 노드가 포함되는가

public boolean contains(E obj){
	Node<E> current = null;
	while(current != null) { 
		if (((Comparable<E>) obj).compareTo(current.data)==0)// Comparable 인터페이스
			return true; // 존재 시 True 반환
		current = current.next;
	}
	return false; // 존재 안해서 False 반환 
}

• remove 메소드 - Comparable 인터페이스를 통해 제거하고 싶은 노드 제거
  
  <진행 방법>

(1) Comparable 인터페이스를 사용해 노드의 위치 찾기
-여기서 Comparable 인터페이스를 사용한 건 타입이 정해지지 않은 객쳬까라 비교할 때 '=='을 사용하면 객체에 할당된 메모리를 비교하여 옳지 않음
<코드>

public boolean contains(E obj){
	Node<E> current = null;
	while(current != null) {
	//Comparable를 사용
	if((Comparable<E>)current.data) // 현 데이터 비교

(2) 제거할 노드 앞에 있는 노드의 next가 제거할 노드 뒤의 노드를 가리키게 만든다

(3) 제거할 노드 제거
-만약 노드가 1개만 있는 경우에 제거한다면 removeFirst메소드를 사용

-마지막 노드를 제거하는 경우, removeLast메소드 사용

총정리
<remove메소드>

public E remove(E obj){
	Node<E> current = null; 
	head.previous = null;
	while(current != null) { // Empty element 고려
    // null인 걸 찾아야 제거하고자 하는 요소를 찾았다고 증명됌
		if (((Comparable<E>) obj).compareTo(current.data)==0) {// 1. find 
			if (current==head) // Single element 고려
            // 노드가 1개 or 첫 번째 노드 제거
				return removeFirst(); // Single, Beginning
			if (current==tail) //  End element 고려
            // 마지막 노드 제거
				return removeLast();
			
            currentsize--;
            // 2. remove
			previous.next=current.next; 
			return current.data;
			}
		previous = current;
		current = current.next;
	}
	return null; // 찾지 못하면 null 반환(이 때, 반환하는 자료형이 무엇인지 알 필요가 있다)
}

생각해보기 - remove와 removeFirst 메소드, removeLast 메소드와의 차이점은 무엇인가요?
생각해보기 - 리스트가 비어있는 경우에 remove를 사용하면 어떻게 되나요?

2-9. peek메소드
->용도: 연결리스트 읽기(peekFirst메소드, peekLast메소드)
*먼저, head/tail를 통해 head/tail이 가르치는 곳의 data를 파악하고서 시작하니 알아두기!(with 경계조건)

• peekFirst() - 첫번째 요소인지 확인 후 실행

public E peekFirst(){
	if (head == null)
		return null;
	return head.data;
}

• peekLast() - 마지막 요소인지 가는 방법 2개
  ->임시 포인터로 마지막 요소를 찾는 경우, 시간복잡도는 O(n)
  ->tail포인터로 head처럼 미리 설정했다면, 시간복잡도는 O(1)

public E peekLast(){
	if (tail == null) // tail.next != null
		return null;
	return tail.data;
}

cf)tmp가 임시 포인터라 할 때, while(tmp.next != null)과 while(tmp != null)의 차이점은?
while(tail.next != null)이라면 -> stop at last node => removeLast,peekLast
while(tail != null)이라면 -> pass the last node => contains,remove

2-10. 연결리스트 테스트
참고)ListI 인터페이스
-연결리스트를 제작해 메소드 검사 - 숫자 이용

public class Tester {
	public static void main (String[] args){
		static ListI<Integer> List = new LinkedList <Integer>();
		int n=10;
		// 연결 리스트를 만듭니다.
		for(int i=0; i<n; i++)
			list.addFirst(i); // addLast도 가능
		// 연결 리스트를 제거합니다.
		for(int i=n-1; i>=0; i--)
			int x=list.removeFirst(); // removeLast도 가능
            if(x != i) // x == i인지 확인
        for(int i = 0;i < n;i++)
        	int x = list.removeLast()
}

->이후, 노드의 크기나 currentSize등을 알 필요가 있다

연결리스트 문제풀이 참고
https://coding-factory.tistory.com/552