1. 역사LinkedList
Java에는 C++ 언어에서 상속된 또 다른 컬렉션 클래스 Java가 있습니다. 이것은 LinkedList
"연결된 목록"을 구현하는 클래스입니다.
겉으로 보기에 a는 LinkedList
와 동일하게 보입니다 ArrayList
. 클래스 LinkedList
에는 클래스와 동일한 메서드가 모두 있습니다 ArrayList
. LinkedList
원칙적으로 an 대신 항상 a를 사용할 수 ArrayList
있으며 모든 것이 작동합니다.
그렇다면 다른 목록 클래스가 필요한 이유는 무엇입니까?
대답은 클래스의 내부 구조와 관련이 있습니다 LinkedList
. 배열 대신 이중 연결 목록을 사용합니다 . 그것이 무엇인지 잠시 후에 설명하겠습니다.
클래스 LinkedList
의 다른 내부 구조로 인해 목록 중간에 요소를 삽입하는 것이 가장 빠릅니다.
인터넷에서 종종 ArrayList
및 LinkedList
클래스의 비교를 찾을 수 있습니다.
작업 | 방법 | 배열목록 | LinkedList |
---|---|---|---|
요소 추가 |
|
빠른 | 매우 빠름 |
요소 삽입 |
|
느린 | 매우 빠름 |
요소 가져오기 |
|
매우 빠름 | 느린 |
요소 설정 |
|
매우 빠름 | 느린 |
요소 제거 |
|
느린 | 매우 빠름 |
모든 것이 충분히 명확해 보입니다. 목록에 요소를 자주 삽입해야 하는 경우 LinkedList
; 드물다면 ArrayList를 사용하십시오. 하지만 현실은 조금 다릅니다.
2. 아무도 사용하지 않는다LinkedList
아무도 사용하지 않습니다 LinkedList
.
수업 의 저자조차도 LinkedList
최근 트윗했습니다. "실제로 사용하는 사람이 있습니까 LinkedList
? 내가 썼고 사용하지 않습니다."
그래서 거래가 뭐야?
첫째, 클래스 ArrayList
는 요소를 목록 중간에 매우 빠르게 삽입할 수 있게 되었습니다. 목록 중간에 요소를 삽입할 때 삽입 지점 이후의 모든 요소를 목록의 끝으로 1씩 이동해야 합니다. 예전에는 시간이 걸렸습니다.
그러나 이제 모든 것이 바뀌었습니다. 배열의 모든 요소는 동일한 메모리 블록에서 서로 가까이 있으므로 요소를 이동하는 작업은 매우 빠른 저수준 명령으로 수행됩니다 .System.arraycopy()
또한 오늘날의 프로세서에는 일반적으로 전체 배열을 저장할 수 있는 큰 캐시가 있어 배열 요소를 메모리가 아닌 캐시 내부로 이동할 수 있습니다. 백만 개의 요소가 1밀리초 안에 쉽게 이동됩니다.
둘째, 반복자를 사용하여 요소를 삽입하면 클래스에서 요소를 빠르게 삽입할 수 있습니다 . LinkedList
반복자를 사용하여 a를 통과 LinkedList
하고 지속적으로 새 요소를 삽입(또는 기존 요소를 제거)하면 작업이 매우 빠릅니다.
LinkedList
루프 내의 개체 에 단순히 요소를 추가하는 경우 각각의 빠른 삽입 작업에는 느린 "요소 가져오기" 작업이 수반됩니다.
현실은 이것에 훨씬 더 가깝습니다.
작업 | 방법 | 배열목록 | LinkedList |
---|---|---|---|
요소 추가 |
|
빠른 | 매우 빠름 |
요소 삽입 |
|
느린 | 아주 느린 |
요소 가져오기 |
|
매우 빠름 | 아주 느린 |
요소 설정 |
|
매우 빠름 | 아주 느린 |
요소 제거 |
|
느린 | 아주 느린 |
반복자를 사용하여 삽입 |
|
느린 | 매우 빠름 |
반복자를 사용하여 제거 |
|
느린 | 매우 빠름 |
LinkedList
이렇게 느린 작업 에서 요소를 가져오는 이유는 무엇입니까 ?
가 어떻게 구성되어 있는지 조금 알게 된 후에 이 질문에 대답할 수 있습니다 LinkedList
.
3. LinkedList
구성 방법
LinkedList
와 내부 구조가 다릅니다 ArrayList
. 요소를 저장하기 위한 내부 배열이 없습니다. 대신 이중 잉크 목록 이라는 데이터 구조를 사용합니다 .
이중 연결 목록의 각 요소는 이전 요소와 다음 요소에 대한 참조를 저장합니다. 마치 상점에 줄을 서 있는 것과 비슷합니다. 저마다 앞에 서 있는 사람과 뒤에 서 있는 사람을 기억합니다.
이러한 목록은 메모리에서 다음과 같이 표시됩니다.
머리와 꼬리(배경이 회색인 셀)는 개체 에 대한 참조를 저장하는 first
및 변수입니다 .last
Node
중간에는 Node
개체 체인(변수가 아닌 개체)이 있습니다. 각각은 세 개의 필드로 구성됩니다.
prev
— 이전 객체(노란색 배경의 셀) 에 대한 참조 (링크)를 저장합니다.Node
value
— 목록의 이 요소 값을 저장합니다(배경이 녹색인 셀).next
— 다음 개체(파란색 배경의 셀) 에 대한 참조 (링크)를 저장합니다.Node
두 번째 객체(주소 F24)는 첫 번째 객체의 경우 다음( )이고 세 번째 객체의 경우 next
이전( )입니다. prev
세 번째 개체의 노란색 필드에는 주소 F24가 포함되고 첫 번째 개체의 파란색 필드에는 주소 F24가 포함됩니다.
첫 번째 및 세 번째 개체의 화살표는 동일한 두 번째 개체를 가리킵니다. 따라서 이렇게 화살표를 그리는 것이 더 정확할 것입니다.
4. 연결된 목록에 요소 삽입
이렇게 줄을 선 사람을 추가하려면 나란히 서 있는 두 사람의 허락을 받기만 하면 됩니다. 첫 번째 사람은 신인을 '내 뒤에 있는 사람'으로 기억하고, 두 번째 사람은 그들을 '내 앞에 있는 사람'으로 기억한다.
인접한 두 개체의 참조를 변경하기만 하면 됩니다.
두 번째 및 세 번째 개체의 참조를 변경하여 목록에 새 항목을 추가했습니다. 새 개체는 이전 두 번째 개체의 다음 개체이고 이전 세 번째 개체의 이전 개체입니다. 물론 새 개체 자체는 올바른 참조를 저장해야 합니다. 이전 개체는 이전 두 번째 개체이고 다음 개체는 이전 세 번째 개체입니다.
요소 제거는 훨씬 더 쉽습니다. 예를 들어 목록에서 100번째 개체를 제거하려면 99번째 개체의 필드를 변경하여 101번째 개체를 next
가리키도록 하고 prev
101번째 개체의 필드를 변경하기만 하면 됩니다. 개체가 99번째를 가리키도록 합니다. 그게 다야.
하지만 100번째 개체를 얻는 것은 그리 쉬운 일이 아닙니다.
5. 목록에서 요소 제거
연결된 목록의 100번째 요소를 가져오려면 다음을 수행해야 합니다.
first
첫 번째 개체 가져오기: 개체 의 변수를 사용하여 이 작업을 수행합니다 LinkedList
. 첫 번째 개체의 필드 next
는 두 번째 개체에 대한 참조를 저장합니다. 그것이 우리가 두 번째 객체를 얻는 방법입니다. 두 번째 개체에는 세 번째 개체에 대한 참조가 있습니다.
100번째 개체에 대한 참조를 가져와야 하는 경우 모든 개체를 1번째부터 100번째까지 순차적으로 이동해야 합니다. 그리고 목록에서 백만 번째 요소가 필요한 경우 백만 개가 넘는 개체를 차례로 반복해야 합니다!
그리고 이러한 개체가 다른 시간에 목록에 추가된 경우 메모리의 다른 부분에 위치하게 되며 동시에 프로세서의 캐시에 저장되지 않을 수 있습니다. 즉, 연결된 목록의 요소를 반복하는 것이 느릴 뿐만 아니라 매우 느립니다.
그것이 우리가 다루는 것입니다.
그렇다면 왜 우리는 이 느린 LinkedList
작동 방식을 가르쳐야 할까요?
글쎄 , 취업 면접 중에 LinkedList
당신ArrayList
은 . 분명히.