배열

[자료구조] 5.2. 선형 자료 구조

본 포스팅은 [면접을 위한 CS 전공지식 노트]의 내용을 참고하여 작성하였습니다. 5.2. 선형 자료 구조 선형 자료 구조란 요소가 일렬로 나열되어 있는 자료 구조를 말한다. 1) 연결 리스트 연결 리스트는 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료구조이다. 삽입과 삭제에 O(1), 탐색에 O(n)이 걸린다. 위와 같이 prev 포인터와 next 포인터로 앞과 뒤를 연결한 것이 연결 리스트이다. 연결 리스트는 다음과 같이 3가지 연결 리스트가 존재한다. 싱글 연결 리스트: next 포인터만 가진다. 이중 연결 리스트: next 포인터와 prev 포인터를 가진다. 원형 이중 연결 리스트: 마지막 노드의 next 포인터가 헤드 노드를 가리키는 이중 연결 리스트. 2) 배열 배열..