선형데이터구조, 연결리스트(LinkedList) #4 removeFirst / removeLast 메서드

이전글

https://yonghwankim-dev.tistory.com/107?category=974118 

선형데이터구조, 연결리스트(LinkedList) #3 addFirst/addLast 메서드

 

개요

이전글에서는 addFirst, addLast 메서드를 구현하였습니다. 이번글에서는 removeFirst, removeLast 메서드를 구한하도록 하겠습니다.

 

1. removeFirst 메서드

removeFirst 메서드는 연결리스트의 제일 앞쪽에 위치한 노드를 제거하는 메서드입니다. removeFirst 메서드의 수행 과정은 아래 그림과 같습니다.

위의 과정을 코드로 표현하면 아래와 같습니다.

1. head = head.next;

removeFirst 메서드를 구현하기 전에 경계조건(Boundary Conditions)들을 고려해야 합니다. 경계조건 5개는 다음과 같습니다.

1. Empty : 자료구조가 비어있는 경우
2. Single Element : 자료구조에 데이터가 하나만 있는 경우
3. Beginning : 자료구조의 첫번째 요소를 추가하거나 제거하려고 하는 경우
4. End : 자료구조의 마지막 요소를 추가하거나 제거하려고 하는 경우
5. Middle : 자료구조의 중간 부분을 처리하는 경우

1. removeFirst 메서드 수행 중 자료구조가 비어있는 경우

자료구조가 비어있다는 의미는 head가 null을 가리키고 있다는 의미이므로 null을 반환합니다.

if(head==null)
{
	return null;
}

2. removeFirst 메서드 수행 중 삭제할 노드가 하나만 있는 경우

삭제할 노드가 하나만 존재하는 경우 head와 tail은 같은 노드를 바라보고 있으므로 head와 tail은 null을 가리키도록 합니다.

if(head==tail)
{
	head = tail = null;
}

그외의 경계조건은 중복되거나 해당사항이 없으므로 생략하겠습니다.

 

위와 같이 경계 조건을 고려한 removeFirst 메서드의 내용은 아래와 같습니다.

public E removeFirst() {
	// 경계조건 1. Empty, 자료구조가 비어있는 경우
	if(head==null)
	{
		return null;
	}
		
	E delData = head.data;
		
	// 경계조건 2. Single Element, 삭제할 노드가 단 하나남은 노드인 경우 
	// head, tail은 null을 가리키도록 함
	if(head==tail)
	{
		head = tail = null;
	}
	else
	{
		head = head.next;
	}
		
	currentSize--;
		
	return delData;
}

	@Test
	void removeFirstTest() {
		LinkedList<String> list = new LinkedList<String>();
		
		list.addFirst("A");
		list.addFirst("B");
		list.addFirst("C");
		
		System.out.println(list.removeFirst());	// Expected Output : C
	}

C

 

2. removeLast 메서드

removeLast 메서드는 연결리스트의 제일 뒤쪽의 노드를 제거하는 메서드입니다. 연결리스트의 제일 뒤쪽에 있는 노드를 제거하기 위해서는 제일 마지막 노드와 마지막 노드의 이전 노드를 알아야 합니다. 마지막 노드와 마지막 노드의 이전 노드를 파악하는 제일 간단한 방법은 current 포인터와 previous 포인터를 활용하는 방법이 있습니다. 마지막 노드를 찾은 current 포인터와 마지막 노드의 이전 노드인 previous 포인터는 아래 그림과 같을 것입니다.

current와 previous 포인터가 마지막 노드와 마지막 노드의 이전 노드를 가리키는 방법을 코드로 표현하면 아래와 같습니다.

Node<E> current = head;
Node<E> previous = null;
		
while(current!=tail)
{
	previous = current;
	current = current.next;		 
}

 

removeLast 메서드의 수행 과정은 아래 그림과 같습니다.

위 그림의 수행과정을 코드로 표현하면 아래와 같습니다.

1. previous.next = null;
2. tail = previous;

 

removeLast 메서드에서도 경계 조건을 고려해야 합니다.

1. Empty : 자료구조가 비어있는 경우

head가 null을 가리키고 있으므로 null을 반환합니다.

 

2. Single Element, Beginning : 자료구조에서 노드가 한개밖에 없는 경우

removeFirst 메서드의 수행과정과 동일하므로 removeFirst 메서드를 호출합니다.

 

3. End : 자료구조의 마지막 요소를 추가하거나 제거하려고 하는 경우

위에서 소개된 removeLast 메서드의 수행과정을 수행합니다.

 

4. Middle : 자료구조의 중간 요소를 추가하거나 제거하려고 하는 경우

해당사항 없음

 

위의 경계 조건을 고려하여 완성된 removeLast 메서드의 내용은 아래와 같습니다.

public E removeLast() {
	// 경계조건 1. Empty, 자료구조가 비어있는 경우
	if(head==null)
	{
		return null;
	}
		
	// 경계조건 2. Single Element, 자료구조에서 요소가 하나 있는 경우
	if(head==tail)
	{
		return removeFirst();
	}
		
	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;
		
}

	@Test
	void removeLastTest() {
		LinkedList<String> list = new LinkedList<String>();
		
		list.addFirst("A");
		list.addFirst("B");
		list.addFirst("C");
		
		System.out.println(list.removeLast());	// Expected Output : A
	}

A

 

 

References

source code : https://github.com/yonghwankim-dev/DataStruct/tree/main/LinkedList/Implement
[부스트코스] 자바로 구현하고 배우는 자료구조