거의 모든 Java 인터뷰에서 묻는 질문: ArrayList와 LinkedList의 차이점에 대해 이야기합니다.

머리말

안녕하세요 여러분, 저는 여러분의 오랜 친구인 Qing Ge입니다. 여러분이 저를 그리워한다는 것을 알고 있어서 또 왔습니다.

인터뷰의 초점은 Java입니다. Java에 참여해 보신 적이 있으신가요? 인터뷰에 응한 모든 학생들이 이런 경험을 했을 거라 생각합니다. 면접관들이 이런 질문을 할 때, 단순히 "사용법을 아는" 수준에 머물기보다는 Java에서 일반적으로 사용되는 데이터 유형의 기본 구조를 연구했는지 여부를 확인하려는 경우가 많습니다. 그렇다면 어떻게 하면 면접 시 이 질문에 잘 대답하고 면접관을 만족시킬 수 있을까요?

이번 호에서는 Java 고주파 테스트 포인트ArrayList 및 LinkedList의 원리를 분석해 보세요. 도움이 되기를 바랍니다. ArrayList和LinkedList的原理进行分析，希望能帮助到你。

ArrayList和LinkedList简介

ArrayList底层是一个Object类型的数组，初始容量是10，支持动态扩容，扩容后的容量是当前容量的1.5倍，它的最大容量是 Integer.MAX_VALUE - 8（但是仍可以扩容到Integer.MAX_VALUE），对于空出的8位，目前的解释是避免一些机器内存溢出，减少出错几率。

LinkedList

ArrayList 및 LinkedList 소개

🎜 🎜🎜

ArrayList 코드 >하단 레이어는 초기 용량이 10인 객체형 배열이며, 확장 용량은 현재 용량의 1.5배입니다. 최대 용량은 Integer.MAX_VALUE - 8입니다(그러나 여전히 Integer.MAX_VALUE까지 확장 가능). ) , 비워진 8비트에 대한 현재 해석은 <code style="font-size: 14px;overflow-wrap: break-word;padding: 2px 4px;border-radius: 4px;margin-right: 2px;margin- 왼쪽: 2px;배경색상: rgba(27, 31, 35, 0.05);글꼴군: " operator mono consolas monaco menlo monospace break-all rgb>일부 시스템 메모리 오버플로를 방지하고 오류 가능성을 줄입니다. 🎜

LinkedList하단 레이어는 이중 연결 리스트입니다. 초기 용량은 0입니다. 용량을 확장하려면 노드를 포인터로 가리키기만 하면 됩니다. 🎜🎜🎜학생들이 면접 시 면접관에게 설명할 수 있도록 말로 표현 가능한 언어로 단순화하기 위해 여기에 소스 코드 보조 지침을 게시하지 않겠습니다. 관심 있는 학생들은 소스 코드를 확인하여 내부 구조와 방법을 확인할 수 있습니다. . 이 분야에 대한 이해를 깊게 하세요. 🎜

Difference

Query

• ArrayList는 요소의 저장이 정렬되어 있고 메모리에서 쿼리된 데이터의 위치를 ​​첨자를 통해 알 수 있기 때문에 임의 액세스에 매우 효율적입니다. index.주소는 빠르고 시간복잡도는 O(1); N).
• Insertion

ArrayList는 꼬리 삽입 시 시간 복잡도가 O(1)로 더 효율적이지만, 다른 위치에서는 삽입 효율성이 상대적으로 낮아 시간이 지남에 따라 많은 양의 데이터 이동이 필요합니다. O(n)의 복잡도

• LinkedList는 머리와 꼬리에 요소를 삽입하는 데 더 효율적이며 시간 복잡도는 O(1)입니다. 그러나 중간에 지정된 위치에 요소를 삽입하려면 다음이 필요합니다. 요소의 위치를 ​​먼저 찾은 다음 삽입하는 것은 복잡합니다.
• Delete

ArrayList에서 요소를 제거하려면 끝 노드를 제외하고 많은 데이터 이동이 필요하며 시간 복잡도는 O(n)입니다.

• LinkedList는 요소를 삭제하는 데 상대적으로 효율적입니다. 포인터의 포인팅만 변경하면 되지만, 요소를 삭제하려면 데이터 위치를 탐색하고 쿼리해야 하며 시간 복잡도는 O(n)입니다.
• 메모리 공간

ArrayList는 배열을 기반으로 구현됩니다. 용량은 확장할 때마다 고정되므로 공간의 일부는 마지막에 예약됩니다.

• LinkedList는 이중으로 구현됩니다. 연결된 목록이므로 각 노드는 데이터를 저장하는 것 외에도 이전 및 다음 노드의 포인터도 저장해야 하는데, 이는 약간의 공간을 차지합니다.
• 확장 메커니즘

ArrayList는 확장될 때마다 원래 배열의 요소를 새 배열에 복사해야 합니다.

• LinkedList는 연결된 목록이며 확장이 없습니다.

Sameness

스레드 안전

ArrayList 및 LinkedList는 모두 스레드에 안전하지 않으며 다중 스레드 환경에서 쉽게 더러운 읽기 문제를 일으킬 수 있습니다. Collections.synchronizedList() 메서드를 사용하여 스레드 안전성을 보장할 수 있습니다.

저장 기능

저장된 요소는 모두 정렬될 수 있습니다. 반복되고 새 요소가 목록 끝에 저장됩니다.

위 내용은 거의 모든 Java 인터뷰에서 묻는 질문: ArrayList와 LinkedList의 차이점에 대해 이야기합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!