자바 ArrayList 대 LinkedList

1. 개요

컬렉션과 관련하여 Java 표준 라이브러리는 선택할 수있는 많은 옵션을 제공합니다. 이러한 옵션 중에는 ArrayListLinkedList 로 알려진 두 가지 유명한 List 구현이 있으며 각각 고유 한 속성과 사용 사례가 있습니다.

이 튜토리얼에서는이 두 가지가 실제로 어떻게 구현되는지 볼 것입니다. 그런 다음 각 응용 프로그램에 대해 서로 다른 응용 프로그램을 평가합니다.

2. ArrayList

내부적으로 ArrayList 는 배열을 사용하여 List 인터페이스 를 구현합니다 . 배열은 Java에서 고정 크기이므로 ArrayList 는 초기 용량이있는 배열을 만듭니다. 그 과정에서 기본 용량보다 더 많은 항목을 저장해야하는 경우 해당 어레이를 새롭고 더 넓은 어레이로 대체합니다.

속성을 더 잘 이해하기 위해 항목 추가, 인덱스로 하나씩 가져 오기 및 인덱스로 제거의 세 가지 주요 작업과 관련하여이 데이터 구조를 평가 해 보겠습니다.

2.1. 더하다

ArrayList를 만들 때 기본 용량 (현재 10)으로 백업 배열을 초기화합니다.

배열이 아직 가득 차지 않은 상태에서 새 항목을 추가하는 것은 해당 항목을 특정 배열 인덱스에 할당하는 것만 큼 간단합니다. 이 배열 인덱스는 실제로 목록에 추가하기 때문에 현재 배열 크기에 의해 결정됩니다.

backingArray[size] = newItem; size++;

따라서 최상의 경우 및 평균적인 경우 추가 작업의 시간 복잡도는 O (1) 이며 이는 매우 빠릅니다. 그러나 백업 배열이 가득 차면 추가 구현의 효율성이 떨어집니다.

새 항목을 추가하려면 먼저 더 많은 용량의 새 어레이를 초기화하고 기존 항목을 모두 새 어레이에 복사해야합니다. 현재 요소를 복사 한 후에 만 ​​새 항목을 추가 할 수 있습니다. 따라서 시간 복잡도는 n 개의 요소를 먼저 복사해야하므로 최악의 경우 O (n) 입니다 .

이론적으로 말하면, 새로운 요소를 추가하는 것은 상각 된 일정한 시간에 실행됩니다. 즉, n 개의 요소를 추가 하려면 O (n) 시간이 필요합니다 . 그러나 일부 단일 추가는 복사 오버 헤드로 인해 제대로 수행되지 않을 수 있습니다.

2.2. 색인으로 액세스

인덱스로 항목에 액세스하는 것은 ArrayList가 실제로 빛나는 곳입니다. 인덱스 i 에서 항목을 검색하려면 백업 배열에서 i 번째 인덱스에 있는 항목을 반환하면 됩니다. 결과적 으로 인덱스 연산에 의한 액세스의 시간 복잡도는 항상 O (1)입니다.

2.3. 색인으로 제거

ArrayList 에서 색인 6을 제거한다고 가정 해 보겠습니다. ArrayList는 백업 배열의 요소 15에 해당합니다.

원하는 요소를 삭제 된 것으로 표시 한 후 모든 요소를 ​​한 인덱스 뒤로 이동해야합니다. 분명히 배열의 시작 부분에 가까울수록 더 많은 요소를 이동해야합니다. 따라서 시간 복잡도는 최상의 경우 O (1) 이고 평균 및 최악의 경우 O (n) 입니다.

2.4. 응용 프로그램 및 제한 사항

일반적으로 ArrayListList 구현이 필요한 많은 개발자의 기본 선택입니다 . 사실 읽기 횟수가 쓰기 횟수보다 훨씬 많은 경우 실제로 현명한 선택 입니다.

