LinkedList 컬렉션 소개

1. 역사LinkedList

Java에는 C++ 언어에서 상속된 또 다른 컬렉션 클래스 Java가 있습니다. 이것은 LinkedList"연결된 목록"을 구현하는 클래스입니다.

겉으로 보기에 a는 LinkedList와 동일하게 보입니다 ArrayList. 클래스 LinkedList에는 클래스와 동일한 메서드가 모두 있습니다 ArrayList. LinkedList원칙적으로 an 대신 항상 a를 사용할 수 ArrayList있으며 모든 것이 작동합니다.

그렇다면 다른 목록 클래스가 필요한 이유는 무엇입니까?

대답은 클래스의 내부 구조와 관련이 있습니다 LinkedList. 배열 대신 이중 연결 목록을 사용합니다 . 그것이 무엇인지 잠시 후에 설명하겠습니다.

클래스 LinkedList의 다른 내부 구조로 인해 목록 중간에 요소를 삽입하는 것이 가장 빠릅니다.

인터넷에서 종종 ArrayList및 LinkedList클래스의 비교를 찾을 수 있습니다.

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

모든 것이 충분히 명확해 보입니다. 목록에 요소를 자주 삽입해야 하는 경우 LinkedList; 드물다면 ArrayList를 사용하십시오. 하지만 현실은 조금 다릅니다.

2. 아무도 사용하지 않는다LinkedList

아무도 사용하지 않습니다 LinkedList.

수업 의 저자조차도 LinkedList최근 트윗했습니다. "실제로 사용하는 사람이 있습니까 LinkedList? 내가 썼고 사용하지 않습니다."

그래서 거래가 뭐야?

첫째, 클래스 ArrayList는 요소를 목록 중간에 매우 빠르게 삽입할 수 있게 되었습니다. 목록 중간에 요소를 삽입할 때 삽입 지점 이후의 모든 요소를 ​​목록의 끝으로 1씩 이동해야 합니다. 예전에는 시간이 걸렸습니다.

그러나 이제 모든 것이 바뀌었습니다. 배열의 모든 요소는 동일한 메모리 블록에서 서로 가까이 있으므로 요소를 이동하는 작업은 매우 빠른 저수준 명령으로 수행됩니다 .System.arraycopy()

또한 오늘날의 프로세서에는 일반적으로 전체 배열을 저장할 수 있는 큰 캐시가 있어 배열 요소를 메모리가 아닌 캐시 내부로 이동할 수 있습니다. 백만 개의 요소가 1밀리초 안에 쉽게 이동됩니다.

둘째, 반복자를 사용하여 요소를 삽입하면 클래스에서 요소를 빠르게 삽입할 수 있습니다 . LinkedList반복자를 사용하여 a를 통과 LinkedList하고 지속적으로 새 요소를 삽입(또는 기존 요소를 제거)하면 작업이 매우 빠릅니다.

LinkedList루프 내의 개체 에 단순히 요소를 추가하는 경우 각각의 빠른 삽입 작업에는 느린 "요소 가져오기" 작업이 수반됩니다.

현실은 이것에 훨씬 더 가깝습니다.

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

it.add(value)

it.remove()

LinkedList이렇게 느린 작업 에서 요소를 가져오는 이유는 무엇입니까 ?

가 어떻게 구성되어 있는지 조금 알게 된 후에 이 질문에 대답할 수 있습니다 LinkedList.

3. LinkedList구성 방법

LinkedList와 내부 구조가 다릅니다 ArrayList. 요소를 저장하기 위한 내부 배열이 없습니다. 대신 이중 잉크 목록 이라는 데이터 구조를 사용합니다 .

이중 연결 목록의 각 요소는 이전 요소와 다음 요소에 대한 참조를 저장합니다. 마치 상점에 줄을 서 있는 것과 비슷합니다. 저마다 앞에 서 있는 사람과 뒤에 서 있는 사람을 기억합니다.

이러한 목록은 메모리에서 다음과 같이 표시됩니다.

머리와 꼬리(배경이 회색인 셀)는 개체 에 대한 참조를 저장하는 first및 변수입니다 .lastNode

중간에는 Node개체 체인(변수가 아닌 개체)이 있습니다. 각각은 세 개의 필드로 구성됩니다.

• prev— 이전 객체(노란색 배경의 셀) 에 대한 참조 (링크)를 저장합니다.Node
• value— 목록의 이 요소 값을 저장합니다(배경이 녹색인 셀).
• next— 다음 개체(파란색 배경의 셀) 에 대한 참조 (링크)를 저장합니다.Node

두 번째 객체(주소 F24)는 첫 번째 객체의 경우 다음( )이고 세 번째 객체의 경우 next이전( )입니다. prev세 번째 개체의 노란색 필드에는 주소 F24가 포함되고 첫 번째 개체의 파란색 필드에는 주소 F24가 포함됩니다.

첫 번째 및 세 번째 개체의 화살표는 동일한 두 번째 개체를 가리킵니다. 따라서 이렇게 화살표를 그리는 것이 더 정확할 것입니다.

4. 연결된 목록에 요소 삽입

이렇게 줄을 선 사람을 추가하려면 나란히 서 있는 두 사람의 허락을 받기만 하면 됩니다. 첫 번째 사람은 신인을 '내 뒤에 있는 사람'으로 기억하고, 두 번째 사람은 그들을 '내 앞에 있는 사람'으로 기억한다.

인접한 두 개체의 참조를 변경하기만 하면 됩니다.

두 번째 및 세 번째 개체의 참조를 변경하여 목록에 새 항목을 추가했습니다. 새 개체는 이전 두 번째 개체의 다음 개체이고 이전 세 번째 개체의 이전 개체입니다. 물론 새 개체 자체는 올바른 참조를 저장해야 합니다. 이전 개체는 이전 두 번째 개체이고 다음 개체는 이전 세 번째 개체입니다.

요소 제거는 훨씬 더 쉽습니다. 예를 들어 목록에서 100번째 개체를 제거하려면 99번째 개체의 필드를 변경하여 101번째 개체를 next가리키도록 하고 prev101번째 개체의 필드를 변경하기만 하면 됩니다. 개체가 99번째를 가리키도록 합니다. 그게 다야.

하지만 100번째 개체를 얻는 것은 그리 쉬운 일이 아닙니다.

5. 목록에서 요소 제거

연결된 목록의 100번째 요소를 가져오려면 다음을 수행해야 합니다.

first첫 번째 개체 가져오기: 개체 의 변수를 사용하여 이 작업을 수행합니다 LinkedList. 첫 번째 개체의 필드 next는 두 번째 개체에 대한 참조를 저장합니다. 그것이 우리가 두 번째 객체를 얻는 방법입니다. 두 번째 개체에는 세 번째 개체에 대한 참조가 있습니다.

100번째 개체에 대한 참조를 가져와야 하는 경우 모든 개체를 1번째부터 100번째까지 순차적으로 이동해야 합니다. 그리고 목록에서 백만 번째 요소가 필요한 경우 백만 개가 넘는 개체를 차례로 반복해야 합니다!

그리고 이러한 개체가 다른 시간에 목록에 추가된 경우 메모리의 다른 부분에 위치하게 되며 동시에 프로세서의 캐시에 저장되지 않을 수 있습니다. 즉, 연결된 목록의 요소를 반복하는 것이 느릴 뿐만 아니라 매우 느립니다.

그것이 우리가 다루는 것입니다.

그렇다면 왜 우리는 이 느린 LinkedList작동 방식을 가르쳐야 할까요?

글쎄 , 취업 면접 중에 LinkedList당신ArrayList 은 . 분명히.