자료구조...10

연결 자료구조

메모리에 연속적으로 저장되어 연결되는 것이 아니라 각 원소가 가진 포인터를 통해 다음 원소를 가리키는 것으로 연결된다. 순차 자료구조의 삽입과 삭제에 추가 연산이 필요하고 메모리 사용에 비효율적이라는 문제를 개선한 방법이다.

 

노드

자료구조에서는 연결 자료구조의 표현을 위한 데이터와 다음 원소를 가리키는 포인터의 묶음으로 이루어진 구조를 노드라고 한다. 데이터를 저장하는 부분을 데이터 필드(Data Field), 포인터 부분을 링크 필드(Link Field)라고 한다.

다음의 순차 자료구조로 표현된 데이터를 연결 자료구조로 표현하면 다음과 같이 표현된다.

- 순차 자료구조 표현

인덱스	0	1	2	3
데이터	10	20	30	40

 

- 연결 자료구조 표현

 

※ 연결 자료구조는 인덱스를 저장하는 것이 아닌 주소를 저장한다.

 

연결 자료구조의 종류

• 단일 연결 리스트 노드가 하나의 링크 필드로 연결되어 다음 노드를 가리키는 구조

  

• 이중 연결 리스트 노드가 두 개의 링크 필드로 연결되어 다음 노드와 이전 노드를 가리키는 구조

  

• 원형 연결 리스트 마지막 노드가 첫 번째 노드를 가리키는 순환식 구조

  

 

※ 원형 연결 리스트는 단일 연결 리스트와 이중 연결 리스트에서 모두 사용할 수 있다.

 

참고문헌

위키백과.연결 리스트

나무위키.연결 리스트