선형 자료 구조

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