단순 연결 리스트 개념 (p72)

단순 연결 리스트는 각 노드마다 하나의 포인터 영역을 가지며,

이전 노드의 포인터가 다음 노드를 가리키면서 서로 연결된 구조이다.

기억 공간 내 떨어져 있는 자료들을 포인터로 연결하며, 자료가

주기억 장치 내에 물리적으로 어떻게 저장되어 있는지에 관계없이

포인터가 가리키는 주소를 사용하여 논리적인 순서를 가진다.

 

 

연결 리스트에서 하나의 자료를 저장하는 단위를 노드(node)라고 하며,

한 개의 노드는 실제로 자료를 저장하는 데이터 영역과 다음 자료가 저장된

노드를 가리키는 포인터 영역으로 구성되어 있다.

 

헤드 포인터(head pointer)가 첫 번째 노드와 연결되며, 포인터를 통하여

연결되어 있는 각 자료에 접근할 수 있다. 또한, 마지막 노드는 더 이상

연결할 후속 노드가 없기 때문에 포인터 영역을 null로 설정한다.

연결 리스트

 

 

연결 리스트는 크기가 제한적이지 않고 자료의 삽입과 삭제가 자유롭기

때문에 자료를 빈번하게 삽입 및 삭제하는 업무에 효과적이다. 그러나

자료의 위치를 찾을 때 포인터를 하나씩 따라가야 하므로 순차 리스트에

비하여 자료에 접근하는 시간이 오레 걸리고 포인터 영역을 사용함에 따라

저장 공간을 상대적으로 많이 차지한다는 단점이 있다.