검색
색인
연결 목록, 連結目錄, linked list
일련의 데이터 요소들을 통합하여 관리함으로써 정보의 축적과 검색 등 각종 응용 프로그램을 효율적으로 실현하기 위해 사용되는 목록 구조의 하나로, 각 데이터 요소가 포인터(pointer)에 의해 다른 데이터 요소에 연결되는 목록. 데이터 요소기억 장치 중 여기저기 분산되어 있지만 각 데이터 요소에는 목록 중 다른 데이터 요소기억 장소를 가리키는 포인터가 수용되어 있어서 그 포인터의 순서에 따라서 데이터 요소의 물리적 위치는 변경하지 않고 데이터 요소를 삽입, 삭제, 분할, 결합 및 검색할 수 있고 순서를 변경할 수 있게 하는 목록이다. 포인터가 수용되어 있는 데이터 요소를 노드라고 한다. 단방향 연결 목록(singly linked list)은 각 노드에 목록 중 직후(直後)의 노드를 가리키는 1개의 포인터를 가지며, 이중 연결 목록(doubly linked list)은 각 노드에 목록 중 직후의 노드와 직전(直前)의 노드를 가리키는 2개의 포인터를 갖는다. 순환 목록(circular list)에서는 목록의 첫 번째 노드와 맨 끝 노드가 서로 연결된다. 목록이 비순환적인 경우 목록의 맨 끝 데이터 요소에는 널 포인터(null pointer)가 포함된다. 연결 목록은 연쇄 목록과 동의어이며 선형 목록(linear list)과 대비된다.