Java의 ArrayList를 통해 LinkedList를 사용하는 경우는 언제입니까?
질문
나는 항상 단순히 사용하기 만하면됩니다.
List<String> names = new ArrayList<>();
인터페이스를 휴대 성의 유형 이름으로 사용하므로 문제를 묻는 메시지가 표시되면 코드를 재 작업 할 수 있습니다.
언제 LinkedList가 ArrayList를 통해 사용되어야하며 그 반대의 경우는 무엇입니까?
답변
Summary ArrayDeque가있는 ArrayList가 LinkedList보다 많은 사용 사례에서 바람직합니다.확실하지 않은 경우 - ArrayList로 시작하십시오.
ArrayList에서 요소를 액세스하는 ArrayList의 TLDR은 일정한 시간을 취하고 요소를 추가하는 것은 O (n) 시간 [최악의 경우]를 취합니다.LinkedList에서 요소를 추가하는 것은 o (n) 시간을 가져 와서 액세스 o (n) 시간이 걸리지 만 LinkedList는 ArrayList보다 더 많은 메모리를 사용합니다.
LinkedList 및 ArrayList는 목록 인터페이스의 두 가지 다른 구현입니다.LinkedList는 이중 연결된 목록으로 구현합니다.ArrayList는 동적으로 다시 조정 된 배열로 구현합니다.
표준 링크 된 목록 및 배열 작업과 마찬가지로 다양한 방법으로 다양한 알고리즘 런타임이 있습니다.
linkedlist
get (int index)은 o (n) (n / 4 단계의 평균값)이지만 index = 0 또는 index = list.size () - 1 (이 경우 getFirst를 사용할 수 있습니다).)와 getlast ()).linkedlist
참고 : 많은 작업은 평균적으로 N / 4 단계, 최상의 경우 (예 : index = 0)에서 일정한 단계 수, 최악의 경우 n / 2 단계 (목록 중)
ArrayList
get (int index)는 o (1)입니다.ArrayList
참고 : 많은 작업의 대부분은 평균적으로 N / 2 단계, 최상의 경우 최악의 경우 n 단계 (목록 시작)의 n 단계에서 N / 2 단계가 필요합니다.
linkedlist
ArrayList
따라서 수행하려는 작업에 따라 구현을 선택해야합니다.어느 종류의 목록을 반복하는 것은 실질적으로 똑같이 싸다.(ArrayList를 통해 반복하는 것은 기술적으로 더 빠르지 만, 실제로 성능에 민감한 일을하고 있지 않으면 이것에 대해 걱정하지 않아야합니다. 둘 다 상수입니다.)
LinkedList를 사용하는 주된 이점은 기존 반복기를 다시 사용하여 요소를 삽입하고 제거 할 때 발생합니다.이러한 작업은 목록을 로컬로 변경하여 O (1)에서 수행 할 수 있습니다.배열 목록에서 배열의 나머지 부분은 이동해야합니다 (즉, 복사).다른 쪽에서 LinkedLest를 찾는 것은 O (n) (n) (n / 2 단계)의 링크를 최악의 경우, 배열 목록에서는 원하는 위치를 수학적으로 계산하여 O (1)에서 액세스 할 수 있습니다.
LinkedList를 사용하는 또 다른 이점은 목록의 머리에서 추가 또는 제거 할 때 발생할 때 발생합니다.이 작업은 O (1)이므로 ArrayList의 o (n)입니다.ArrayDeque는 머리에서 추가 및 제거하기위한 LinkedList에 대한 좋은 대안이 될 수 있지만 목록이 아닙니다.
또한 목록이 큰 경우 메모리 사용량도 다르게 유지하십시오.LinkedList의 각 요소는 다음과 이전 요소에 대한 포인터가 저장되므로 더 많은 오버 헤드가 있습니다.ArrayLists는이 오버 헤드가 없습니다.그러나 ArrayLists는 요소가 실제로 추가되었는지 여부에 관계없이 용량에 대해 할당 된 많은 메모리를 차지합니다.
ArrayList의 기본 초기 용량은 꽤 작습니다 (Java 1.4 - 1.8에서 10).그러나 기본 구현이 배열이기 때문에 많은 요소를 추가하면 배열을 크기가 조정해야합니다.크기 조정 비용이 많이 들지 않으려면 많은 요소를 추가하려고 할 때자를 더 높은 초기 용량으로 ArrayList를 구성하십시오.
데이터 구조의 관점이 두 개의 구조를 이해하기 위해 사용되는 경우, LINKEDLIST는 기본적으로 헤드 노드를 포함하는 순차적 데이터 구조입니다.노드는 두 가지 구성 요소의 래퍼입니다. T [Accepted Through Through]의 값과 연결된 노드에 대한 다른 참조의 값.따라서 재귀 데이터 구조 (노드가 다른 노드 등)를 포함하는 노드가 포함되어 있습니다.요소 추가는 위에 명시된대로 LinkedList에서 LinkedLeas에서 선형 시간을 차지합니다.
ArrayList는 재배 가능 배열입니다.그것은 정규 배열과 같습니다.후드 아래에 요소가 추가되고 ArrayList가 이미 용량으로 가득 차면 이전 크기보다 큰 크기가있는 다른 배열을 만듭니다.그런 다음 요소를 이전 어레이에서 새 하나로 복사하고 추가 할 요소도 지정된 인덱스에 배치됩니다.
답변
그럼에도 불구하고, 아무도 링크리스트가 ArrayList보다 "Lots More"라는 일반적인 합의 외에이 각 목록의 메모리 풋 프린트를 해결 한 것으로 보이는 것으로 보이지 않으므로 두 목록이 n null 참조를 얼마나 많이 가져 오는지 정확히 보여주기 위해 몇 가지 숫자가 숫자를 보여주었습니다....에
참고 문헌은 상대 시스템에서 32 개 또는 64 비트 (null) 중 하나이기 때문에 32 개 및 64 비트 LinkLists 및 ArrayLists에 대해 4 세트의 데이터 세트가 포함되어 있습니다.
참고 : ArrayList 행에 표시된 크기는 트리밍 된 목록입니다. 실제로 ArrayList의 백업 배열의 용량은 일반적으로 현재 요소 수보다 크다.
참고 2 : (Appee Equey Equie) CompressEdoops는 이제 JDK6 중간에서 기본값이므로 64 비트 컴퓨터의 값은 기본적으로 32 비트 대응 부분과 일치하지 않으면 특별히 꺼집니다.
결과는 LinkedList가 Arraylist, 특히 매우 높은 요소 수를 갖는 훨씬 더 훨씬 더 훨씬 더 많은 것임을 분명히 보여줍니다.메모리가 요인 인 경우 LinkedLists를 조정하십시오.
내가 사용한 수식은 내가 잘못한 일을했는지 알려주고 나는 그것을 고칠 것이다.'B'는 32 또는 64 비트 시스템의 경우 4 또는 8이며 'n'은 요소 수입니다.참고 Mods의 이유는 Java의 모든 객체가 모두 사용되었는지 여부에 관계없이 8 바이트 공간을 여러 번 가져올 수 있기 때문입니다.
ArrayList :
ArrayList 오브젝트 헤더 + 크기 정수 + modcount 정수 + 배열 참조 + (어레이 oject 헤더 + b * n) + mod (배열 orject, 8) + mod (ArrayList 객체, 8) == 8 + 4 + 4 + B + (12+ B * N) + 모드 (12 + B * N, 8) + 모드 (8 + 4 + 4 + B + (12 + B * N) + 모드 (12 + B * N, 8), 8)
LinkedList :
LinkedList 객체 헤더 + 크기 정수 + modcount 정수 + 바닥 글 +에 대한 참조 + (노드 오브젝트 오버 헤드 + 이전 요소 + 요소 +에 대한 참조 +에 대한 참조) * n) + mod (노드 오브젝트, 8) * n+ 모드 (LinkedList Object, 8) == 8 + 4 + 4 + 2 * B + (8 + 3 * B) * N + MOD (8 + 3 * B, 8) * N + MOD (8 + 4 + 4+ 2 * B + (8 + 3 * B) * N + MOD (8 + 3 * B, 8) * N, 8)
답변
ArrayList는 원하는 것입니다.LinkedList는 거의 항상 (성능) 버그입니다.
왜 LinkedList가 짜증나는 이유 :
그것은 많은 작은 메모리 객체를 사용하므로 프로세스 전반에 걸쳐 성능에 영향을 미칩니다. 많은 작은 물체가 캐시 지역에 좋지 않습니다. 임의의 인덱싱 된 동작은 순회, 즉 O (n) 성능을 갖는다.이것은 ArrayList가 사용 된 경우보다 알고리즘 O (n) 느리게 알고리즘을 선도하는 소스 코드에서는 분명하지 않습니다. 좋은 성능을 얻는 것은 까다로운 것입니다. Big-O 성능이 ArrayList와 동일하더라도 어쨌든 상당히 느리게 될 것입니다. 그것은 아마도 잘못된 선택이기 때문에 소스에서 linkedlist를 보려면 jarring입니다.
답변
Algorithm ArrayList LinkedList
seek front O(1) O(1)
seek back O(1) O(1)
seek to index O(1) O(N)
insert at front O(N) O(1)
insert at back O(1) O(1)
insert after an item O(N) O(1)
알고리즘 : Big-Oh Notation (아카이브)
ArrayLists는 한 번만 읽기 - 많은 또는 부록기를 쓰는 것이 좋지만 앞이나 중간에서 추가 / 제거에 좋지 않습니다.
답변
약 10 년 동안 매우 큰 스케일 SOA 웹 서비스에서 운영 성과 공학을 수행 한 사람으로서, ArrayList를 통해 LinkedList의 동작을 선호합니다.LinkedList의 정상 상태 처리량은 더 나 빠졌으므로 더 많은 하드웨어를 구입하게 될 수 있습니다. 압력하에있는 ArrayList의 동작은 클러스터의 어레이에서 앱을 펼치고 큰 배열 크기가 반응력이 부족해질 수 있습니다.앱과 정전에서 압력을받는 동안, 그것은 치명적인 행동입니다.
마찬가지로 기본 처리 초상화 가비지 수집기에서 앱에서 더 나은 처리량을 얻을 수 있지만 10GB 힙이있는 Java 앱을 얻으면 SOA 앱의 시간 초과 및 실패를 일으키는 전체 GC에서 25 초 동안 앱을 잠그는 것입니다.너무 자주 발생하면 SLA를 불어 넣습니다.CMS 수집기가 더 많은 자원을 차지하고 동일한 원시 처리량을 얻지 못하지만, 더 예측 가능하고 더 작은 대기 시간이기 때문에 훨씬 더 나은 선택입니다.
ArrayList는 성능이 처리량으로 의미가 있고 대기 시간을 무시할 수있는 모든 것이 더 나은 성능에 대한 더 나은 선택입니다.내 직업에서의 경험에서 나는 최악의 대기 시간을 무시할 수 없습니다.
업데이트 (2021 년 8 월 27 일, 10 년 후) :이 답변 (가장 역사적으로 upboted 답변)은 틀릴 수 있습니다 (아래의 의견에 설명 된 이유로). ArrayList가 메모리 읽기를 최적화하고 캐시 라인 및 TLB 누락을 최소화 할 수 있도록 추가하고 싶습니다. 배열이 경계를 지나갈 때 배열이 성장할 수있는 오버 헤드는 비교하여 중요하지 않을 수 있습니다 (효율적인 CPU 작업으로 수행 할 수 있습니다. ~의 이 답변은 또한 하드웨어 트렌드가 주어지면 시간이 지남에 따라 악화됩니다. LinkedList가 의미가있는 유일한 상황은 당신이 GB 크기가 될 수있는 것 중 하나가 성장할 수있는 수천 명의 목록을 가지고있는 곳이지만, 목록의 배정 시간에 좋은 추측이없고 그 (것)들을 설정할 수있는 곳이었습니다. GB 크기로 모두 힙을 날려 버릴 것입니다. 그리고 그런 문제를 발견하면 솔루션이 무엇이든간에 Reengineering을 요구합니다 (그리고 나는 나 자신이 더미와 더미를 유지하기 때문에 나 자신이 더미와 더미를 유지하기 때문에 실현하는 것을 싫어합니다. 원래의 디자인이 단순히 활주로에서 벗어나 척해서 척해질 필요가있는 곳의 아주 좋은 경우). 나는 아직도 수십 년간의 가난한 의견을 남겨두고 있기 때문에 당신이 읽을 수 있도록 간단하고 논리적이며 꽤 잘못되었습니다.
답변
그래, 알아, 이것은 고대의 질문이지만, 나는 내 두 센트를 던질거야 :
LinkedList는 거의 항상 잘못된 선택, 성능이 현명합니다.LinkedList가 호출되는 매우 구체적인 알고리즘이 있지만 매우 드뭅니다. 매우 드물게 알고리즘은 일반적으로 목록의 중간에 요소를 삽입하고 삭제할 수있는 LinkedList의 능력에 따라 상대적으로 빠르게 목록 중간에 요소를 삽입하고 삭제할 수있는 능력에 의존합니다.ListIterator.
LinkedList가 ArrayList : 대기열의 ourperforms : Queue의 일반적인 사용 사례가 하나 있습니다.그러나 LinkedList 대신에 목표가 성능이있는 경우 ArrayBlockingQueue를 사용하는 것도 고려해야합니다 (대기열 크기에서 상한을 결정할 수있는 경우, 모든 메모리를 최대한 활용할 수 있음) 또는이 CircularArrayList 구현을 할 여유가있을 수 있습니다....에(예, 그것은 2001 년부터 제출해야 할 필요가 있지만 최근의 JVM에서 지금 당사에서 인용 한 것에 비교할 수있는 성능 비율을 얻을 수 있습니다)
출처:https://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist-in-java
최근댓글