2-3) 연결 리스트 - removeFirst, removeLast, remove와 find

 

아래 내용은 부스트코스 <자바로 구현하고 배우는 자료구조> 강의를 들으며 정리한 것입니다.

 

removeFirst 메소드 

연결 리스트의 첫 번째 node를 제거하기 위한 removeFirst 메소드를 만든다고 생각해보자.

첫 노드를 제거하기 위해서는, 그 노드를 가리키는 포인터가 없게해서 가비지 컬렉션이 일어나도록 하고 data에 저장된 객체를 반환해야 한다. 그러므로 우선 head 포인터가 두 번째 노드를 가리키게끔 만들기 위해 head = head.next; 를 해볼 수 있다.

head = head.next;

이 때 앞에서 살펴본 자료구조에서 고려해야 하는 경계 조건을 만족하는지를 따져 보면,

 

경계 조건 1. 자료구조가 비어있는 경우(head = null; 일 경우)

addLast에서 tmp가 null일 경우와 마찬가지로 head가 head.next를 가리키게 하면 NullPointerException 런타임 에러가 발생한다. head가 null을 가리키고 있기 때문이다. 자바 문서에는 리스트가 비어있으면 null을 반환한다고 적혀있으므로 이 상황에서는 null을 반환하면 된다. 

public E removefirst(){
	// 경계 조건 1 : empty list인 경우 null을 return
	if (head == null)
		return null;

 

이제 자료구조가 비어있지 않은 경우, remove하려는 첫 노드의 data 객체를 반환해야한다. 

첫 번째 노드의 data 객체를 기억하기 위해 임시 변수를 만들어 이 data 값을 저장한다.

public E removefirst(){
	// 경계 조건 1 : empty list인 경우 null을 return
	if (head == null)
		return null;
		E tmp = head.data; 	// 임시 변수에 첫 노드의 data 저장

 

경계 조건 2. 자료 구조에 하나의 요소만이 들어있는 경우

노드가 하나만 있을 경우 head=head.next를 하면 head는 이제 null을 가리키게 된다. 또한 이 경우에 tail 포인터도 같은 노드를 가리키고 있기 때문에, tail 포인터 역시 제거하려는 이 노드를 가리키지 않고 null을 가리키게 바꾸어줘야 한다. 

 

* 리스트에 한 개의 노드만이 있다는 것을 알기 위해서는 다음을 확인하면 된다.

1. head.next == null
2. currentSize == 1
3. head == tail

 

removeFirst

public E removefirst(){
	// 경계 조건 1 : empty list인 경우 null을 return
	if (head == null)
		return null;
	E tmp = head.data;	// 임시 변수에 첫 노드의 data 저장
	// 경계 조건 2 : 하나의 요소만 있을 경우
	if (head == tail) // head.next == null, currentSize == 1도 가능
		head = tail = null;
	// 그 외의 경우 (요소가 여러 개)
	else
		head = head.next;
	currentSize--;
    return tmp;	// 제거한 data의 값을 반환
}

 

removeLast 메소드

연결 리스트의 마지막 node를 제거하기 위해서는 tail을 마지막에서 두 번째 노드로 옮긴다. 그런데 이 노드(마지막에서 두 번째 노드)를 찾기 위해서는 단일 연결 리스트이기 때문에 리스트 맨 앞에서부터 시작해야 한다. 그러나 이 방법은 노드가 굉장히 많을 경우 너무 힘들고, currentSize를 활용하여 현재의 위치가 currentSize - 1인지를 확인할 수도 있으나 보다 더 효율적인 방법은 임시 포인터 두 개(current, previous)를 만들어 활용하는 것이다.

 

current는 현재 위치를 가리키는 포인터이며 previous는 현재의 이전 위치를 가리키는 포인터이다.

처음에 current는 head를, previous는 null을 가리키는 것으로 시작하여 ①previous → current , ②current → current.next 를 리스트 끝까지 반복한다. (current가 마지막 노드를 가리키고 previous가 그 전 노드를 가리킬 때까지) 

그 후 previous.next (마지막에서 두 번째 노드의 next)를 null로 설정해준다.

 

리스트 끝으로 온 것을 확인하는 방법

1. current == tail
2. current.next == null

 

경계 조건 살펴보기

 

경계 조건 1. 자료구조가 비어있는 경우

마찬가지로 NullPointerException 런타임 에러가 발생할 것이므로 removeFirst와 같은 방법으로 null을 반환한다.

 

경계 조건 2. 자료 구조에 하나의 요소만이 들어있는 경우

어차피 요소가 한 개이므로 removeFirst와 removeLast 는 같다. 같은 코드를 사용하면 된다. (removeFirst를 반환한다)

 

3. 자료구조의 시작에 삽입 / 삭제할 경우 :  맨 앞에서 removeLast를 한다는 것 = 요소가 하나만 있다는 것 = case 2

4. 자료구조의 끝에 삽입 / 삭제할 경우  :  removeLast의 본질 기능

5. 자료구조의 중간 부분을 처리할 경우 :  removeLast는 리스트 중간에서 일어나지 않으므로 고려할 필요 없음

 

 

removeLast

public E removeLast(){
	// 경계 조건 1. empty list인 경우: head가 null이면 null을 반환한다 
	if (head == null)
		return null;
	// 경계 조건 2. 하나의 요소만 있을 경우
	if (head == tail)
		return removeFirst();
	// 그 외의 경우
	// 임시 포인터 current, previous를 활용하여 마지막 노드를 제거하기
	Node<E> current = head, 
	Node<E> previous = null;
	while (current != tail) {	// current가 tail과 같지 않을 동안...
		previous = current;		// !!순서 유의!!
		current = current.next;
	}
	previous.next = null;
	tail = previous;
	currentSize--;
	return current.data;	//제거한 current 노드의 data 반환
}

 

remove 메소드

 

1. Comparable 인터페이스를 사용하여 제거하고 싶은 요소의 위치를 찾는다.

2. 제거할 노드의 앞 노드의 next 포인터가, 제거할 노드의 다음 노드를 가리키게 만들어 가운데 노드를 제거한다.
previous, current의 2가지 포인터를 사용하여 각각 바로 앞의 노드와 제거하고자 하는 노드를 가리키게 한다.

 

 

경계조건 살펴보기

1. 리스트가 비어있는 경우: 찾을 노드가 없으므로 null을 반환 ( current = head == null이므로 while문 skip하고 null 반환)

2. 노드가 한 개만 있는 경우:  removeLast 경우와 같이 removeFirst 메소드를 그대로 사용

3. 자료구조의 시작에서 제거할 경우: current가 head인지 or previous가 null인지 확인하여 removeFirst

4. 자료구조의 끝에서 제거할 경우: removeLast

 

remove

public E remove(E obj){
	Node<E> current = head, previous = null;
	while(current != null) {	// 마지막 요소까지 확인하기 위해 current가 null이 될 때까지 check
		if (((Comparable<E>) obj).compareTo(current.data)==0) { // 1. find
			if (current==head) // 노드가 1개 or 첫 번째 노드 제거
				return removeFirst();
			if (current==tail) // 마지막 노드 제거
				return removeLast();
			currentsize--;
			previous.next=current.next; // 2. remove : current를 가리키던 포인터 제거
			return current.data;	// 유일하게 제거할 노드를 가리키는 current까지 반환
            // : 메소드의 객체가 아닌 리스트에 있었던 객체를 반환해 리스트 객체의 정보를 알 수 있음 
			}
		previous = current;
		current = current.next;	// 제거할 노드가 아니면 다음 노드로 넘어감
	}
	return null;	// 제거할 노드 찾지 못하고 모든 요소 비교 끝
}

유의할 것

1. removeFirst, removeLast가 반환하는 객체와 remove 메소드가 반환하는 객체와 같은 타입인지 확인해야 한다.

2. current가 tail인지 확인해야 할까 생각해보자 ( if (current == tail) 코드가 필요할까)

 :  마지막 노드를 삭제할 때 remove 메소드를 사용할 경우, tail의 위치에 대한 조정이 이루어지지 않아 문제 발생 가능(?)

 

contains (find) 메소드

public boolean contains(E obj){
	Node<E> current = head;
	while(current != null) {
		if (((Comparable<E>) obj).compareTo(current.data)==0) // Comparable 인터페이스
			return true;	// 찾고자 하는 것이 맞으면 true 반환
		current = current.next;
	}
	return false;	// 찾고자 하는 것이 없으면 false 반환
}