removeFirst
연결리스트의 첫 노드를 제거하는 방법에 대해서 알아보겠습니다.
간단히 생각하면, Head는 첫번째 노드를 가리키고 있으니 head= head.next를 통해 다음번 노드를 가르키게하고 첫번째 노드는 가비지 컬랙션 대상이되므로 제거됩니다.
하지만 경계조건을 고려해보아야합니다.
자료구조가 비어있는경우
head가 Null인 경우에는 어떻게 할까요?
이 때, head가 head.next를 가리키게 하면 NullPointerException 에러가 발생하게 됩니다.
그래서 이 상황에서는 아무것도 하지 않고 null을 반환하면 됩니다.
자료구조에 단 하나의 요소가 들어가있을때
일단 요소가 한개만 있는지 어떻게 알 수 있을까요?
head.next가 null이면 요소가 한 개인 사실을 알 수 있습니다.
또한 currentSize가 1인지 확인하는 방법도 있습니다.
마지막으론 head와 tail이 같은지 확인하면 됩니다.
head 포인터, tail 포인터 모두 null을 가리키게 해야 합니다.
public E removeFirst(){
//경계조건 1
if(head == null)
return null;
E temp = head.data; // 반환하고 싶은 요소가 맨 앞에있을 때
//경계조건 2
if (head == tail)
head = null;
tail = null;
else
head = head.next;
currentSize--;
}removeLast
마지막 노드를 제거하는 방법입니다.
마지막노드를 마지막에서 두번째 노드로 옮긴 후 마지막 노드를 제거하면 됩니다.
그러나 단일 연결리스트에서 뒤에서 앞으로 찾아갈수는 없습니다.
head에서 시작해 앞에서부터 찾아가야합니다.
그러면 addLast처럼 역시 임시포인터를 사용하도록 하겠습니다.
head를 가르키는 current와 null을 가르키는 previous라는 임시포인터가 있습니다.
current를 current.next로 설정해주고 previous는 current로 설정해줍니다.
이렇게 마지막 노드까지 반복하면 current와 tail이 같아질 것입니다.
혹은 current.next가 null인 경우에도 마지막 노드라는 것을 알 수 있습니다.
이때 previous.next를 null설정해주변 마지막 요소를 제거할 수 있습니다.
하지만 또 고려해볼 경계조건이 있습니다.
리스트가 비어있을때, 요소가 한개만 있을때
removeFirst와 똑같이 처리하면 됩니다. 즉 null을 반환하고 종료하면 됩니다.
public E removeLast(){
// 자료 구조가 비어있는 경우
if (head == null)
return null;
// 자료 구조에 단 하나의 요소가 들어있을 때
if (head == tail)
return 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;
}