📌 List<E>
List 인터페이스는 배열과 같이 객체를 일렬로 늘어놓은 구조를 가지고 있다.
객체를 인덱스로 관리하기 때문에 객체를 저장하면 자동으로 인덱스가 부여되고, 인덱스로 객체를 검색, 추가, 삭제할 수 있는 등의 여러 기능을 제공한다. List 인터페이스를 구현한 클래스로는 ArrayList, Vector, LinkedList, Stack 등이 있다. 이 중에서 ArrayList와 LinkedList가 가장 많이 사용된다.
List 인터페이스에서 공통적으로 사용 가능한 메서드는 다음과 같다. 앞서 살펴본 컬렉션 인터페이스의 메서드 또한 상속을 받아 사용이 가능하다.
✔️ List의 메서드
| 기능 | 리턴 타입 | 메서드 | 설명 |
| 객체 추가 | void | add(int index, Object element) | 주어진 인덱스에 객체를 추가 |
| boolean | addAll(int index, Collection c) | 주어진 인덱스에 컬렉션을 추가 | |
| Object | set(int index, Object element) | 주어진 위치에 객체를 저장 | |
| 객체 검색 | Object | get(int index) | 주어진 인덱스에 저장된 객체를 반환 |
| int | indexOf(Object o) lastIndexOf(Object o) |
순방향 / 역방향으로 탐색하여 주어진 객체의 위치를 반환 | |
| ListIterator | listIterator() istIterator(int index) |
List의 객체를 탐색할 수 있는ListIterator 반환 주어진 index부터 탐색할 수 있는 ListIterator 반환 |
|
| List | subList(int fromIndex, int toIndex) | fromIndex부터 toIndex에 있는 객체를 반환 | |
| 객체 삭제 | Object | remove(int index) | 주어진 인덱스에 저장된 객체를 삭제하고 삭제된 객체를 반환 |
| boolean | remove(Object o) | 주어진 객체를 삭제 | |
| 객체 정렬 | void | sort(Comparator c) | 주어진 비교자(comparator)로 List를 정렬 |
📌 ArrayList
List 인터페이스를 구현한 클래스로, 컬렉션 프레임워크에서 가장 많이 사용된다.
기능적으로는 Vector와 동일하지만 기존의 Vector를 개선한 것이므로, Vector보다는 주로 ArrayList를 많이 사용한다.
ArrayList에 객체를 추가하면 객체가 인덱스로 관리된다는 점에서 배열과 유사하다. 그러나 배열은 생성할 때 크기가 고정되며, 크기를 변경할 수 없다. ArrayList는 이러한 배열의 단점을 보완하여, 저장 용량을 초과하면 자동으로 저장용량을 늘리는 기능을 가지고 있다.
또한, 리스트 계열 자료구조의 특성을 이어받아 데이터가 연속적으로 존재된다. 즉, 데이터의 순서를 유지한다.
ArrayList에 객체를 추가하면 인덱스 0부터 차례대로 저장된다. 그리고 특정 인덱스의 객체를 제거하면, 바로 뒤 인덱스부터 마지막 인덱스까지 모두 앞으로 1씩 당겨진다.
그래서 빈번한 객체 삭제와 삽입이 일어나는 곳에서는 ArrayList보다는 LinkedList를 사용하는 것이 좋다.
✔️ ArrayList의 메서드
| 타입 | 메서드명 | 설명 |
| boolean | add(E e) | 지정된 요소를 이 목록의 끝에 추가한다. |
| void | add(int index, E element) | 이 목록의 지정된 위치에 지정된 요소를 삽입한다. |
| boolean | addAll(Collection<? extends E> c) | 지정된 컬렉션의 Iterator에서 반환된 순서대로 지정된 컬렉션의 모든 요소를 이 목록의 끝에 추가한다. |
| boolean | addAll(int index, Collection<? extends E> c) | 지정된 위치에서 시작하여 지정된 컬렉션의 모든 요소를 이 목록에 삽입한다. |
| void | clear() | 이 목록에서 모든 요소를 제거한다. |
| Object | clone() | 이 ArrayList 인스턴스 의 얕은 복사본을 반환한다. |
| boolean | contains(Object o) | 이 목록에 지정된 요소가 포함되어 있으면 true 를 반환한다. |
| void | ensureCapacity(int minCapacity) | 필요한 경우 이 ArrayList 인스턴스 의 용량을 늘려 최소 용량 인수로 지정된 요소 수 이상을 보유할 수 있도록 한다. |
| void | forEach(Consumer<? super E> action) | Iterable 모든 요소가 처리되거나 작업이 예외를 throw할 때까지 의 각 요소에 대해 지정된 작업을 수행한다. |
| E | get(int index) | 이 목록의 지정된 위치에 있는 요소를 반환한다. |
| int | indexOf(Object o) | 이 목록에서 지정된 요소가 처음 나타나는 인덱스를 반환하거나 이 목록에 요소가 없으면 -1을 반환한다. |
| boolean | isEmpty() | 이 목록에 요소가 없으면 true 를 반환한다. |
| Iterator<E> | iterator() | 이 목록의 요소에 대한 반복자를 적절한 순서로 반환한다. |
| int | lastIndexOf(Object o) | 이 목록에서 지정된 요소가 마지막으로 나타나는 인덱스를 반환하거나 이 목록에 요소가 포함되어 있지 않으면 -1을 반환한다. |
| ListIterator<E> | listIterator() | 이 목록의 요소에 대한 목록 반복자를 적절한 순서로 반환한다. |
| ListIterator<E> | listIterator(int index) | 목록의 지정된 위치에서 시작하여 이 목록의 요소에 대한 목록 반복자를 적절한 순서로 반환한다. |
| E | remove(int index) | 이 목록의 지정된 위치에 있는 요소를 제거한다. |
| boolean | remove(Object o) | 해당 객체가 있는 경우 이 목록에서 지정된 요소의 첫 번째 항목을 제거한다. |
| boolean | removeAll(Collection<?> c) | 지정된 컬렉션에 포함된 모든 요소를 이 목록에서 제거한다. |
| boolean | removeIf(Predicate<? super E> filter) | 주어진 술어를 만족하는 이 컬렉션의 모든 요소를 제거한다. |
| protected void |
removeRange(int fromIndex, int toIndex) | 이 목록에서 인덱스가 fromIndex, 포함 및 toIndex제외 사이에 있는 모든 요소를 제거한다. |
| void | replaceAll(UnaryOperator<E> operator) | 이 목록의 각 요소를 해당 요소에 연산자를 적용한 결과로 바꾼다. |
| boolean | retainAll(Collection<?> c) | 지정된 컬렉션에 포함된 이 목록의 요소만 유지한다. |
| E | set(int index, E element) | 이 목록의 지정된 위치에 있는 요소를 지정된 요소로 바꾼다. |
| int | size() | 이 목록의 요소 수를 반환한다. |
| void | sort(Comparator<? super E> c) | 지정된 순서에 따라 이 목록을 정렬(Comparator) |
| Spliterator<E> | spliterator() | 이 목록의 요소에 대해 지연 바인딩 및 장애 조치를 만든다(Spliterator) |
| List<E> | subList(int fromIndex, int toIndex) | 지정된 fromIndex, 포함 및 toIndex, 제외 사이의 이 목록 부분의 보기를 반환한다. |
| Object[] | toArray() | 이 목록의 모든 요소를 적절한 순서로 포함하는 배열을 반환한다.(첫 번째 요소에서 마지막 요소까지) |
| <T> T[] | toArray(T[] a) | 이 목록의 모든 요소를 적절한 순서로 포함하는 배열을 반환한다.(첫 번째 요소에서 마지막 요소까지) 반환된 배열의 런타임 유형은 지정된 배열의 런타임 유형이다. |
| void | trimToSize() | 이 ArrayList 인스턴스 의 용량을 목록의 현재 크기로 자른다. |
📌 LinkedList
LinkedList 컬렉션은 데이터를 효율적으로 추가, 삭제, 변경하기 위해 사용한다.
배열에는 모든 데이터가 연속적으로 존재하지만, LinkedList에는 불연속적으로 존재하며, 이 데이터는 서로 연결(link)되어 있다.
아래의 그림을 살펴보자.
| 용어 | 설명 |
| node | 데이터를 저장하는 요소 객체를 말한다. |
| prev | 이전 노드의 주소를 가리킨다. (첫번째 노드는 null) |
| value | 노드에 저장된 값을 의미한다. |
| next | 다음 노드의 주소를 가리킨다. (없을 시 null) |
그림을 통해 알 수 있듯이 LinkedList의 각 요소(node)들은 자신과 연결된 이전 요소 및 다음 요소의 주소 값과 데이터로 구성되어 있다.
LinkedList에 데이터를 삭제하려면,
삭제하고자 하는 요소의 이전 요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경하면 된다. 링크를 끊어줬다라고 생각하면 된다. 끊어진 노드는 자바의 가비지 컬렉터가 수거해간다. 배열처럼 데이터를 이동하기 위해 복사할 필요가 없기 때문에 처리 속도가 훨씬 빠르다.
LinkedList에 데이터를 추가하려면,
새로운 요소를 추가하고자 하는 위치의 이전 요소와 다음 요소 사이에 연결해주면 된다. 즉 이전 요소가 새로운 요소의 주소를 참조하고, 새로운 요소가 다음 요소를 참조하게 만들면 된다.
📌 ArrayList와 LinkedList의 차이
위 그림은 ArrayList에서 데이터를 추가하는 상황을 나타낸 그림이다.
ArrayList에서 데이터를 추가 또는 삭제하려면 그림과 같이 다른 데이터를 복사해서 이동해야 한다. ArrayList에 객체를 순차적으로 저장할 때는 데이터를 이동하지 않아도 되므로 작업 속도가 빠르지만, 중간에 위치한 객체를 추가 및 삭제할 때에는 데이터 이동이 많이 일어나므로 속도가 저하된다.
반면, 인덱스가 n인 요소의 주소값을 얻기 위해서는 배열의 주소 + n * 데이터 타입의 크기를 계산하여 데이터에 빠르게 접근이 가능하기 때문에 검색(읽기) 측면에서는 유리하다.
❗️효율적
- 데이터를 순차적으로 추가하거나 삭제하는 경우
- 순차적으로 추가한다는 것은 0번 인덱스에서부터 데이터를 추가하는 것을 의미
- 순차적으로 삭제한다는 것은 마지막 인덱스에서부터 데이터를 삭제하는 것을 의미
- 데이터를 읽어들이는 경우
- 인덱스를 통해 바로 데이터에 접근할 수 있으므로 검색이 빠르다.
❗️비효율적
- 중간에 데이터를 추가하거나, 중간에 위치하는 데이터를 삭제하는 경우
- 추가 또는 삭제 시, 해당 데이터의 뒤에 위치한 값들을 뒤로 밀어주거나 앞으로 당겨주어야 한다.
Apple과 Orange 사이에 Mango라는 데이터를 추가하는 상황을 가정해보자. 이 때, 내부적으로 다음과 같은 동작이 이루어진다.
- Mango 객체가 생성된다.
- Apple의 Next에 Mango의 주소값이 저장된다.
- 이 때, Mango의 Prev에 Apple의 주소값이 저장된다.
- Mango의 Next에 Orange의 주소값이 저장된다.
- 이 때, Orange의 Prev에 Mango의 주소값이 저장된다.
이처럼 LinkedList의 중간에 데이터를 추가하면, Next와 Prev에 저장되어 있는 주소값만 변경해주면 되므로, 각 요소들을 ArrayList처럼 뒤로 밀어내지 않아도 다. 마찬가지로, 중간에 위치한 데이터를 삭제하는 경우에도 삭제한 데이터의 뒤에 위치하는 요소들을 앞으로 당기지 않아도 된다.
따라서 데이터를 중간에 추가하거나 삭제하는 경우, LinkedList는 ArrayList보다 빠른 속도를 보여준다.
하지만 데이터 검색할 때에는 시작 인덱스에서부터 찾고자하는 데이터까지 순차적으로 각 노드에 접근해야 하기 때문에 데이터 검색에 있어서는 ArrayList보다 상대적으로 속도가 느리다.
❗️효율적
- 중간에 위치하는 데이터를 추가하거나 삭제하는 경우
- 데이터를 중간에 추가하는 경우, Prev와 Next의 주소값만 변경하면 되므로, 다른 요소들을 이동시킬 필요가 없다.
❗️비효율적
- 데이터를 검색하는 경우
- 데이터를 검색하는 경우, 각 노드를 순차적으로 접근해야하기 때문에 검색에 있어서는 상대적으로 느리다.
결론적으로,
데이터의 잦은 변경이 예상된다면 LinkedList를 사용한다.
데이터의 개수가 변하지 않는다면 ArrayList를 사용한다.
댓글