연결 목록 불연속 메모리

Question

지난 시험지에서 다음 질문에 대한 답을 찾는 데 어려움이 있습니다. 나는 설명을 바르게 평가할 것이다.

링크 된 목록은 인접하지 않은 메모리를 사용합니다. 이것은 무엇을 의미합니까?

Answer 1

인접하지 않음은 연결된 목록의 요소가 반드시 메모리의 인접한 위치에 있지 않음을 의미합니다. 이는 인접한 메모리를 사용하는 배열이나 배열 목록과는 다릅니다. 배열 및 배열 목록의 경우 연속적인 요소는 인접한 메모리 위치에도 있습니다.

Answer 2

목록의 각 노드는 메모리의 어느 위치 에나있을 수 있습니다. 이것은리스트를 연속적으로 저장되는 배열과 구별하는 한 가지입니다.

Answer 3

링크 된 목록은 링크를 사용하며 링크는 목록의 다음 요소를 가리키며이 링크는 메모리에 인접하지 않아도됩니다. 연결된 목록의 각 요소는 모든 메모리 위치에있을 수 있으며 링크를 사용하여 순차적으로 목록을 탐색 할 수 있습니다. 다른 쪽의 배열은 인접한 메모리 블록을 사용합니다. 즉, 모든 요소가 서로 인접 해 있음을 의미합니다.

Answer 4

이 경우 비 연속 메모리는 연결된 목록을 구성하는 노드에 할당 된 메모리 주소가 연속적이지 않다는 사실을 의미합니다. 이를 각 노드가 순차적으로 발생하는 기존 배열과 비교하십시오. 포인터가있는 언어 (C 계열 이상)에서는 색인 자체를 증가시키는 대신 인덱스를 나타내는 메모리 주소에 숫자를 추가하여 배열의 다음 색인에 액세스 할 수 있습니다. 여기서 상기 숫자는 배열에 포함 된 데이터 유형의 크기 (바이트)입니다. 돌아 가기 연결리스트와 자바에

... 자바에서

, 당신은 명시 적으로 메모리 위치에 액세스 할 수 있지만 기본 개념은 여전히 ​​성능상의 이유로 중요하다. 다음 노드를 점프해야하는 링크 된 목록의 항목에 액세스하는 대신 포인터에 추가하여 인덱스가 증가하는 배열의 항목에 액세스하는 것이 더 빠릅니다. 따라서 링크 된 목록의 인덱스 액세스에는 O (n) 시간이 걸리며 배열은 O (1) 시간입니다.

적어도 약간의 의미가 있기를 바랍니다.

Answer 5

링크 된 목록 자체는 노드의 시퀀스로 나타나며 목록의 다음 노드 (이전 일 수도 있음)를 가리키는 멤버 변수가 있습니다. 연결된 목록을 만들 때 일반적으로 머리가 될 첫 번째 노드를 사용하여 링크 된 목록을 만듭니다. 새 요소를 링크 된 목록에 추가해야하는 경우 먼저 요소를 만들어야합니다. 메모리 어딘가에서 생성되고 힙이 될 수 있으며 스택 될 수 있습니다. 그리고 메모리는 OS에 의해 할당되고, OS의 메모리 위치가 우리에게 제공됩니다. 새 Node를 생성 한 직후에, 우리는 현재 노드의 "next"를 그 새로운 노드에 할당해야합니다.

인접한 데이터 구조 란 무엇입니까? 배열.