아래 내용은 부스트코스 <자바로 구현하고 배우는 자료구조> 강의를 들으며 정리한 것입니다.
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 이란?
Collection framework는 뭔가 되게 많고 복잡한 느낌이 들어서 완벽하게 정리가 된 느낌은 아니었다. 가령 Iterator는 어떤 역할인지는 알겠는데 어떤 계층구조를 갖고 있는지 궁금했고, 공부하다보니 It
devlog-wjdrbs96.tistory.com
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를 리턴한다.
'Programming > java 자료구조' 카테고리의 다른 글
| 2.2) 배열로 구현하는 스택과 큐의 시간 복잡도 (0) | 2022.08.05 |
|---|---|
| 2-5) 이중 연결 리스트, 원형 연결 리스트 (0) | 2022.08.03 |
| 2-3) 연결 리스트 - removeFirst, removeLast, remove와 find (0) | 2022.07.30 |
| 2-2) 연결 리스트 - addFirst, addLast (+ 자료구조의 경계 조건) (0) | 2022.07.30 |
| 2-1) 연결 리스트, 노드와 크기 (0) | 2022.07.25 |