연결 리스트 - removeFirst(), removeLast()

removeFirst
: 연결 리스트의 첫 노드를 제거하는 메소드

첫 노드(A)를 제거하고자 한다면, 첫 노드를 가리키는 head가 head.next(B)를 가리키도록 하여 A를 가리키는 포인터가 없게 하고, 그 안에 있는 데이터에 저장된 객체를 제거한다. 
하지만 경계 조건을 고려하지 않으면 에러가 발생하므로 코드를 추가해야 한다.

https://paradiseiswhereiam.tistory.com/124

자료구조의 경계 조건

 

경계 조건1. 자료 구조가 비어 있는 경우
head가 null을 가리킬 경우, head가 null이라면 head.next이라는 것은 없기 때문에 NullPointerException에러가 발생하게 된다.
그러므로, 이 경우에는 아무것도 하지 않고 null을 반환한다.

경계 조건2. 자료 구조에 단 하나의 요소가 들어 있는 경우
head 포인터와 tail 포인터가 가리키는 노드는 같다.
그리고 이 노드는 마지막 노드이기도 하기에, next의 값은 null이다.
head.next가 null이라는 것을 이용하여, 이 head.next의 값을 head에 넣으면
head는 null이 되어 요소가 제거된다.
head 포인터, tail 포인터 모두 null을 가리키게 해야 한다.

tail 포인터는 요소를 추가할 때는 편리하지만 제거할 때는 코드가 복잡해진다는 점이 단점이다.

아무튼 경계 조건2는 코드로 한다면
head.next가 null인가 확인,
currentSize가 1인지 확인 또는
head가 tail과 같은지 확인하면 된다.
이 교수님은 마지막 방법을 선호한다고 한다.
currentSize를 쓰는 건 위에서도 말했지만 currentSize 값을 갱신하는 것을 잊었을 수도 있으니까 신경 쓸 것이 하나 더 느는 방법이다.

 

public E removefirst(){
	// 경계 조건 1
	if (head == null)
		return null;
	E tmp = head.data; // data를 넣어두는 변수 tmp 생성
	// 경계 조건 2
	if (head == tail) // head.next == null, currentSize == 1도 가능
		head = null;
		tail = null;
	// 그 외의 경우
	else
		head = head.next;
	currentSize--;
    return tmp; // 제거한 data가 무엇인지 보여주기 위해 값을 반환
}

 

removeLast
: 연결리스트의 마지막 node를 제거하는 메소드

마지막 노드를 '마지막에서 두 번째 노드'로 옮겨 연결 리스트의 마지막 노드를 제거한다.
단일 연결 리스트이기 때문에 '마지막에서 두 번째 노드'를 찾으려면 head에서부터 시작해야 한다. ( A -> b -> C로는 이동이 가능하지만 C -> b -> A로는 불가능)

currentSize - 1이 되는 지점을 찾는 방식으로 '마지막에서 두 번째 노드'를 찾을 수도 있겠지만, 이 교수님은 currentSize는 값 설정을 깜빡할 수도 있기 때문에 currentSize는 웬만하면 쓰지 않는 것을 추천하는 것 같다.

그래서 '마지막에서 두 번째 노드'를 찾는 방식으로 임시 포인터 current와 previous를 활용할 것이다.
current는 현재 위치를 가리키는 포인터이며, previous는 이전 위치를 가리키는 포인터이다. 
current 포인터가 tail과 같으면 previous 포인터는 '마지막에서 두 번째 노드'를 가리키게 된다.

이번에도 경계 조건에서 에러가 발생하기 때문에 코드를 추가해야 한다.

경계 조건1. 자료 구조가 비어있는 경우
경계 조건2. 자료 구조에 단 하나의 요소가 들어 있는 경우
(removeFirst에서와 똑같이 예외 처리)

public E removeLast(){
	// 경계조건1. 자료 구조가 비어있는 경우
	if (head == null)
		return null;
	// 경계조건2. 자료 구조에 단 하나의 요소가 들어있을 때
	if (head == tail)
		return removeFirst(); // removeFirst()와 방법이 똑같기 때문에 그냥 호출
	// 그 외의 경우
	// 임시 포인터 current, previous를 활용하여 마지막 노드를 제거
	Node<E> current = head, 
	Node<E> previous = null;
	while (current != tail) {
    	//순서 주의
		previous = current;
		current = current.next;
	}
	previous.next = null;
	tail = previous;
	currentSize--;
	return current.data;
}