[java] 코드를 통해 보는 ListIterator (LinkedList, Iterator)
java를 사용할 때 컬렉션 중에 Iterator가 사용 가능한 자료구조가 몇 개 있다.
구현하려는 로직이 시간복잡도 측면에서 인덱스보다 Iterator를 사용하는 것이 유리했기 때문에 겸사겸사 이를 정리해보려고 한다.
목차
1. Iterator란?
2. Iterator가 더욱 유리한 로직에 대해서 (시간복잡도 관점에서)
3. Iterator의 내부 동작
1. Iterator란?
Java Iterator
An Iterator is an object that can be used to loop through collections, like ArrayList and HashSet. It is called an "iterator" because "iterating" is the technical term for looping.
To use an Iterator, you must import it from the java.util package.
출처: https://www.w3schools.com/java/java_iterator.asp
간단히 말해서 Iterator란 java의 ArrayList나 HashSet과 같은 컬렉션에서 반복을 할 수 있도록 하는 객체이다.
나에게 Iterator란 컬렉션에서 반복을 사용할 때 보다 편리하게 사용할 수 있도록 구현된 도구이다. 사용 가능한 컬렉션에서는 AbstractIterator라는 추상 클래스를 상속해 이미 구현해놨다. (확인하고 싶다면 IDE 켜서 shift 2번 연속해서 누르고 AbstractIterator 검색하면 된다.)
컬렉션에서 반복을 하려면 index를 이용한 for문이나 향상된 for문을 사용할 수도 있지만, Iterator를 사용할 수도 있다. 결론적으로, 구현할 로직에 유용한 방법을 사용하면 된다는 것이다.
2. Iterator가 유리한 로직?
ArrayList와 LinkedList, Iterator를 예시로 설명해보겠다.
ArrayList는 배열 기반, LinkedList는 이름 그대로 데이터를 연결시켜 만든 자료구조이다.
-
get
get의 경우 배열 기반인 ArrayList는 index에 맞는 데이터를 바로 접근할 수 있지만, LinkedList는 해당 자료구조의 시작 노드부터 index에 해당하는 Node까지 순차적으로 접근해야 하기 때문에 index 만큼의 시간복잡도가 소요된다. -
삽입/삭제
삽입, 삭제의 경우 ArrayList는 배열 기반이기 때문에 추가, 삭제 시에 배열을 뒤로 밀거나 앞으로 땡겨오는 작업이 필요하다. 이에 따라 시간복잡도가 매우 높은 편이다. LinkedList는 순차적으로 접근하기는 하나, 연결을 추가하거나 연결을 끊는 작업(시간복잡도 O(1))이 수행되기 때문에 ArrayList 보다는 효율적이다.
관련해서 참고하기 좋은 포스팅: http://changpd.blogspot.com/2014/08/arraylist-linkedlist-java.html
😯:만약 index를 유지하면서 삽입, 삭제가 빈번하다면 어떤 것이 유리할까?
=> Iterator를 이용한 LinkedList를 사용하는 것이 유리하다. LinkedList 삽입/삭제에 유리한 구조를 갖고 있고 Iterator는 인덱스가 아닌 객체를 가르키기 때문에 index의 흐름을 유지한 채 삽입/삭제를 효율적으로 수행할 수 있다.
추가적인 설명은 3. Iterator 내부 동작을 설명하면서 추가적으로 설명하도록 하겠다.
3. Iterator의 내부 동작
*LinkedList, ListIterator 기준
3-1. ListIterator의 생성
- ListItr 인스턴스 생성 메소드 (LinkedList.java)
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}ListIterator 생성할 때 사용하는 메소드
1. 들어온 index가 타당한지 확인하고
2. ListIterator 반환
index 없이 listIterator() 호출하는 경우에는,
public ListIterator<E> listIterator() {
return listIterator(0);
}자동적으로 index=0으로 들어가서 생성된다. (AbstractList.java)
- ListIterator 구현 ListItr 클래스 (LinkedList.java)
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;
ListItr(int index) {
// assert isPositionIndex(index);
next = (index == size) ? null : node(index);
nextIndex = index;
} ListItr 클래스는
- lastReturned 객체
- next 객체
- nextIndex 인덱스
- expectedModCount 카운트
를 멤버로 가진다.
- lastReturned : 마지막으로 return한 객체
- next : iterator가 다음으로 반환할 객체
- nextIndex : next 객체의 index
- expectedModCount : 현재 Iterator에서 연산한 횟수(값이 변경되는 연산에 한함. add나 remove 같은 거)
👉🏻 expectedModCount란?
만약 멀티스레딩 상황에서 하나의 list에 대해 여러 iterator를 생성했거나, iterator가 아닌 list에 접근해서 연산을 동시에 한다면 -> 로직적으로 코드가 꼬이게 됨. -> 이걸 방지하기 위해서 List는 modCount 변수를 보유하고 있음. expectedModCount와 modCount를 비교하고 다르면 문제 있다고 판단해서 exception 발생시킴.
생성자를 통해 next, nextIndex를 초기화한다. 만일 index가 0으로 되어 생성한다면, next는 0번째 데이터의 주소와 nextIndex는 0을 갖게 된다.
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}해당 로직을 통하여 next는 index에 해당하는 객체의 주소 값을 갖게 된다.
여기서 shift 연산은 단순히 size/2를 해서 현재 index가 중간값을 기준으로 앞쪽에 있으면 앞에서부터 접근, 뒤쪽에 있으면 뒤에서부터 접근하도록 한 것이다.
shift 연산은 /2를 하는 산술연산보다 매우 빠르기 때문에 현재 index에 순차적으로 접근하는 o(index) 시간 복잡도를 최대한 줄이는 것 같다.
3-2. next
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}- checkForModification은 위에서도 언급했던 expectedModCount와 리스트의 modCount를 비교하는 로직
- 이후 hasNext를()를 통해 next가 존재하는지 확인
public boolean hasNext() {
return nextIndex < size;
}- lastReturned = 현재 next 객체 주소. 우리가 현재 반환해야 하는 건 next의 값이기 때문에 lastReturned에 값을 넣어주고 반환하는 느낌이다. next는 또 다음을 가르켜야 되기 때문에 temp 변수같은 느낌으로 쓰는 듯함.
- next = next.next. 현재 next의 다음 객체로 next 변경.
- nextIndex++ 현재 next의 다음 객체 index로 변경(하나 증가하면 됨)
- lastReturned.item 반환함으로써, next() 호출 시점의 next 객체의 데이터를 반환할 수 있다.
3-3. previous
public E previous() {
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();
lastReturned = next = (next == null) ? last : next.prev;
nextIndex--;
return lastReturned.item;
}- lastReturned = next = (next == null) ? last : next.prev;
next가 null이면 next()를 통하여 마지막 데이터를 lastReturned로 반환하고 next=null이 된 것이기 때문에 이때의 previous는 last다.
next가 null이 아니면, 현재 next의 prev를 previous로 반환한다. - nextIndex--; next의 이전 객체 인덱스로 nextIndex 변경.
- lastReturned.item을 반환함으로써, next의 이전 객체를 반환할 수 있다.
결론
로직을 알아보기 좋은 next와 previous에 대해 코드로 이해해보았다. 두 가지만 접근해도 ListIterator의 변수 이용과 흐름을 알 수 있었다.
ListIterator가 어렵게 느껴지는 이유는 next 객체에 있다고 생각한다. 다음을 가르키는 next 객체가 Iterator에서 매우 중요하고, 순차 next가 아닌 previous와 add, remove를 연속하면 next가 무엇을 가르키는지 매우 헷갈린다.
import java.util.*;
public class Main{
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.addLast(0);
list.addLast(1);
ListIterator<Integer> it = list.listIterator();
ArrayList<Integer> ans=new ArrayList<>();
ans.add(it.next());
ans.add(it.previous());
ans.add(it.next());
ans.add(it.next());
System.out.print(ans);
}
}간단한 이 코드에서도 정답은 [0, 0, 0, 1] 로 나온다.
제일 헷갈리는 부분은 previous를 하고 next를 했을 때 0이 나온다는 점이다. 내부 동작을 보면 이게 당연한 것이지만 논리적으로는 previous를 통해 0을 이미 가르켰고 이후, next를 했는데도 또 0이 나온다고? 하면서 헷갈린다.
이에 대해 조심하면서 로직을 구현하면 좋을 것 같다. 3학년 때 수강한 객체지향 수업에서 iterator 패턴을 공부하며 iterator를 직접 구현했었는데 역시 라이브러리 코드의 깔끔함 수준이 미친 거 같다 🙇🏻♀️
