리스트의 정의

연결 리스트는 일정한 순서를 가지는 데이타 항목들을 표현하는 방법중의 하나이다. 배열과 같은 순차적 표현 방법과는 달리 데이타 항목들의 논리적인 순서만 유지되고 기억장소내에서는 각 항목들의 임의의 위치를 가지도록 하는 자료구조이다.


다음과 같이 'ABC'순으로 정렬된 목록에서 각 항목들 사이에는 "graph 다음에는 list"하는 식의 논리적 순서가 유지된다.
(graph, list, stack, tree)
이 목록을 연결 리스트로 표현하면 다음과 같다.

연결 리스트에서는 각 데이타 항목들이 기억장소내의 어떤 위치에 어떤 항목이 있는 지를 표시해 주어야 한다. 이를 위해 데이터 항목에는 값뿐만이 아니라 다음 항목의 위치 정보도 함께 저장해둔다.

순차적 표현 방법

순차적 표현방법은 각각의 데이타 항목들이 논리적으로뿐 아니라 물리적으로도 동일한 순서와 위치를 가지는 것이다. 다음과 같이 'ABC'순으로 정렬된 목록에서 각 항목들 사이에는 "graph, 다음list"하는 식의 논리적 순서가 유지된다.
(graph, list, stack, tree)
이 목록을 순차적 방법으로 표현하면 다음과 같다.

순차적 표현 방법에서는 각 데이타 항목들이 논리적인 순서와 마찬가지로 기억장소 내에 차례로 저장된다. 즉 list항목은 기억장소내에서도 "graph" 항목의 바로 뒤에 놓이게 된다.

연결 리스트의 구조

연결 리스트에서 하나의 데이타 항목을 저장하는 단위를 노드(node)라고 한다. 하나의 노드는 데이타 값과, 다음 항목이나 이전 항목을 가리키는 포인터로 구성된다.

(graph, list, stack, tree)의 목록은 다음과 같이 연결 리스트로 표현될수 있다.

연결 리스트는 노드의 구조와 연결방법에 따라 세가지로 구분된다.

연결 리스트에서의 포인터

연결 리스트에서 포인터는 각 항목의 다음 순서인 항목이나 앞 순서인 항목의 위치를 가리키는지시자이다.
포인터의 특수한 형태인 NULL포인터는 아무런 항목도 가리키지 않는다는 의미이다. 연결 리스트의 마지막 노드에는 다음 순서인 항목이 없고, 첫번째 노드에는 이전 순서인 항목이 없으므로 이들 포인터는 NULL로 해주어야 한다.

연결 리스트의 종류