2-4) 연결 리스트 - peek 메소드, 연결 리스트 테스트, 반복자

 

아래 내용은 부스트코스 <자바로 구현하고 배우는 자료구조> 강의를 들으며 정리한 것입니다.

 

peek 메소드

peek 메소드는 연결 리스트의 특정 하나의 node를 살펴보는 메소드로, 추가하거나 제거하기 위함이 아닌 요소의 내용을 읽기 위함이다. 

 

peekFirst

첫 노드를 읽기 위한 peekFirst 메소드를 위해서는 단순히 head의 data를 살펴보면 된다. 따라서 head.data를 반환해준다.

 

이번 역시 경계 조건 1. 리스트가 비어있을 경우에 head가 null일 때 head.data를 반환하면 NullporintException이 발생하게 되므로 다른 메소드의 경우와 같이 null을 반환해준다.

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

 

peekLast

임시 포인터를 만들어 .next를 반복해 peekLast를 할 수도 있지만, 이렇게 하게 되면 모든 리스트의 요소 수만큼 살펴보아야 하기 때문에 시간 복잡도는 O(n)이 된다.

 

따라서 tail을 활용하면 tail.data 만을 반환하여 시간 복잡도 O(1)로 간단히 처리할 수 있다.

마찬가지로 경계 조건 1. 리스트가 비어있는 상황을 고려하여 tail이 null일 경우 null을 반환하도록 한다.

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

 

연결 리스트 메소트 테스트

public class Tester {
	public static void main (String[] args){
    	static ListI<Integer> List = new LinkedList<Integer>();
        int n = 10;
        // 연결 리스트 생성: head 10부터 점점 작은 값을 가진 리스트
        for (int i=0; i<n; i++)
        	list.addFirst(i);	// or addLast 
        // 연결 리스트 제거
        for (int i=n-1; i>=0; i--)	// i= 9, 8, 7, 6, 5 ... 0
        	int x = list.removeFirst();	
            	if (x != i) …
		// or
        for (int i=0; i<n; i++)
        	int x = list.removeLast();
}

+ 삽입과 제거 후 currentSize를 통해 리스트의 크기도 확인해 본다.

 

 

Iterator & Iterable 인터페이스

 

Iterable과 Iterator 이란? [Gyun's 개발일지]

[Java] Iterable 과 Iterator 이란?

 

Iterator 인터페이스의 메소드 - hasNex(), next(), remove()

 

반복자 (Iterator)

배열에서 각각의 원소를 하나씩 출력하고자 한다면 아래와 같이 코드를 작성할 수 있는데,

int arr[] = {1,2,3,4,5};
for (int i=0; i<arr.length; i++) 
	System.out.println(arr[i]);
}

자바에서 이를 더욱 간편히 작성하기 위한 것으로 Iterable 인터페이스가 있다. Iterable 인터페이스를 구현한 클래스의 경우 같은 기능의 코드를 아래와 같이 향상된 for문(for-each)으로 작성할 수 있다.

int arr[] = {1,2,3,4,5};
for (int x:arr){	//타입 변수: 배열이름
	system.out.println(x);	// x를 출력: 배열의 각 원소를 출력
}

 

 

Iterable 인터페이스

Iterable 인터페이스는 아래와 같은 한 가지의 추상메소드를 가진다. 

public Iterator<E> iterator() {}

이는 'Iterator 인터페이스를 구현하는 하위 클래스를 만들겠다'는 것으로, 그 클래스의 인스턴스로 IteratorHelper의 new 인스턴스를 반환해야 한다.

 

IteratorHelper 클래스 정의하기

public Iterator<E> iterator(){
	return new IteratorHelper();	// new IteratorHelper 반환
}

public class LinkedList<E> implements ListI<E>{	//LinkedList의 내부 클래스 정의
	class IteratorHelper implement Iterator<E>{	
    // Iterator를 구현: public boolean hasNext() , public <E> next() 두 메소드를 가짐
		Node<E> index;	// 연결 리스트를 가리키기 위한 임시 포인터 index
		public IteratorHelper(){	// 생성자
			index=head;		// index가 head를 가리키게 함
		}
		public boolean hasNext(){
			return (index != null);		// index가 null이 아니면 hasNext는 true를 반환
		}
		public E next(){
			if (!hasNext())		// hasNext가 true를 반환하지 않으면(index = null이면) 리스트가 비어있음 
				throw new NoSuchElementException();	// 반환할 것이 없음을 알림
			E val = index.data;		// val에 index의 data 저장 후
			index = index.next;		// next로 이동
			return val;		// val 반환
		}
	}
}

위와 같이 IteratorHelper 클래스를 정의해 Iterator 인터페이스를 구현하는 클래스를 만들면 아래와 같이 간단하게 list의 요소들을 향상된 for문을 사용해 i 변수로 하나씩 꺼낼 수 있다.

for(int i: List) {
	System.out.println(i);
}

 

hasNext

읽어 올 데이터가 있는지 확인하는 메소드로 있으면 true, 없으면 false를 반환한다.(boolean 타입)

예를 들어 현재 가리키고 있는 지점에서 다음 지점이 null이면( == 이동이 불가능하면, 포인터가 null을 가리키고 있을 때) false를 리턴한다.