선형 자료 구조란 요소가 일렬로 나열되어 있는 자료 구조를 말한다.
연결 리스트
연결 리스트는 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조이다. 삽입과 삭제가 이 걸리며, 탐색에는 이 걸린다.
prev 포인터와 next 포인터로 앞과 뒤의 노드를 연결시킨 것이 연결리스트이며, 연결 리스트는 싱글 연결 리스트, 이중 연결 리스트, 원형 이중 연결 리스트가 있다. 맨 앞에 있는 노드를 헤드(head)라고 한다.
•
싱글 연결 리스트 : next 포인터만 가진다.
•
이중 연결 리스트 : next 포인터와 prev 포인터를 가진다.
•
원형 이중 연결 리스트 : 이중 연결 리스트와 같지만 마지막 노드의 next 포인터가 헤드 노드를 가리키는 것을 말한다.