연결 자료 구조

컴퓨터 과학에서 연결 자료 구조(Linked data structure)는 함께 연결되고 참조(링크 또는 포인터)에 의해 구성된 데이터 레코드(노드) 집합으로 구성된 자료 구조이다. 데이터 간의 링크는 커넥터라고도 부를 수 있다.

연결 자료 구조에서 링크는 일반적으로 특수 자료형으로 취급되며, 오직 역참조되거나 동등성을 비교할 수 있다. 따라서 연결 자료 구조는 배열 및 포인터에 대한 산술 연산을 수행해야 하는 다른 자료 구조와 대조된다. 이 구분은 노드가 실제로 단일 배열의 요소로 구현되고 참조가 실제로 배열 인덱스일 때도 유효하다. 해당 인덱스에 대해 산술 연산이 수행되지 않는 한, 자료 구조는 본질적으로 연결된 자료 구조이다.

연결은 두 가지 방법으로 수행할 수 있다.  – 동적 할당을 사용하고 배열 인덱스 연결을 사용한다.

연결 자료 구조에는 연결 리스트, 탐색 트리, 표현 트리 및 기타 널리 사용되는 많은 자료 구조가 포함된다. 또한 위상 정렬^[1] 및 집합 합집합-찾기^[2]와 같은 많은 효율적인 알고리즘의 핵심 구성 요소이다.

연결 리스트는 메모리의 물리적 배치에 의해 정렬되지 않고, 구조 자체의 데이터 일부로 저장된 논리적 링크에 의해 정렬된 구조의 모음이다. 인접한 메모리 위치에 저장될 필요는 없다. 모든 구조에는 데이터 필드와 주소 필드가 있다. 주소 필드에는 해당 계승자의 주소가 포함된다.

연결 리스트는 단일, 이중 또는 다중으로 연결될 수 있으며 선형 또는 원형일 수 있다.

기본 속성

• 노드라고 불리는 객체는 선형 시퀀스로 연결된다.
• 리스트의 첫 번째 노드에 대한 참조는 항상 유지된다. 이를 '헤드' 또는 '프론트'라고 한다.^[3]

각각 두 개의 필드(정수 값과 다음 노드에 대한 링크)를 포함하는 세 개의 노드가 있는 연결 리스트

다음은 연결 리스트의 자바 구현에서 정수를 저장하는 데 사용되는 노드 클래스의 예시이다.

public class IntNode {      public int value;      public IntNode link;      public IntNode(int v) { value = v; } } 

다음은 C에서 연결 리스트 구현에 사용되는 구조의 예시이다.

struct node { 	int val; 	struct node *next; }; 

다음은 Typedef를 사용한 예시이다.

typedef struct node node;  struct node { 	int val; 	node *next; }; 

참고: 동일한 구조를 가리키는 멤버를 포함하는 이러한 구조를 자기 참조 구조라고 한다.

다음은 C++에서 연결 리스트 구현에 사용되는 노드 클래스 구조의 예시이다.

class Node { 	int val; 	Node *next; }; 

탐색 트리는 노드에 일부 순서 집합에서 데이터 값을 저장할 수 있는 트리 자료 구조이며, 트리의 중위 순회를 수행하면 저장된 값의 오름차순으로 노드를 방문한다.

기본 속성

• 노드라고 불리는 객체는 정렬된 집합에 저장된다.
• 중위 순회는 트리 내 데이터의 오름차순 읽기를 제공한다.

배열과 비교하여 연결 자료 구조는 데이터를 구성하고 공간을 할당하는 데 더 많은 유연성을 제공한다. 배열에서는 배열의 크기를 처음에 정확하게 지정해야 하므로 잠재적인 메모리 낭비 또는 나중에 어떤 식으로든 기능을 방해할 임의의 제한이 될 수 있다. 연결 자료 구조는 동적으로 구축되며 프로그램이 요구하는 것보다 커질 필요가 없다. 또한 생성 시 할당해야 할 공간에 대해 추측할 필요가 없다. 이는 메모리 낭비를 방지하는 핵심 기능이다.

배열에서 배열 요소는 메모리의 연속적인(연결되고 순차적인) 부분에 있어야 한다. 그러나 연결 자료 구조에서 각 노드에 대한 참조는 다음 노드를 찾는 데 필요한 정보를 사용자에게 제공한다. 연결 자료 구조의 노드는 배열과 달리 논리적 연결에 영향을 주지 않으면서 물리적 메모리 내의 다른 위치로 개별적으로 이동할 수도 있다. 적절한 주의를 기울이면 특정 프로세스 또는 스레드가 다른 프로세스 또는 스레드가 다른 부분을 작업하는 동안에도 자료 구조의 한 부분에서 노드를 추가하거나 삭제할 수 있다.

반면에 연결 자료 구조의 특정 노드에 접근하려면 각 노드에 저장된 참조 체인을 따라가야 한다. 구조에 n개의 노드가 있고 각 노드에 최대 b개의 링크가 포함되어 있다면, log_b n단계 미만으로 접근할 수 없는 노드가 있어 이러한 노드에 접근하는 프로세스가 느려진다. 이는 특히 많은 수의 노드를 포함하는 구조의 경우 상당한 속도 저하를 나타낼 수 있다. 많은 구조에서 일부 노드는 최악의 경우 n-1단계까지 필요할 수 있다. 대조적으로, 많은 배열 자료 구조는 항목 수와 무관하게 상수 개의 연산으로 모든 요소에 접근할 수 있다.

대체로 이러한 연결 자료 구조의 구현은 동적 자료 구조를 통해 이루어진다. 이는 특정 공간을 다시 사용할 수 있는 기회를 제공한다. 이러한 자료 구조를 사용하면 메모리를 더 효율적으로 활용할 수 있다. 메모리는 필요에 따라 할당되며 더 이상 필요하지 않을 때 할당이 해제된다.

연결 자료 구조는 또한 상당한 메모리 할당 오버헤드를 발생시킬 수 있으며(노드가 개별적으로 할당되는 경우) 메모리 페이징 및 프로세서 캐싱 알고리즘을 방해할 수 있다(일반적으로 참조 국부성이 좋지 않기 때문). 어떤 경우에는 연결 자료 구조가 경쟁하는 배열 구조보다 더 많은 메모리(링크 필드용)를 사용할 수도 있다. 이는 연결 자료 구조가 연속적이지 않기 때문이다. 데이터 인스턴스는 배열과 달리 메모리 전체에서 찾을 수 있다.

배열에서는 n번째 요소에 즉시 접근할 수 있지만, 연결 자료 구조에서는 여러 포인터를 따라가야 하므로 요소 접근 시간은 요소가 구조 내 어디에 있는지에 따라 달라진다.

포인터 머신과 같이 연결된 구조의 제약 조건을 강제하는 일부 이론적인 계산 모델에서는 랜덤 접근 기계 모델에서보다 많은 단계를 요구하는 많은 문제가 있다.

• 자료 구조 목록