List 인터페이스의 경우 Collection의 구현체 외 iterator , add , remove , equals 및 hashCode 메소드 의 계약에 추가 규정을 둡니다. 편의를 위해 다른 상속된 메서드에 대한 선언도 여기에 포함됩니다.
오늘 공부할 것은 Iterator에서 ListIterator에 관한 것 입니다.
ListIterator은 아래와 같이 커서(^)와 같은 위치 값을 갖고 있습니다. 이를 next()와 previous()를 통해 움직입니다. hashNext(), hashprevious()를 통해 다음값이 있으면 true, 없다면 false를 반환 받습니다. 또한, add(E), remove(), set(E)를 통해 값을 넣고, 빼고, 바꿀 수 있습니다.
위와 같이보면 위치를 가리키고있는 것을 제외하면 ArrayList, LinkedList와 유사하다고 생각합니다.
시간복잡도는 어떨까요. 먼저, ArrayList와 LinkedList의 시간복잡도 입니다.
| Method | ArrayList | LinkedList | |
| add at last index | add() | O(1) | O(1) |
| add at given index | add(index, value) | O(N) | O(1) |
| remove by index | remove(index) | O(N) | O(1) |
| remove by value | remove(value) | O(N) | O(1) |
| get by index | get(index) | O(1) | O(N) |
| search by value | indexOf(value) | O(N) | O(N) |
추가, 삭제 시 ArrayList보다 LinkedList가 훨씬 빠릅니다. 하지만, LinkedList의 경우 index로 맨앞, 맨뒤가 아닌 중간에 값을 추가, 삭제할 경우에 탐색해야하기 때문에 사실상 O(N)이 걸린다고 봐야합니다.
결론적으로 중간에 데이터를 추가, 삭제하는 작업이 많은 경우 ArrayList, LinkedList 모두 좋은 자료구조가 아니라고 볼 수 있습니다.
index를 이동하며, 데이터를 추가, 삭제해야하는 경우에 적합한 자료구조는 바로 ListIterator입니다.
ListIterator의 경우 index를 한칸씩 이동하는 커서가있고 previous(), next() 메소드를 가지고 있습니다. 또한, List 인터페이스가 LinkedList 구현체로 되어있다면 추가, 삭제에 O(1)의 시간복잡도를 사용합니다. (이 부분이 이해되지 않는다면 ArrayList와 LinkedList의 차이점을 공부해봅시다.)
위의 개념을 완벽하게 이해하고있다면 쉽게 풀 수 있는 문제가 있습니다.
1406번: 에디터
첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수
www.acmicpc.net
참고
listIterator 공식문서
Java Platform SE 8
docs.oracle.com
Iterator 공식문서
Iterator (Java Platform SE 8 )
An iterator over a collection. Iterator takes the place of Enumeration in the Java Collections Framework. Iterators differ from enumerations in two ways: Iterators allow the caller to remove elements from the underlying collection during the iteration with
docs.oracle.com
list 공식문서
List (Java Platform SE 8 )
An ordered collection (also known as a sequence). The user of this interface has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the lis
docs.oracle.com
'JAVA' 카테고리의 다른 글
| [Java 8] Optional (0) | 2022.10.07 |
|---|---|
| [JAVA 8] Stream (0) | 2022.10.06 |
| [JAVA 8] 인터페이스의 변화 (0) | 2022.10.06 |
| [JAVA 8] 함수형 인터페이스와 람다 표현식 (0) | 2022.09.23 |
| SnakeGame (0) | 2022.07.16 |