1.ArrayList는 동적 배열 기반의 데이터 구조를 구현하고, LinkedList는 연결된 목록 기반의 데이터 구조를 구현합니다.
2. 가져오고 설정하기 위한 임의 액세스의 경우 ArrayList는 무작위로 배치될 수 있는 반면 LinkedList는 포인터를 노드로 단계별로 이동해야 하기 때문에 LinkedList보다 ArrayList가 더 좋습니다. (배열과 연결리스트를 참고해서 생각해 보세요)
3. 신규 및 삭제 작업 추가 및 제거의 경우 LinedList는 포인터만 수정하면 되고 ArrayList는 삭제된 객체의 공간을 채우기 위해 데이터를 이동해야 합니다.
ArrayList 및 LinkedList는 일련의 개체 참조를 저장하는 데 사용되는 두 가지 컬렉션 클래스입니다. 예를 들어 ArrayList를 사용하여 일련의 문자열 또는 정수를 저장할 수 있습니다. 그렇다면 ArrayList와 LinkedList의 성능 차이는 무엇입니까? 언제 ArrayList를 사용해야 하며 언제 LinkedList를 사용해야 합니까?
하나. 시간 복잡도
첫 번째 요점은 ArrayList의 내부 구현이 기본 개체 배열을 기반으로 한다는 것입니다. 따라서 get 메서드를 사용하여 목록의 모든 요소에 액세스할 때(임의 액세스) LinkedList보다 빠릅니다. LinkedList의 get 메소드는 목록의 한쪽 끝에서 다른 쪽 끝까지 순서대로 확인합니다. LinkedList의 경우 목록의 특정 요소에 액세스하는 더 빠른 방법은 없습니다.
큰 목록이 있고 그 안에 있는 요소가 정렬되어 있다고 가정합니다. 이 목록은 ArrayList 유형 또는 LinkedList 유형일 수 있습니다. 이제 이 목록에 대해 비교 목록을 수행합니다. ArrayList 및 LinkedList의 쿼리 속도는 다음과 같습니다. 다음 프로그램을 참조하세요:
LinkedList 소비 시간: 2596
이 결과는 고정되어 있지 않지만 기본적으로 ArrayList의 시간은 LinkedList의 시간보다 훨씬 적습니다. 따라서 이 경우에는 LinkedList를 사용하면 안 됩니다. 이진 검색 방법은 무작위 액세스(randomaccess) 전략을 사용하며 LinkedList는 빠른 무작위 액세스를 지원하지 않습니다. LinkedList에 대한 무작위 액세스에 소요되는 시간은 목록의 크기에 비례합니다. 이에 따라 ArrayList에서 임의 액세스에 소요되는 시간은 고정되어 있습니다.
이것은 ArrayList가 LinkedList보다 항상 더 나은 성능을 발휘한다는 것을 의미합니까? 이것이 반드시 사실인 것은 아닙니다. 어떤 경우에는 LinkedList가 ArrayList보다 더 나은 성능을 발휘하고 일부 알고리즘은 LinkedList에서 구현될 때 더 효율적입니다. 예를 들어 Collections.reverse 메서드를 사용하여 목록을 반대로 하면 성능이 더 좋습니다.
이러한 예를 살펴보세요. 목록이 있고 목록에 대해 많은 수의 삽입 및 삭제 작업을 수행하려는 경우 이 경우 LinkedList가 더 나은 선택입니다. 목록의 시작 부분에 요소를 반복적으로 삽입하는 다음 극단적인 예를 생각해 보십시오.
현재 내 출력은 다음과 같습니다. ArrayList는 2463을 사용합니다.
LinkedList 소요 시간: 15
이는 이전 예제의 결과와 완전히 반대입니다. ArrayList의 시작 부분에 요소가 추가되면 기존 요소가 모두 뒤로 이동하므로 데이터 이동 및 복사의 오버헤드가 발생합니다. 이와 대조적으로 LinkedList의 시작 부분에 요소를 추가하면 요소에 레코드가 할당되고 두 링크가 조정됩니다. LinkedList의 시작 부분에 요소를 추가하는 비용은 고정되어 있는 반면 ArrayList의 시작 부분에 요소를 추가하는 비용은 ArrayList의 크기에 비례합니다.
둘. 공간 복잡도
LinkedList에는 다음과 같이 정의된 비공개 내부 클래스가 있습니다.
개인 정적 클래스 항목 {
개체 요소;
다음 항목;
이전 항목;
}
각 항목 개체는 목록의 요소뿐만 아니라 LinkedList의 이전 요소와 다음 요소도 참조합니다. 1000개의 요소가 있는 LinkedList 개체에는 1000개의 Entry 개체가 서로 연결되어 있으며 각 개체는 목록의 요소에 해당합니다. 이 경우 LinkedList 구조에는 1000개의 Entity 개체에 대한 관련 정보를 저장해야 하므로 공간 오버헤드가 많이 발생합니다.
ArrayList는 내장 배열을 사용하여 요소를 저장합니다. 이 배열의 시작 용량은 10입니다. 배열을 늘려야 할 경우 다음 공식에 따라 새 용량을 얻습니다. 새 용량 = (기존 용량*3)/2+ 1, 즉 용량은 매번 약 50%씩 증가합니다. 즉, 요소 수가 많은 ArrayList 개체가 있으면 결국 공간 낭비가 많아지게 됩니다. 이러한 낭비는 ArrayList 작동 방식으로 인해 발생합니다. 새 요소를 저장할 공간이 충분하지 않으면 새 요소를 추가할 수 있도록 배열을 다시 할당해야 합니다. 어레이를 재할당하면 성능이 크게 저하됩니다. ArrayList에 포함될 요소 수를 알고 있으면 생성자를 통해 용량을 지정할 수 있습니다. ArrayList가 할당된 후 낭비되는 공간을 제거하기 위해 TrimToSize 메서드를 사용할 수도 있습니다.
삼. 요약
ArrayList와 LinkedList는 각각 성능 측면에서 장점과 단점이 있으며, 일반적으로 다음과 같이 설명할 수 있습니다.
성능 요약:
| - | 추가() 작업 | 삭제() 작업 | 삽입 작업 | 인덱스 값 연산 | 반복자 값 연산 |
|---|---|---|---|---|---|
| 배열 목록/벡터/스택 | 좋은 | 차이점 | 차이점 | 훌륭한 | 훌륭한 |
| 링크드리스트 | 좋은 | 좋은 | 좋은 | 차이점 | 훌륭한 |
1. ArrayList와 LinkedList 모두 목록 끝에 요소를 추가하는 비용은 고정되어 있습니다. ArrayList의 경우 주로 내부 배열에 항목을 추가하여 추가된 요소를 가리키며 이로 인해 때때로 배열이 재할당될 수 있습니다. LinkedList의 경우 이 오버헤드는 균일하며 내부 Entry 개체를 할당합니다.
2. ArrayList 중간에 요소를 삽입하거나 삭제하면 목록의 나머지 요소가 이동되는 반면 LinkedList 중간에 요소를 삽입하거나 삭제하면 비용이 고정됩니다.
3． LinkedList는 효율적인 임의 요소 액세스를 지원하지 않습니다.
4． ArrayList의 공간 낭비는 주로 목록의 끝 부분에 일정량의 공간을 확보하는 데 반영되는 반면, LinkedList의 공간 소비는 각 요소가 상당한 양의 공간을 소비해야 한다는 점에서 반영됩니다.
이는 다음과 같이 말할 수 있습니다. 작업이 데이터 열의 앞이나 중간이 아닌 뒤에 데이터를 추가하는 것이고 요소에 무작위로 액세스해야 하는 경우, 작업이 데이터 열 앞에 있을 때 ArrayList를 사용하면 더 나은 성능을 제공할 수 있습니다. 데이터의 열 중간에 데이터를 추가하거나 삭제하고, 요소에 순서대로 접근하려면 LinkedList를 사용해야 합니다.
Java에서 ArrayList와 List의 차이점
목록 모음
목록은 Collection 인터페이스에서 상속됩니다. List는 순서가 지정된 컬렉션입니다. List에 포함된 요소는 인덱스(순서 번호: 컬렉션에 포함된 요소의 위치 정보)를 기준으로 가져오거나 삭제하거나 삽입할 수 있습니다.
Set 컬렉션과 달리 List는 중복 요소를 허용합니다. e1.equals(e2)의 조건을 충족하는 e1 및 e2 객체 요소의 경우 List 컬렉션에 동시에 존재할 수 있습니다. 물론 중복 요소를 허용하지 않는 List 구현 클래스도 있습니다.
동시에 List는 ListIterator 인터페이스 객체를 반환하는 listIterator() 메서드도 제공합니다. Iterator 인터페이스와 비교하면 ListIterator는 요소 추가, 삭제 및 설정을 위한 메서드를 추가하고 앞으로 또는 뒤로 이동할 수도 있습니다.
목록과 컬렉션의 관계:
java.util.Collection[I]
+--java.util.List[I]
+--java.util.ArrayList [C]
+--java.util.LinkedList [C]
+--java.util.Vector [C]
+--java.util.Stack [C]
List 인터페이스의 구현 클래스에는 주로 ArrayList, LinkedList, Vector, Stack 등이 포함됩니다.
아버지와 아들의 관계.
List는 인터페이스이고 ArrayList는 이 인터페이스를 상속하여 구현합니다.
저는 주로 ArrayList를 사용하는데, List를 사용한 적이 없습니다. 다음과 같이 사용할 수 있습니다. List list = new ArrayList();
컬렉션 인터페이스
컬렉션은 가장 기본적인 컬렉션 인터페이스입니다. 컬렉션은 개체 집합, 즉 컬렉션의 요소를 나타냅니다. 일부 컬렉션은 동일한 요소를 허용하지만 다른 컬렉션은 허용하지 않습니다. 어떤 종류는 있고 다른 것들은 그렇지 않습니다. Java SDK는 Collection에서 직접 상속되는 클래스를 제공하지 않습니다. Java SDK에서 제공하는 클래스는 모두 List 및 Set과 같이 Collection에서 상속되는 "하위 인터페이스"입니다.
Collection 인터페이스를 구현하는 모든 클래스는 두 가지 표준 생성자, 즉 빈 컬렉션을 생성하기 위한 매개 변수 없는 생성자와 새 컬렉션을 생성하기 위한 컬렉션 매개 변수 생성자를 제공해야 합니다. 입력 컬렉션에는 동일한 요소가 있습니다. 후자의 생성자를 사용하면 사용자가 컬렉션을 복사할 수 있습니다.
컬렉션의 각 요소를 반복하는 방법은 무엇입니까? Collection의 실제 유형에 관계없이 Collection의 각 요소에 하나씩 액세스하는 데 사용할 수 있는 반복자를 반환하는 iterator() 메서드를 지원합니다. 일반적인 사용법은 다음과 같습니다.
Iterator it = collection.iterator(); // 반복자를 가져옵니다.
while(it.hasNext()) {
Object obj = it.next(); // 다음 요소를 가져옵니다.
}
Collection 인터페이스에서 파생된 두 가지 인터페이스는 List와 Set입니다.
목록 인터페이스:
목록은 순서가 지정된 컬렉션입니다. 이 인터페이스를 사용하면 각 요소의 삽입 위치를 정확하게 제어할 수 있습니다. 사용자는 Java 배열과 유사한 인덱스(배열 첨자와 유사한 목록의 요소 위치)를 사용하여 목록의 요소에 액세스할 수 있습니다.
아래에 언급된 Set과 달리 List는 동일한 요소를 허용합니다.
Collection 인터페이스에 필요한 iterator() 메소드 외에도 List는 ListIterator 인터페이스를 반환하는 listIterator() 메소드도 제공합니다. 이는 표준 Iterator 인터페이스와 비교하여 ListIterator에는 추가가 가능한 add() 및 기타 메소드가 더 있습니다. 요소를 삭제하고 설정하며 앞으로 또는 뒤로 이동합니다.
List 인터페이스를 구현하는 일반적인 클래스는 LinkedList, ArrayList, Vector 및 Stack입니다.
링크드리스트 클래스
LinkedList는 List 인터페이스를 구현하고 null 요소를 허용합니다. 또한 LinkedList는 LinkedList의 헤드 또는 테일에 추가 가져오기, 제거 및 삽입 메서드를 제공합니다. 이러한 작업을 통해 LinkedList를 스택, 큐 또는 데크로 사용할 수 있습니다.
LinkedList에는 동기화된 메서드가 없습니다. 여러 스레드가 동시에 List에 액세스하는 경우 액세스 동기화를 자체적으로 구현해야 합니다. 한 가지 해결 방법은 목록을 생성할 때 동기화된 목록을 구성하는 것입니다.
목록 목록 = Collections.synchronizedList(new LinkedList(...));
ArrayList 클래스
ArrayList는 가변 크기 배열을 구현합니다. null을 포함한 모든 요소를 허용합니다. ArrayList가 동기화되지 않았습니다.
size, isEmpty, get 및 set 메소드의 실행 시간은 일정합니다. 그러나 add 메서드의 비용은 상각 상수이며 n 요소를 추가하려면 O(n) 시간이 필요합니다. 다른 방법에는 선형 실행 시간이 있습니다.
각 ArrayList 인스턴스에는 요소를 저장하는 데 사용되는 배열의 크기인 용량(Capacity)이 있습니다. 이 용량은 새 요소가 추가됨에 따라 자동으로 증가하지만 증가 알고리즘은 정의되지 않습니다. 많은 수의 요소를 삽입해야 하는 경우 삽입 전에 verifyCapacity 메소드를 호출하여 ArrayList의 용량을 늘려 삽입 효율성을 높일 수 있습니다.
LinkedList와 마찬가지로 ArrayList도 동기화되지 않습니다.
요약: 스택, 큐 등의 작업이 포함된 경우 List를 사용하는 것이 좋습니다. 요소를 빠르게 삽입하고 삭제해야 하는 경우에는 LinkedList를 사용하는 것이 좋습니다. 요소에 대한 빠른 임의 액세스가 필요한 경우 ArrayList를 사용하는 것이 좋습니다.
ArrayList 대신 List를 반환하는 등 실제 유형이 아닌 인터페이스를 반환해 보세요. 그러면 나중에 ArrayList를 LinkedList로 바꿔야 하는 경우 클라이언트 코드를 변경할 필요가 없습니다. 이것은 추상화를 위한 프로그래밍입니다.