때때로 우리는 똑같이 빈번한 읽기와 쓰기가 필요합니다. 가능한 최대 항목 수를 추정 한 경우에도 ArrayList 를 사용하는 것이 좋습니다 . 이 경우 초기 용량으로 ArrayList 를 초기화 할 수 있습니다 .

int possibleUpperBound = 10_000; List items = new ArrayList(possibleUpperBound);

이 추정은 불필요한 복사 및 배열 할당을 많이 방지 할 수 있습니다.

또한 배열은 Java에서 int 값으로 색인화됩니다 . 따라서 Java 배열 및 결과적으로 ArrayList에 232 개 이상의 요소 를 저장할 수 없습니다 .

3. LinkedList

LinkedList 는 이름에서 알 수 있듯이 연결된 노드 모음을 사용하여 요소를 저장하고 검색합니다 . 예를 들어 다음은 네 가지 요소를 추가 한 후 Java 구현이 어떻게 보이는지입니다.

각 노드는 두 개의 포인터를 유지합니다. 하나는 다음 요소를 가리키고 다른 하나는 이전 요소를 가리 킵니다. 이를 확장하면 이중 연결 목록에는 첫 번째 항목과 마지막 항목을 가리키는 두 개의 포인터가 있습니다.

다시, 동일한 기본 작업과 관련하여이 구현을 평가 해 보겠습니다.

3.1. 더하다

새 노드를 추가하려면 먼저 현재 마지막 노드를 새 노드에 연결해야합니다.

그런 다음 마지막 포인터를 업데이트하십시오.

이 두 작업 모두 사소하기 때문에 추가 작업의 시간 복잡도는 항상 O (1) 입니다.

3.2. 색인으로 액세스

LinkedListArrayList 와 달리 빠른 임의 액세스를 지원하지 않습니다. 따라서 인덱스로 요소를 찾으려면 목록의 일부를 수동으로 탐색 해야 합니다.

가장 좋은 경우, 요청 된 항목이 목록의 시작 또는 끝 근처에있을 때 시간 복잡도는 O (1) 만큼 빠릅니다 . 그러나 평균 및 최악의 시나리오에서는 많은 노드를 차례로 검사해야하므로 액세스 시간이 O (n)으로 끝날 수 있습니다 .

3.3. 색인으로 제거

항목을 제거하려면 먼저 요청 된 항목을 찾은 다음 목록에서 연결을 해제해야합니다 . 결과적으로 액세스 시간은 시간 복잡성을 결정합니다. 즉, 최상의 경우 O (1) , 평균 및 최악의 시나리오에서는 O (n) 입니다.

3.4. 응용

LinkedLists 는 추가 속도가 읽기 속도보다 훨씬 높을 때 더 적합합니다 .

또한 대부분의 경우 첫 번째 또는 마지막 요소를 원할 때 읽기가 많은 시나리오에서 사용할 수 있습니다. LinkedList 는 컬렉션의 양쪽 끝에 대한 효율적인 액세스를 지원 하는 Deque 인터페이스 도 구현 한다는 점을 언급 할 가치가 있습니다.

일반적으로 구현 차이점을 알고 있다면 특정 사용 사례에 대해 쉽게 선택할 수 있습니다.

예를 들어 목록과 같은 데이터 구조에 많은 시계열 이벤트를 저장한다고 가정 해 보겠습니다. 우리는 매초마다 많은 이벤트를 받게 될 것임을 알고 있습니다.

또한 모든 이벤트를 주기적으로 검사하고 통계를 제공해야합니다. 이 사용 사례의 경우 추가 속도가 읽기 속도보다 훨씬 높기 때문에 LinkedList 가 더 나은 선택입니다.

또한 모든 항목을 읽으므로 O (n) 상한을 이길 수 없습니다 .

4. 결론

이 튜토리얼에서는 먼저 Java에서 ArrayListLinkLists 를 구현 하는 방법을 살펴 보았습니다 .

또한 각각에 대해 서로 다른 사용 사례를 평가했습니다.