선형데이터구조, 연결리스트(LinkedList) #6 peekFirst & peekLast 메서드

이전글

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

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

 

개요

이전글에서는 remove 메서드와 contains 메서드를 구현하였습니다. 이번글에서는 peekFirst, peekLast 메서드를 구현하도록 하겠습니다.

 

1. peekFirst 메서드

peekFirst 메서드는 연결리스트의 제일 앞쪽에 위치한 노드의 데이터값을 반환하는 메서드입니다. 대표적인 특징은 remove 메서드와 같이 노드를 제거하지 않고 요소의 값을 확인하기만 합니다.

 

peekFirst 메서드 구현시 주의해야 할 경계 조건은 자료구조의 데이터가 비어있는 경우입니다. 연결리스트에서 이는 head가 null인 경우를 의미합니다.

 

peekFirst 메서드의 구현 내용은 아래와 같습니다.

public E peekFirst() {
	if(head==null)
	{
		return null;
	}
	return head.data;
}

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

C

 

2. peekLast 메서드

peekLast 메서드는 연결리스트의 제일 뒷 부분의 요소의 데이터값을 반환하는 메서드입니다. 이 메서드도 마찬가지로 제거와 같은 연산을 하지 않고 확인만 하는 메서드입니다. 

 

peekLast 메서드를 직관적으로 구현하고 다음과 같습니다.

public E peekLast() {
	Node<E> current = head;
	while(current.next!=null)
	{
		current = current.next;
	}
	return current.data;
}

위 코드는 연결리스트의 제일 앞 노드부터 순회하여 제일 뒷 부분의 노드까지 이동한 후 제일 마지막 노드의 데이터값을 반환하는 코드입니다. 하지만 위 방식의 문제점은 제일 뒷부분의 노드까지 이동하기 위해서 O(n)의 시간복잡도를 소요합니다. 따라서 이 문제를 해결하기 위해서 아래와 같이 개선합니다.

public E peekLast() {
	if(tail==null)
	{
		return null;
	}
	return tail.data;
}

위와 같이 tail 포인터를 활용하면 상수적인 시간으로 제일 뒷부분의 데이터값을 확인할 수 있습니다.

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

A

 

3. while(current.next != null) & while(current != null) 구문의 차이점

while(current.next != null)
{
	...
    current = current.next;
}

위 구문은 current 포인터가 연결리스트의 마지막 노드에서 정지합니다. 그림으로 표현하면 아래와 같습니다.

위와 같은 구문은 peekLast, removeLast와 같은 메서드에서 사용됩니다.

 

while(current != null)
{
	...
    current = current.next;
}

위와 같은 구문은 current 포인터가 null을 가리킵니다. 즉, 연결리스트의 마지막 노드를 지나칩니다. 그림으로 표현하면 아래와 같습니다.

위와 같은 구문은 contains, remove와 같은 메서드에서 사용됩니다.

 

References

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