[Java] LinkedList의 ListIterator 사용하기

Iterator는 LinkedList 클래스에 있는 요소를 순차접근하고 싶을 때 효율적으로 접근할 수 있도록 해준다.
만약 Iterator가 없다면, n개의 요소에 순차적으로 접근하기 위해 매번 LinkedList.get(k)을 호출해야 하는데, 그때마다 k번 인덱스를 찾아가느라 결국 O(n^2)의 시간이 걸린다.
Iterator를 사용한다면 최근에 접근했던 위치를 기억하기 때문에 n개의 요소를 순차적으로 접근할 때의 시간복잡도는 O(n)가 된다.

그런데 LinkedList를 사용하다가 자동완성에 listIterator()를 발견하게 되었다. MutableIterator과 MutableListIterator의 차이는 뭔가 싶어서 알아보았는데, 다음과 같은 차이점이 있었다.

MutableIterator는 단방향으로 순차접근을 할 때와 요소를 삭제할 때 사용하고,
MutableListIterator는 양방향으로 순차접근할 수 있고, 요소를 삭제뿐만 아니라 삽입, 수정까지 할 수 있다.

단방향으로만 순차접근하는 게 아니라면 MutableListIterator를 사용하는 경우가 더 많을 것 같아서 이번 포스팅에서는 LinkedList에서의 MutableListIterator의 사용법을 정리해보려고 한다~!😉

📍 MutableListIterator 가져오기

val linkedList = LikedList<Int>()

val listIterator: MutableListIterator<Int> = linkedList.listIterator()

📍 다음 요소 가져오기 (next())

리스트의 다음 요소를 반환하고, cursor의 위치를 다음으로 이동시킨다.
다음 요소로 이동할 땐 다음 요소가 있는지 hasNext()로 확인 후 이동하는 걸 잊지 말자!

if (listIterator.hasNext()) listIterator.next()

📍 이전 요소 가져오기 (previous())

리스트의 이전 요소를 반환하고, cursor의 위치는 이전으로 이동시킨다.
이 역시 hasPrevious()로 이전 요소가 존재하는 지 확인하자!

if (listIterator.hasPrevious()) listIterator.previous()

📍 요소 추가하기 (add(k))

리스트에 현재 cursor의 위치에 요소k를 추가한다.

linkedList.add(4)
linkedList.add(5)
linkedList.add(6) // [4, 5, 6]

val listIterator = linkedList.listIterator()
listIterator.add(1) // [1, 4, 5, 6]
listIterator.next()
listIterator.add(2) // [1, 4, 2, 5, 6]
listIterator.next()
listIterator.next()
listIterator.add(3) // [1, 4, 2, 5, 6, 3]

📍 요소 삭제하기 (remove())

가장 마지막으로 next()나 previous()로 반환된 요소를 리스트에서 삭제한다.
즉, 이 메서드를 호출하기 전에 next()나 previous()를 호출하지 않았다면 IllegalStateException이 발생한다.

linkedList.add(1)
linkedList.add(2)
linkedList.add(3) // [1, 2, 3]

val listIterator = linkedList.listIterator()
listIterator.next() // 1 반환
listIterator.next() // 2 반환

listIterator.remove() // [1, 3] : 요소 2를 삭제

📍 요소 수정하기 (set(k))

가장 마지막으로 next()나 previous()로 반환된 요소를 k로 수정한다.
역시 이 메서드를 호출하기 전에 next()나 previous()를 호출하지 않았다면 IllegalStateException이 발생한다.
또한 이전에 remove()된 요소에 이 메서드를 사용해도 IllegalStateException이 발생한다.

linkedList.add(1)
linkedList.add(4)
linkedList.add(3) // [1, 4, 3]

val listIterator = linkedList.listIterator()
listIterator.next() // 1 반환
listIterator.next() // 4 반환

listIterator.set(2) // [1, 2, 3]