DS_4. Linked-list

Linked-list

연결 리스트(Linked List)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 대표적인 선형 자료구조이다. 다양한 추상 자료형(ADT: Abstract Data Type) 구현의 기반이 되며 탐색에는 O(n), 추가, 삭제, 추출 등의 작업에는 O(1)의 시간복잡도를 가진다.

연결 리스트의 종류

연결 리스트는 다음과 같이 나눌 수 있다.

단일 연결 리스트

단일 연결 리스트는 각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킨다.

이중 연결 리스트

이중 연결 리스트의 구조는 단일 연결 리스트와 비슷하지만, 포인터 공간이 두 개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다.

원형 연결 리스트

원형 연결 리스트는 일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다.

참고
위키 백과 - 연결 리스트