선형데이터구조, 연결리스트(LinkedList) #5 remove & find 메서드

이전글

https://yonghwankim-dev.tistory.com/181

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

 

개요

이전글에서는 removeFirst, removeLast 메서드 구현을 알아보았습니다. 이번글에서는 연결리스트의 중간 부분을 삭제할 수 있는 remove 메서드와 연결리스트의 노드들을 탐색하여 해당 데이터값이 포함되었는지 알아보는 contains 메서드를 구현하겠습니다.

 

1. remove 메서드

remove 메서드는 removeFirst, removeLast 메서드와는 다르게 노드들을 순차적으로 탐색하여 삭제하고자 하는 데이터값과 동일한 노드를 삭제하는 메서드입니다. 즉, 중간 부분의 노드를 삭제할 수 있습니다. remove 메서드의 수행절차는 다음과 같습니다.

1. Comparable 인터페이스를 사용하여 제거하고 싶은 요소의 위치를 찾습니다.
2. 바로 앞 노드의 next 포인터가 다음 노드를 가리키게 만들어 가운데 노드를 제거합니다. previous, current의 2가지 포인터를 사용하여 각각 바로 앞의 노드와 제거하고자 하는 노드를 가리키게 합니다.

가운데 노드를 제거하는 과정은 아래 그림과 같습니다.

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

1. if(((Comparable<E>)obj).compareTo(current.data)==0){
    	...
        
        2. previous.next = current.next;
    }

 

remove 메서드 구현시 경계조건(Boundary Conditions)

• Empty, 자료구조가 비어있는 경우
• Single Element, 자료구조에 요소가 한개 있는 경우
• Beginning, 자료구조의 추가/제거가 맨 앞에서 수행되는 경우
• End, 자료구조의 추가/제거가 맨 뒤에서 수행되는 경우
• Middle, 자료구조의 추가/제거가 중간에서 수행되는 경우

remove 메서드의 구현은 아래와 같습니다.

public E remove(E obj) {
	Node<E> current=head, previous=null;
		
	// 경계 조건 Empty 포함
	while(current!=null)
	{
		if(((Comparable<E>)obj).compareTo(current.data)==0) // find
		{
			// 경계조건 Single Element, Beginning
			// 노드가 1개 or 첫번째 노드 제거
			if(current==head)
			{
				return removeFirst();
			}
			// 경계조건 End
			// 마지막 노드 제거
			if(current==tail)
			{
				return removeLast();
			}
			previous.next = current.next;	// remove
			currentSize--;
			return current.data;
		}
		// 찾고자 하는 요소가 아닌 경우
		previous = current;
		current = current.next;
	}
	
	return null;
}

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

B
C A

 

2. contains 메서드

contains 메서드는 연결리스트의 앞쪽부터 노드를 탐색하여 찾고자 하는 값이 포함되는지 확인하는 메서드입니다. contains 메서드의 수행과정은 아래와 같습니다.

1. Comparable 인터페이스를 사용하여 앞쪽부터 노드의 데이터값과 동일한 노드를 탐색합니다.
2. 동일한 노드가 있다면 true를 반환하고 맨뒤의 노드까지 탐색하였는데도 불구하고 동일한 데이터가 없다면 false를 반환합니다.

conatins 메서드의 구현은 아래와 같습니다.

public boolean contains(E obj)
{
	Node<E> current=head;
	
	// 경계 조건 Empty 포함
	while(current!=null)
	{
		// 찾고자 하는 요소인 경우
		if(((Comparable<E>)obj).compareTo(current.data)==0)
		{
			return true;
		}
		// 찾고자 하는 요소가 아닌 경우
		current = current.next;
	}
		
	// 요소가 포함되지 않은 경우
	return false;
}

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

true

 

3. remove, removeFirst, removeLast 메서드의 차이

removeFirst 메서드의 핵심적인 로직은 head 포인터의 위치를 head가 가리키는 노드의 다음 노드로 이동시키는 것입니다.

 

removeLast 메서드 같은 경우 previous, current 포인터를 활용하여 연결리스트의 "마지막 노드의 이전 노드"와 마지막 노드로 이동시킨 후 tail 포인터의 위치를 previous가 가리키는 노드로 변경하는 것입니다. 만약 head와 tail이 같은 노드를 바라본다면 연결리스트의 요소가 한개 있는 경우이므로 removeFirst 메서드를 호출하여 제거합니다.

 

remove 메서드도 마찬가지로 previous, current 포인터를 활용합니다. previous 포인터는 찾고자 하는 노드의 이전 노드를 가리키고 current 포인터는 찾고자 하는 노드를 가리킵니다. 만약 current 포인터가 head를 가리킨다면 찾고자 하는 노드가 맨 앞에 있는 것이므로 removeFirst 메서드를 호출하여 제거합니다. current 포인터가 tail을 가리킨다면 찾고자 하는 노드가 맨 뒤에 있는 것이므로 removeLast 메서드를 호출하여 제거하고 tail 포인터를 갱신합니다. 그외의 가운데 부분에 제거하고자 하는 노드가 존재하는 경우 이전 노드의 next 포인터(previous.next)를 현재 노드의 next(current.next)가 가리키는 노드를 가리키도록 합니다.

 

4. 리스트가 비어있는 경우 remove 메서드를 사용하는 경우

리스트가 비어있는 경우는 경계 조건에서 Empty(자료구조가 비어있는 경우)에 해당되므로 remove 메서드의 내용 중 반복문을 들어가지 못하고 null을 반환하게 됩니다.

public E remove(E obj) {
	Node<E> current=head, previous=null;
	
	// 경계 조건 Empty 포함
	while(current!=null)
	{
		...
	}
	
	return null;	
}

 

References

[부스트코스] 자바로 구현하고 배우는 자료구조