자바 공식 Collection Framework 튜토리얼
Trail: Collections (The Java™ Tutorials)
The Java Tutorials have been written for JDK 8. Examples and practices described in this page don't take advantage of improvements introduced in later releases and might use technology no longer available. See Java Language Changes for a summary of updated
docs.oracle.com
https://en.wikipedia.org/wiki/Java_collections_framework
List Interface
List 인터페이스는 자바 프로그래밍 언어에서 제공하는 인터페이스 중 하나입니다. 이 인터페이스는 순서가 있는 요소의 컬렉션을 나타내며, 중복된 요소를 포함할 수 있습니다. List 인터페이스는 자바의 컬렉션 프레임워크에 속하며, 배열과 유사한 동작을 수행하는 동적인 크기의 리스트를 제공합니다.
List 인터페이스는 java.util 패키지에 정의되어 있으며, java.util.Collection 인터페이스를 확장하고 있습니다. 따라서 List는 Collection 인터페이스에서 정의된 모든 메서드를 상속받습니다. 또한 List 인터페이스는 자체적으로 인덱스를 사용하여 요소에 접근하는 메서드를 추가로 정의하고 있습니다.
List 인터페이스의 주요 특징은 다음과 같습니다:
- 순서: List의 요소는 순서를 가지고 있으며, 요소의 삽입 순서를 유지합니다. 따라서 요소를 추가한 순서대로 접근할 수 있습니다.
- 중복 요소: List는 중복된 요소를 포함할 수 있습니다. 즉, 동일한 값을 가진 요소를 여러 개 가질 수 있습니다.
- 인덱스 기반 접근: List는 인덱스를 사용하여 요소에 접근할 수 있습니다. 인덱스는 0부터 시작하며, 요소의 위치를 지정하는 정수값으로 사용됩니다. 따라서 List에서는 인덱스를 통해 요소를 검색하거나 수정할 수 있습니다.
package java.util;
import java.util.function.UnaryOperator;
public interface List<E> extends Collection<E> {
// Query Operations
int size();
boolean isEmpty();
boolean contains(Object o);
Iterator<E> iterator();
Object[] toArray();
<T> T[] toArray(T[] a);
// Modification Operations
boolean add(E e);
boolean remove(Object o);
// Bulk Modification Operations
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
boolean addAll(int index, Collection<? extends E> c);
boolean removeAll(Collection<?> c);
boolean retainAll(Collection<?> c);
default void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final ListIterator<E> li = this.listIterator();
while (li.hasNext()) {
li.set(operator.apply(li.next()));
}
}
@SuppressWarnings({"unchecked", "rawtypes"})
default void sort(Comparator<? super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator<E> i = this.listIterator();
for (Object e : a) {
i.next();
i.set((E) e);
}
}
void clear();
// Comparison and hashing
boolean equals(Object o);
int hashCode();
// Positional Access Operations
E get(int index);
E set(int index, E element);
void add(int index, E element);
E remove(int index);
// Search Operations
int indexOf(Object o);
int lastIndexOf(Object o);
// List Iterators
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index);
// View
List<E> subList(int fromIndex, int toIndex);
@Override
default Spliterator<E> spliterator() {
if (this instanceof RandomAccess) {
return new AbstractList.RandomAccessSpliterator<>(this);
} else {
return Spliterators.spliterator(this, Spliterator.ORDERED);
}
}
@SuppressWarnings("unchecked")
static <E> List<E> of() {
return (List<E>) ImmutableCollections.EMPTY_LIST;
}
static <E> List<E> of(E e1) {
return new ImmutableCollections.List12<>(e1);
}
static <E> List<E> of(E e1, E e2) {
return new ImmutableCollections.List12<>(e1, e2);
}
static <E> List<E> of(E e1, E e2, E e3) {
return ImmutableCollections.listFromTrustedArray(e1, e2, e3);
}
static <E> List<E> of(E e1, E e2, E e3, E e4) {
return ImmutableCollections.listFromTrustedArray(e1, e2, e3, e4);
}
static <E> List<E> of(E e1, E e2, E e3, E e4, E e5) {
return ImmutableCollections.listFromTrustedArray(e1, e2, e3, e4, e5);
}
static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6) {
return ImmutableCollections.listFromTrustedArray(e1, e2, e3, e4, e5,
e6);
}
static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7) {
return ImmutableCollections.listFromTrustedArray(e1, e2, e3, e4, e5,
e6, e7);
}
static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8) {
return ImmutableCollections.listFromTrustedArray(e1, e2, e3, e4, e5,
e6, e7, e8);
}
static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9) {
return ImmutableCollections.listFromTrustedArray(e1, e2, e3, e4, e5,
e6, e7, e8, e9);
}
static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9, E e10) {
return ImmutableCollections.listFromTrustedArray(e1, e2, e3, e4, e5,
e6, e7, e8, e9, e10);
}
@SafeVarargs
@SuppressWarnings("varargs")
static <E> List<E> of(E... elements) {
switch (elements.length) { // implicit null check of elements
case 0:
@SuppressWarnings("unchecked")
var list = (List<E>) ImmutableCollections.EMPTY_LIST;
return list;
case 1:
return new ImmutableCollections.List12<>(elements[0]);
case 2:
return new ImmutableCollections.List12<>(elements[0], elements[1]);
default:
return ImmutableCollections.listFromArray(elements);
}
}
static <E> List<E> copyOf(Collection<? extends E> coll) {
return ImmutableCollections.listCopy(coll);
}
}
List 인터페이스에서 자주 사용되는 메서드는 다음과 같습니다:
- add(element): 지정된 요소를 List에 추가합니다.
- remove(element): 지정된 요소를 List에서 제거합니다.
- remove(element): 지정된 요소를 List에서 제거합니다.get(index): 지정된 인덱스에 위치한 요소를 반환합니다.
- set(index, element): 지정된 인덱스에 위치한 요소를 새로운 값으로 대체합니다.
- size(): List에 포함된 요소의 개수를 반환합니다.
- contains(element): List에 지정된 요소가 포함되어 있는지 여부를 확인합니다.
- of() : List 인터페이스의 of 메서드는 자바 9부터 추가된 정적 메서드로, 인자로 전달된 요소들로 구성된 변경 불가능한(List) 리스트를 생성하는 간편한 방법을 제공합니다. List.of 메서드는 가변 인자(varargs)를 허용하며, 전달된 요소들을 순서대로 포함하는 변경 불가능한 리스트를 반환합니다. 이 리스트는 크기가 고정되어 있고, 요소들은 수정할 수 없습니다. 따라서 add, remove와 같은 변경 작업은 지원되지 않습니다.
List 인터페이스는 자바에서 다양한 구현 클래스를 가지고 있습니다. 대표적으로 ArrayList, LinkedList, Vector 등이 있으며, 각각의 구현 클래스는 내부적으로 다른 방식으로 데이터를 저장하고 처리합니다. 이러한 구현 클래스는 List 인터페이스를 구현하고 있으므로, List 인터페이스의 메서드를 모두 사용할 수 있습니다.
Static Method of Interface
인터페이스에서 static 메서드는 인터페이스에 정의된 메서드 중에서 정적으로 호출할 수 있는 메서드입니다. 이러한 메서드는 인터페이스의 인스턴스 생성과 관계없이 호출할 수 있습니다.
기존의 인터페이스 메서드는 일반적으로 인터페이스를 구현하는 클래스에서 오버라이딩되어야 했습니다. 하지만 static 메서드는 오버라이딩할 필요 없이 인터페이스에서 직접 호출할 수 있습니다. 또한, static 메서드는 인터페이스를 구현하는 클래스에게 상속되지 않습니다.
static 메서드를 사용하는 주요한 이유는 다음과 같습니다:
1. 유틸리티 메서드 제공: static 메서드를 사용하여 인터페이스와 관련된 유틸리티 기능을 제공할 수 있습니다. 예를 들어, Collections 클래스는 List 인터페이스와 관련된 유틸리티 메서드들을 static으로 제공합니다.
2. 기본 구현 제공: 인터페이스에 새로운 메서드를 추가할 때, 기존에 인터페이스를 구현하는 클래스들이 모두 해당 메서드를 구현해야 하는 문제가 발생할 수 있습니다. 이를 방지하기 위해 default 메서드를 사용하여 기본 구현을 제공할 수 있습니다. 이때 default 메서드는 인터페이스 내부에서 static 메서드를 활용할 수 있습니다.
요약하면, static 메서드는 인터페이스 내에서 유틸리티 메서드나 기본 구현을 제공하기 위해 사용됩니다. 인터페이스를 구현하는 클래스에게는 상속되지 않으며, 인터페이스 자체에서 직접 호출할 수 있습니다.
※RandomAccess
RandomAccess 마커 인터페이스는 JVM에게 컬렉션의 특성에 대한 힌트를 제공합니다. JVM은 이 힌트를 활용하여 컬렉션에 대한 최적화를 수행할 수 있습니다. RandomAccess 인터페이스를 구현한 컬렉션은 빠른 무작위 접근을 지원한다는 힌트를 제공합니다. 이를 통해 JVM은 해당 컬렉션에 대한 반복, 검색, 접근 작업 등을 최적화할 수 있습니다. 예를 들어, JVM은 RandomAccess 인터페이스를 구현한 ArrayList와 같은 배열 기반의 리스트에 대해 내부적으로 빠른 인덱스 기반 접근 방식을 사용할 수 있습니다. 반면, RandomAccess 인터페이스를 구현하지 않은 컬렉션은 순차적인 접근을 가정하고 처리할 수 있습니다. 예를 들어, LinkedList와 같은 연결 리스트는 요소에 접근하기 위해 순차적으로 노드를 따라가야 하기 때문에, JVM은 내부적으로 노드를 탐색하는 방식을 사용할 수 있습니다. JVM은 RandomAccess 인터페이스를 사용하여 컬렉션의 특성을 확인하고, 이를 기반으로 최적화된 알고리즘 및 접근 방식을 선택합니다. 이러한 최적화는 컬렉션을 사용하는 애플리케이션의 성능 향상에 기여할 수 있습니다.
ArrayList
ArrayList를 사용하는 다양한 샘플 코드입니다.
1. ArrayList에 요소 추가하기:
import java.util.ArrayList;
public class ArrayListExample {
public static void main(String[] args) {
ArrayList<String> fruits = new ArrayList<>();
// 요소 추가
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Orange");
// 결과 출력
System.out.println(fruits); // [Apple, Banana, Orange]
}
}2. ArrayList에서 요소 제거하기:
import java.util.ArrayList;
public class ArrayListExample {
public static void main(String[] args) {
ArrayList<String> fruits = new ArrayList<>();
// 요소 추가
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Orange");
// 요소 제거
fruits.remove("Banana");
// 결과 출력
System.out.println(fruits); // [Apple, Orange]
}
}3. ArrayList의 크기 확인하기:
import java.util.ArrayList;
public class ArrayListExample {
public static void main(String[] args) {
ArrayList<String> fruits = new ArrayList<>();
// 요소 추가
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Orange");
// 크기 확인
int size = fruits.size();
// 결과 출력
System.out.println("크기: " + size); // 크기: 3
}
}
4. ArrayList에서 요소 접근하기:
import java.util.ArrayList;
public class ArrayListExample {
public static void main(String[] args) {
ArrayList<String> fruits = new ArrayList<>();
// 요소 추가
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Orange");
// 인덱스를 이용한 요소 접근
String firstFruit = fruits.get(0);
String lastFruit = fruits.get(fruits.size() - 1);
// 결과 출력
System.out.println("첫 번째 과일: " + firstFruit); // 첫 번째 과일: Apple
System.out.println("마지막 과일: " + lastFruit); // 마지막 과일: Orange
}
}5. ArrayList의 요소 순회하기:
import java.util.ArrayList;
public class ArrayListExample {
public static void main(String[] args) {
ArrayList<String> fruits = new ArrayList<>();
// 요소 추가
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Orange");
// 요소 순회
for (String fruit : fruits) {
System.out.println(fruit);
}
}
}6. ArrayList에서 특정 요소의 인덱스 찾기
import java.util.ArrayList;
public class ArrayListExample {
public static void main(String[] args) {
ArrayList<String> fruits = new ArrayList<>();
// 요소 추가
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Orange");
// 특정 요소의 인덱스 찾기
int index = fruits.indexOf("Banana");
// 결과 출력
System.out.println("Banana의 인덱스: " + index); // Banana의 인덱스: 1
}
}7. ArrayList의 모든 요소 제거
import java.util.ArrayList;
public class ArrayListExample {
public static void main(String[] args) {
ArrayList<String> fruits = new ArrayList<>();
// 요소 추가
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Orange");
// 모든 요소 제거
fruits.clear();
// 결과 출력
System.out.println(fruits); // []
}
}8. ArrayList에서 요소의 존재 여부 확인
import java.util.ArrayList;
public class ArrayListExample {
public static void main(String[] args) {
ArrayList<String> fruits = new ArrayList<>();
// 요소 추가
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Orange");
// 요소의 존재 여부 확인
boolean containsBanana = fruits.contains("Banana");
boolean containsGrape = fruits.contains("Grape");
// 결과 출력
System.out.println("Banana의 존재 여부: " + containsBanana); // Banana의 존재 여부: true
System.out.println("Grape의 존재 여부: " + containsGrape); // Grape의 존재 여부: false
}
}9. ArrayList의 요소를 배열로 반환하기
import java.util.ArrayList;
public class ArrayListExample {
public static void main(String[] args) {
ArrayList<String> fruits = new ArrayList<>();
// 요소 추가
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Orange");
// 배열로 변환
String[] fruitArray = fruits.toArray(new String[0]);
// 결과 출력
for (String fruit : fruitArray) {
System.out.println(fruit);
}
}
}10. ArrayList의 요소를 정렬하기:
import java.util.ArrayList;
import java.util.Collections;
public class ArrayListExample {
public static void main(String[] args) {
ArrayList<String> fruits = new ArrayList<>();
// 요소 추가
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Orange");
// 정렬
Collections.sort(fruits);
// 결과 출력
System.out.println(fruits); // [Apple, Banana, Orange]
}
}11. ArrayList의 요소를 역순으로 정렬하기:
import java.util.ArrayList;
import java.util.Collections;
public class ArrayListExample {
public static void main(String[] args) {
ArrayList<String> fruits = new ArrayList<>();
// 요소 추가
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Orange");
// 역순으로 정렬
Collections.reverse(fruits);
// 결과 출력
System.out.println(fruits); // [Orange, Banana, Apple]
}
}12. ArrayList의 일부 요소 추출하기:
import java.util.ArrayList;
import java.util.List;
public class ArrayListExample {
public static void main(String[] args) {
ArrayList<String> fruits = new ArrayList<>();
// 요소 추가
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Orange");
fruits.add("Grape");
fruits.add("Watermelon");
// 일부 요소 추출
List<String> selectedFruits = fruits.subList(1, 4);
// 결과 출력
System.out.println(selectedFruits); // [Banana, Orange, Grape]
}
}13. ArrayList의 요소 복사하기:
import java.util.ArrayList;
import java.util.Collections;
public class ArrayListExample {
public static void main(String[] args) {
ArrayList<String> fruits = new ArrayList<>();
// 요소 추가
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Orange");
// 요소 복사
ArrayList<String> copiedFruits = new ArrayList<>(fruits);
// 결과 출력
System.out.println(copiedFruits); // [Apple, Banana, Orange]
}
}14. ArrayList의 요소를 다른 ArrayList에 추가하기:
import java.util.ArrayList;
import java.util.Collections;
public class ArrayListExample {
public static void main(String[] args) {
ArrayList<String> fruits = new ArrayList<>();
// 요소 추가
fruits.add("Apple");
fruits.add("Banana");
// 다른 ArrayList에 요소 추가
ArrayList<String> moreFruits = new ArrayList<>();
moreFruits.add("Orange");
moreFruits.addAll(fruits);
// 결과 출력
System.out.println(moreFruits); // [Orange, Apple, Banana]
}
}
LinkedList
Linked List
링크드 리스트는 컴퓨터 과학과 프로그래밍에서 데이터를 저장하고 조직화하는 데 사용되는 데이터 구조입니다. 링크드 리스트는 각각의 노드로 구성되며, 각 노드에는 데이터 요소와 다음 노드를 가리키는 참조(또는 링크)가 포함됩니다.
링크드 리스트의 기본 구성 요소는 노드입니다. 각 노드에는 일반적으로 데이터 부분과 다음 노드를 가리키는 포인터(또는 참조) 부분이 있습니다. 데이터 부분은 실제 값이나 정보를 저장하고, 다음 포인터는 시퀀스에서 다음 노드를 가리킵니다.
링크드 리스트는 특히 리스트의 시작 또는 끝에서 요소를 효율적으로 삽입하고 삭제할 수 있습니다. 그러나 리스트의 중간에 있는 요소에 접근하는 것은 배열과 같은 다른 데이터 구조에 비해 느릴 수 있습니다.
링크드 리스트에는 단일 링크드 리스트, 이중 링크드 리스트, 순환 링크드 리스트 등 여러 종류가 있습니다. 단일 링크드 리스트는 각 노드가 다음 노드를 가리키는 참조만 가지고 있습니다. 이중 링크드 리스트는 각 노드가 다음과 이전 노드를 가리키는 참조를 모두 가지고 있어 양방향으로 더 쉬운 순회가 가능합니다. 순환 링크드 리스트는 마지막 노드가 첫 번째 노드를 가리키는 루프를 형성합니다.
링크드 리스트는 스택, 큐, 해시 테이블과 같은 다른 데이터 구조를 구현하는 데 자주 사용됩니다. 동적으로 메모리를 관리하는 데 유연성을 제공하며, 요소 수가 알려지지 않거나 계속 변하는 경우에 특히 유용합니다.
Java LinkedList
자바 LinkedList는 자바 컬렉션 프레임워크의 하나로, 더블 링크드 리스트(doubly linked list)로 구현된 데이터 구조입니다. 각 요소는 이전 요소와 다음 요소를 가리키는 링크(참조)를 가지고 있습니다. LinkedList는 동적인 크기 조정이 가능하며, 요소의 삽입, 삭제, 검색에 효율적입니다.
LinkedList의 주요 특징은 다음과 같습니다:
- 더블 링크드 리스트 구조: LinkedList의 각 노드는 데이터 요소와 이전 노드와 다음 노드를 가리키는 두 개의 링크로 구성됩니다. 이 링크를 통해 순차적인 탐색, 요소의 삽입 및 삭제 작업을 수행할 수 있습니다.
- 동적 크기 조정: LinkedList는 내부적으로 연결된 노드들로 구성되어 있으며, 요소의 추가나 삭제 시 필요에 따라 크기를 동적으로 조정할 수 있습니다. 이는 배열(Array)과 달리 크기 제한에 대한 걱정 없이 요소를 추가하거나 삭제할 수 있다는 장점을 가지고 있습니다.
- 느린 접근 시간: LinkedList는 인덱스를 기반으로 한 빠른 랜덤 액세스를 제공하지 않습니다. 원하는 위치의 요소에 접근하기 위해서는 첫 번째 노드부터 순차적으로 탐색해야 합니다. 따라서 요소를 검색할 때는 LinkedList보다 배열(ArrayList 등)을 사용하는 것이 더 효율적입니다.
- 중간 삽입 및 삭제의 효율성: LinkedList는 중간에 요소를 삽입하거나 삭제하는 작업에 용이합니다. 이 작업은 해당 위치의 이전 노드와 다음 노드의 링크만 변경하면 되기 때문에 배열에 비해 효율적입니다.
Java의 LinkedList는 이중 링크드 리스트는 리스트에서 시퀀스를 나타내는 노드 그룹으로 구성됩니다. 노드 그룹은 노드의 시퀀스에 요소를 저장합니다.
각 노드에는 데이터가 저장된 데이터 필드와 이전 노드와 다음 노드를 가리키는 참조 또는 포인터인 왼쪽(left)과 오른쪽(right) 필드가 세 개의 필드가 있습니다.
포인터는 다음 노드와 이전 노드의 주소를 나타냅니다. 링크드 리스트의 요소를 Node라고 합니다.
첫 번째 노드의 이전 필드와 마지막 노드의 다음 필드는 아무것도 가리키지 않으므로 null 값으로 설정해야 합니다.
Java의 LinkedList에 새로운 요소를 저장할 때마다 자동으로 새로운 노드가 생성됩니다.
요소가 추가될 때마다 크기가 증가하며, 초기 용량은 0입니다. 요소가 제거되면 크기가 자동으로 줄어듭니다.
LinkedList에 요소를 추가하거나 제거하는 작업은 빠르게 수행되며 동일한 시간(즉, 상수 시간)이 소요됩니다.
따라서, 요소가 리스트의 중간에 삽입되거나 제거되는 상황에서 특히 유용합니다.
링크드 리스트에서 요소는 연속적인 메모리 위치에 저장되지 않습니다. 요소(일반적으로 노드라고 함)는 노드 부분의 왼쪽과 오른쪽을 이용하여 서로 연결하여 메모리의 여유 공간 어디에든 위치할 수 있습니다.
Java에서 선형 이중 링크드 리스트의 배열 표현은 아래 그림에 나와 있습니다.
이로써, LinkedList는 요소의 재배치를 필요로 하지 않지만 각 요소가 링크에 의해 다음과 이전 요소와 연결되어야 한다는 점이 필요합니다.
노드의 오른쪽에는 다음 요소의 주소가 포함되어 있고, 노드의 왼쪽에는 리스트 내의 이전 요소의 주소가 포함되어 있습니다.
Java의 LinkedList 클래스는 List, Deque, Queue 인터페이스를 구현합니다. AbstractSequentialList를 상속하였습니다. 또한 serializable과 cloneable과 같은 마커 인터페이스를 구현하지만 random access 인터페이스는 구현하지 않습니다.
주요 기능
Java LinkedList 클래스의 주요 기능은 다음과 같습니다:
1. LinkedList의 내부 데이터 구조는 이중 링크드 리스트입니다. 이는 배열 리스트와 마찬가지로 List 인터페이스의 다른 구체적인 구현체입니다.
2. Java LinkedList 클래스는 중복 요소를 저장할 수 있습니다.
3. LinkedList에는 null 요소를 추가할 수 있습니다.
4. LinkedList에는 다른 타입의 요소를 저장할 수 있습니다.
5. Java LinkedList는 동기화되지 않았습니다. 따라서 여러 스레드가 동시에 동일한 LinkedList 객체에 접근할 수 있습니다. 따라서 스레드 동기화가 지원되지 않습니다. 그러나 LinkedList는 동기화되지 않았으므로 작업이 더 빠릅니다.
6. LinkedList에서 요소의 삽입과 제거는 빠릅니다. 각 요소의 추가 및 제거를 위한 요소들을 이동시킬 필요가 없기 때문입니다. Next와 Prev 요소에 대한 참조만 변경됩니다.
7. LinkedList는 중간에 삽입이나 삭제가 빈번한 경우 가장 좋은 선택입니다.
8. LinkedList에서 요소를 검색하는 것은 매우 느립니다. 요소에 도달하기 위해 시작점이나 끝점부터 순회해야 하기 때문입니다.
9. LinkedList는 "스택"으로 사용할 수 있습니다. pop() 및 push() 메서드를 사용하여 스택으로 동작할 수 있습니다.
10. Java LinkedList는 무작위 액세스 인터페이스를 구현하지 않습니다. 따라서 요소에 임의로 액세스(검색)할 수 없습니다. 주어진 요소에 액세스하려면 LinkedList에서 시작점이나 끝점부터 순회해야 합니다.
11. ListIterator를 사용하여 LinkedList 요소를 Iterable 할 수 있습니다.
12. Java LinkedList에서는 이미 리스트에 저장된 데이터 항목에 영향을 주지 않고 삽입(추가) 작업을 수행할 수 있습니다.
위 개념을 이해하기 위해 예를 살펴보겠습니다.
1. 초기 LinkedList에는 다음과 같은 데이터가 있다고 가정해 봅시다. 아래 그림과 같습니다.
LinkedList<Integer> linkedlist = new LinkedList<>();
2. 이제 이 링크드 리스트에 삽입 작업을 수행해보겠습니다. add() 메서드를 사용하여 인덱스 위치 2에 요소 G를 추가합니다. 요소 G를 추가하는 구문은 다음과 같습니다:
linkedlist.add(2,"G");링크드 리스트에서 삽입 작업이 발생할 때, 내부적으로 LinkedList는 메모리의 가용한 어떤 공간이든 G 요소를 가진 노드를 생성하고, 리스트 내의 어떤 요소도 이동하지 않고 Next와 Prev 포인터만 변경합니다. 위의 그림에서 업데이트된 LinkedList를 확인할 수 있습니다.
Java LinkedList에서 삭제 작업이 어떻게 수행되는지 알아보겠습니다.
이전 섹션에서 이미 링크드 리스트가 내부적으로 삽입 작업을 수행하는 방법을 살펴보았습니다. 이제 Java 링크드 리스트가 내부적으로 삭제 작업을 수행하는 방법에 대해 설명하겠습니다.
1. 초기 LinkedList에 다음과 같은 데이터가 있다고 가정해 봅시다.
2. 인덱스 1에 위치한 요소 B를 제거하려고 합니다. 요소 B를 삭제하는 구문은 다음과 같습니다:
linkedlist.remove(1);삭제 작업이 발생하면 요소 B가 있는 노드가 삭제되고 다음과 이전 포인터가 변경됩니다. 삭제된 노드는 사용되지 않는 메모리가 됩니다.
따라서 Java는 가비지 컬렉션을 사용하여 사용되지 않는 메모리 공간을 정리합니다.
LinkedList Methods
List 인터페이스를 구현하는 것 외에도, Java LinkedList 클래스는 리스트의 양쪽 끝에서 요소를 검색, 삽입 및 제거하기 위한 메서드를 제공합니다.
LinkedList의 메서드는 아래 표에 나열되어 있습니다
| SN | Method | Description |
| 1 | boolean add(Object o) | list의 끝에 지정된 요소를 추가하는 데 사용됩니다. |
| 2 | void add(int index, Object o) | list의 지정된 위치에 지정된 요소를 삽입하는 데 사용됩니다. |
| 3 | boolean addAll(Collection c) | 지정된 컬렉션의 모든 요소를 이 list의 끝에 추가하는 데 사용됩니다. |
| 4 | boolean addAll(int index, Collection c) | list의 지정된 인덱스 위치에 지정된 컬렉션의 모든 요소를 추가하는 데 사용됩니다. |
| 5 | void clear() | list에서 모든 요소를 제거하거나 삭제하는 데 사용됩니다. |
| 6 | boolean contains(Object o) | list에 지정된 요소가 포함되어 있으면 true를 반환합니다. |
| 7 | int size() | list의 요소 수를 얻는 데 사용됩니다. |
| 8 | Object[] toArray() | list의 모든 요소를 적절한 순서로 포함하는 배열을 반환합니다. |
| 9 | Object clone() | 이 메서드는 ArrayList의 shallow copy을 반환하는 데 사용됩니다. |
| 10 | boolean remove(Object o) | 이 메서드는 linked list에서 지정된 요소의 첫 번째 항목을 제거하는 데 사용됩니다. |
| 11 | Element remove(int index) | 이 메서드는 linked list의 지정된 위치에 있는 요소를 제거하는 데 사용됩니다. |
| 12 | Element element() | This method is used to retrieve the first element of the linked list. |
| 13 | E get(int index) | list의 지정된 위치에 있는 요소를 가져오는 데 사용됩니다. |
| 14 | Element set(int index, E element) | list의 지정된 위치에 있는 요소를 지정된 요소로 교체하는 데 사용됩니다. |
| 15 | int indexOf(Object o) | list에서 지정된 요소가 처음 나타나는 인덱스를 가져오는 데 사용됩니다. list에 요소가 없으면 -1을 반환합니다. |
| 16 | int lastIndexOf(Object o) | list에서 지정된 요소의 마지막 항목 인덱스를 가져오는 데 사용됩니다. list에 해당 요소가 없으면 -1을 반환합니다. |
| 17 | Iterator iterator() | 이 메서드는 linked list에서 적절한 순서로 요소에 대한 반복자를 반환합니다. |
| 18 | ListIterator listIterator(int index) | 이 메서드는 list의 지정된 위치에서 시작하여 적절한 순서로 요소의 목록 반복자를 반환합니다. |
LinkedList Deque Methods
Java LinkedList 클래스는 Deque 인터페이스에서 상속받은 다양한 특정 메서드도 가지고 있습니다. 이들은 아래 표에 나열되어 있습니다:
| SN | Method | Description |
| 1 | addFirst(element) | 리스트의 맨 앞에 요소를 추가합니다. |
| 2 | addLast(element) | 리스트의 맨 뒤에 요소를 추가합니다. |
| 3 | offerFirst(element) | 리스트의 맨 앞에 요소를 추가하고 성공 여부를 반환합니다. |
| 4 | offerLast(element) | 리스트의 맨 뒤에 요소를 추가하고 성공 여부를 반환합니다. |
| 5 | removeFirst() | 리스트의 맨 앞에 있는 요소를 제거하고 반환합니다. |
| 6 | removeLast() | 리스트의 맨 뒤에 있는 요소를 제거하고 반환합니다. |
| 7 | pollFirst() | 리스트의 맨 앞에 있는 요소를 제거하고 반환하거나 null을 반환합니다. |
| 8 | pollLast() | 리스트의 맨 뒤에 있는 요소를 제거하고 반환하거나 null을 반환합니다. |
| 9 | getFirst() | 리스트의 맨 앞에 있는 요소를 반환합니다. |
| 10 | getLast() | 리스트의 맨 뒤에 있는 요소를 반환합니다. |
| 11 | peekFirst() | 리스트의 맨 앞에 있는 요소를 반환하거나 null을 반환합니다. |
| 12 | peekLast() | 리스트의 맨 뒤에 있는 요소를 반환하거나 null을 반환합니다. |
| 13 | push(element) | 리스트의 맨 앞에 요소를 추가합니다. |
| 14 | pop() | 리스트의 맨 앞에 있는 요소를 제거하고 반환합니다. |
| 15 | removeFirstOccurrence(element) | 주어진 요소와 일치하는 첫 번째 요소를 제거하고 반환합니다. |
| 16 | removeLastOccurrence(element) | 주어진 요소와 일치하는 마지막 요소를 제거하고 반환합니다. |
이러한 메서드를 사용하여 LinkedList에서 큐나 덱의 기능을 수행할 수 있습니다.
Java 애플리케이션에서 LinkedList를 사용하는 가장 좋은 경우는 리스트의 중간에 요소를 추가하거나 제거하는 작업이 빈번한 경우입니다. 링크드 리스트에서의 요소 추가와 제거는 ArrayList와 비교했을 때 더 빠르기 때문에 이러한 경우에는 Java LinkedList가 가장 적합한 선택입니다.
이 개념을 이해하기 위해 실제 시나리오를 살펴보겠습니다. 예를 들어 ArrayList에 100개의 요소가 있다고 가정해 봅시다. ArrayList에서 50번째 요소를 제거한다면, 51번째 요소는 50번째 위치로 이동하고, 52번째 요소는 51번째 위치로 이동하며, 다른 요소들에 대해서도 이러한 작업이 이루어져야 합니다. 이렇게 되면 요소의 이동에 많은 시간이 소요되어 ArrayList에서의 조작이 느려집니다.
그러나 링크드 리스트의 경우, 링크드 리스트에서 50번째 요소를 제거한다면, 제거 후에 요소의 이동은 발생하지 않습니다. 오직 다음 노드와 이전 노드의 참조만 변경됩니다.
또한 LinkedList는 스택(LIFO) 또는 큐(FIFO) 데이터 구조가 필요한 경우에도 중복을 허용하여 사용할 수 있습니다.
LinkedList를 사용하는 최악의 경우는 링크드 리스트에서 요소를 검색(조회)하는 작업이 빈번한 경우입니다. ArrayList와 비교하여 링크드 리스트에서 요소를 검색하는 것은 매우 느리기 때문에 LinkedList는 최악의 선택입니다.
LinkedList는 무작위 액세스 인터페이스를 구현하지 않습니다. 따라서 요소에 임의로 액세스(조회)할 수 없습니다. 시작점이나 끝점부터 순회하여 링크드 리스트의 요소에 도달해야 합니다.
이 개념을 이해하기 위해 실제 시나리오를 고려해 보겠습니다.
리스트에 10개의 요소가 있다고 가정해 봅시다. 링크드 리스트가 첫 번째 요소에 액세스하여 요소를 가져오는 데 1초가 걸린다고 가정해 봅시다.
첫 번째 노드에서 두 번째 요소의 주소가 사용 가능하므로, 두 번째 요소에 액세스하고 가져오기 위해서는 2초가 걸릴 것입니다.
마찬가지로, 리스트에서 9번째 요소를 가져오려면 LinkedList는 9초가 걸릴 것입니다. 왜냐하면 9번째 요소의 주소는 8번째 노드에 있고, 8번째 노드의 주소는 7번째 노드에 있기 때문입니다.
그러나 리스트에 100만 개의 요소가 있고, 리스트에서 50만 번째 요소를 가져오려고 한다면 링크드 리스트는 50만 번째 요소를 액세스하고 가져오는 데 1년이 걸릴 수도 있습니다.
따라서 링크드 리스트는 링크드 리스트에서 요소를 검색하거나 탐색하는 경우에는 최악의 선택입니다.
이 경우에는 ArrayList가 리스트에서 요소를 가져오는 데 가장 적합한 선택입니다. 왜냐하면 ArrayList는 무작위 액세스 인터페이스를 구현하기 때문에 임의의 위치에서 배열 리스트에서 요소를 매우 빠르게 가져올 수 있기 때문입니다.
'Java' 카테고리의 다른 글
| Java Collection Framework-2 (0) | 2024.04.09 |
|---|---|
| Functional Interface (0) | 2024.04.09 |
| 자바 예외 처리 (0) | 2024.04.09 |
| Callable & ExecutorService (0) | 2024.04.09 |
| Generics 4 (0) | 2024.04.09 |
