링크된 데이터 구조

컴퓨터 과학에서, 링크된 데이터 구조는 서로 링크되고 참조(링크 또는 포인터)에 의해 정리된 데이터 레코드(노드)의 집합으로 구성된 데이터 구조입니다.데이터 간의 링크는 커넥터라고도 합니다.

링크된 데이터 구조에서 링크는 일반적으로 동일성을 위해 참조하거나 비교할 수 있는 특수한 데이터 유형으로 취급됩니다.따라서 링크된 데이터 구조는 포인터에서 산술 연산을 수행해야 하는 배열 및 기타 데이터 구조와 대조됩니다.이 차이는 노드가 실제로 단일 어레이의 요소로 구현되어 있고 참조가 실제로 어레이 인덱스인 경우에도 유지됩니다. 이러한 인덱스에 대해 산술이 수행되지 않는 한 데이터 구조는 기본적으로 링크된 것입니다.

링크는 동적 할당과 어레이 인덱스 링크의 두 가지 방법으로 실행할 수 있습니다.

링크드 데이터 구조에는 링크드 리스트, 검색 트리, 식 트리 및 기타 널리 사용되는 많은 데이터 구조가 포함됩니다.또한 토폴로지^[1] 정렬 및 set union-find와 ^[2]같은 많은 효율적인 알고리즘의 핵심 구성 요소이기도 합니다.

링크된 데이터 구조의 일반적인 유형

링크 리스트

링크 리스트는 메모리 내의 물리적인 위치가 아니라 구조 자체에 데이터의 일부로 저장되는 논리 링크에 의해 정렬된 구조의 집합입니다.인접한 메모리 위치에 저장할 필요는 없습니다.모든 구조에는 데이터 필드와 주소 필드가 있습니다.[ Address ]필드에는 후계자 주소가 포함됩니다.

링크 리스트는 단일, 이중 또는 다중 링크할 수 있으며 선형 또는 원형 링크일 수 있습니다.

기본 속성

• 노드라고 불리는 개체는 선형 순서로 연결됩니다.
• 목록의 첫 번째 노드에 대한 참조는 항상 유지됩니다.이것은 '머리' 또는 '앞'^[3]이라고 불립니다.

노드가 3개인 링크 리스트에는 각각 정수값과 다음 노드에 대한 링크라는2개의 필드가 있습니다.

단일 노드가 있는 링크된 목록입니다.

Java에서의 예

다음 예시는 링크된 목록의 Java 구현에서 정수를 저장하기 위해 사용되는 노드 클래스의 예입니다.

일반의 학급 인트노드 {      일반의 인트 가치;      일반의 인트노드 링크;      일반의 인트노드(인트 v) { 가치 = v; } } 

C의 예

다음 예시는 C에서 링크드목록 구현에 사용되는 구조입니다.

구조 노드 {  인트 값;  구조 노드 *다음 분.; }; 

다음 예제에서는 typedef를 사용합니다.

유형화된 구조 노드 노드;  구조 노드 {  인트 값;  노드 *다음 분.; }; 

주의: 이와 같은 구조를 가리키는 부재를 포함하는 구조를 자기 참조 구조라고 합니다.

C++의 예

다음 예시는 C++에서 링크드목록을 구현하기 위해 사용되는 노드클래스 구조의 예입니다.

학급 노드 {  인트 값;  노드 *다음 분.; }; 

트리 검색

서치 트리는 노드 데이터 값이 순서 있는 세트로부터 격납될 수 있는 트리 데이터 구조이며, 즉 트리의 순서대로 트래버스에서 노드가 격납된 값의 오름차순으로 방문된다.

기본 속성

• 노드라고 불리는 오브젝트는 순서 있는 세트에 저장됩니다.
• 순서대로 트래버설은 트리의 데이터를 오름차순 읽어냅니다.

장점과 단점

링크 리스트와 어레이

어레이에 비해 링크된 데이터 구조를 사용하면 데이터 구성 및 공간 할당에 있어 유연성이 향상됩니다.어레이에서는, 어레이의 사이즈를 최초로 정확하게 지정할 필요가 있습니다.이것은 메모리 낭비의 가능성이 있거나, 나중에 기능을 방해할 가능성이 있는 임의의 제한입니다.링크된 데이터 구조는 동적으로 구축되므로 프로그램에서 요구하는 것보다 클 필요가 없습니다.또, 어느 정도의 공간을 할당할 필요가 있는지를, 작성시에 추측할 필요도 없습니다.이는 메모리 낭비를 방지하는 데 중요한 기능입니다.

어레이에서 어레이 요소는 메모리의 연속된(접속된) 부분에 있어야 합니다.그러나 링크된 데이터 구조에서는 각 노드에 대한 참조가 사용자에게 다음 노드를 찾는 데 필요한 정보를 제공합니다.링크된 데이터 구조의 노드는 어레이와 달리 물리적 메모리 내의 다른 위치로 개별적으로 이동할 수도 있습니다.특정 프로세스 또는 스레드는 다른 프로세스 또는 스레드가 다른 부분에서 작동하는 동안에도 데이터 구조의 한 부분에 노드를 추가하거나 삭제할 수 있습니다.

한편 링크된 데이터 구조에서 특정 노드에 액세스하려면 각 노드에 저장된 참조 체인을 따라야 합니다.구조에 노드가 n개 있고 각 노드에 b개까지 링크가 포함되어 있는 경우 로그 n개보다 적은_b 절차로 도달할 수 없는 노드가 몇 개 있기 때문에 이러한 노드에 액세스하는 프로세스가 느려집니다.이것은 특히 노드의 수가 많은 구조에서는 현저한 저하를 나타내는 경우가 있습니다.많은 구조에서 일부 노드는 최악의 경우 n-1단계까지 필요한 경우가 있습니다.이와는 대조적으로 많은 배열 데이터 구조에서는 엔트리 수에 관계없이 일정한 수의 연산을 가진 모든 요소에 액세스할 수 있습니다.

이러한 링크된 데이터 구조의 구현은 대체로 동적 데이터 구조를 통해 이루어집니다.특정 공간을 다시 사용할 수 있는 기회가 주어집니다.이러한 데이터 구조를 사용하면 메모리를 보다 효율적으로 사용할 수 있습니다.메모리는 필요에 따라 할당되며 메모리가 더 이상 필요하지 않을 경우 할당 해제가 이루어집니다.

일반적인 단점

링크된 데이터 구조도 상당한 메모리 할당 오버헤드가 발생할 수 있으며(노드가 개별적으로 할당되어 있는 경우), 메모리 페이징 및 프로세서 캐싱 알고리즘(일반적으로 참조 인접성이 낮기 때문에)이 좌절될 수 있습니다.경우에 따라서는 링크된 데이터 구조가 경쟁 어레이 구조보다 더 많은 메모리(링크 필드)를 사용할 수도 있습니다.이는 링크된 데이터 구조가 연속적이지 않기 때문입니다.데이터 인스턴스는 어레이와 달리 메모리 전체에서 찾을 수 있습니다.

어레이에서는 n번째 요소에 즉시 액세스할 수 있는 반면 링크된 데이터 구조에서는 요소 액세스 시간이 구조 내 위치에 따라 달라지도록 여러 포인터를 따라야 합니다.

포인터 머신과 같이 링크된 구조의 제약을 적용하는 일부 계산 이론 모델에서는 많은 문제가 구속되지 않은 랜덤 액세스 머신 모델보다 더 많은 단계를 필요로 합니다.

「 」를 참조해 주세요.

• 데이터 구조 목록
• 미들웨어

레퍼런스