Linked List(연결 리스트, 연결목록,

일련의 데이터 요소들을 통합하여 관리함으로써 정보의 축적과 검색 등 각종 응용 프로그램을 효율적으로 실현하기 위해 사용되는 목록 구조의 하나로, 각 데이터 요소가 포인터(pointer)에 의해 다른 데이터 요소에 연결되는 목록. 데이터 요소가 기억 장치 중 여기저기 분산되어 있지만 각 데이터 요소에는 목록 중 다른 데이터 요소의 기억 장소를 가리키는 포인터가 수용되어 있어서 그 포인터의 순서에 따라서 데이터 요소의 물리적 위치는 변경하지 않고 데이터 요소를 삽입, 삭제, 분할, 결합 및 검색할 수 있고 순서를 변경할 수 있게 하는 목록이다. 포인터가 수용되어 있는 데이터 요소를 노드라고 한다.

 

단방향 연결 목록(singly linked list)은 각 노드에 목록 중 직후(直後)의 노드를 가리키는 1개의 포인터를 가지며, 이중 연결 목록(doubly linked list)은 각 노드에 목록 중 직후의 노드와 직전(直前)의 노드를 가리키는 2개의 포인터를 갖는다. 순환 목록(circular list)에서는 목록의 첫 번째 노드와 맨 끝 노드가 서로 연결된다. 목록이 비순환적인 경우 목록의 맨 끝 데이터 요소에는 널 포인터(null pointer)가 포함된다. 연결 목록은 연쇄 목록과 동의어이며 선형 목록(linear list)과 대비된다.

 

연결 리스트의 장점은 노드(Node는 연결 리스트에서 data와 link/pointer가 구성된 요소)의 삽입∙삭제가 쉽고, 메모리에 대해 독립적이어 메모리 단편화를 방지하여 기억장소를 절약할 수 있다. 또한 희소 행렬을 연결 리스트로 표현하면 기억 장소가 절약된다. 그러나 연결 리스트는 포인터를 위한 추가 공간이 필요하고 액세스 속도가 느리며 중간에 단절되면 다음 노드를 찾기가 어렵다는 단점이 있다.

 

단방향 연결리스트(또는 단순 연결리스트)]

 

데이터의 삽입]

 

데이터의 삭제]

 

 

 

출처]

한국정보통신기술협회 : 연결목록

네이버 : 연결리스트

 

 

 

 

대한민국의 아름다운 영토, 독도의 봄