c언어로 쉽게 풀어쓴 자료구조 개정 3판 7장(연결리스트2) 연습문제 (해설 포함)

1. 연결리스트2 개념 정리

연결리스트는 자료구조의 한 종류로서 연속된 메모리 공간이 아닌 각 요소가 포인터를 이용하여 서로 연결된 형태이다. 일반적으로 포인터를 이용하여 이전 노드와 다음 노드의 주소를 가리키는 방식으로 구현되며, 이를 통해 동적 크기 조절이 가능하다. 연결리스트는 인덱스 기반 접근이 아닌 순차 탐색을 통해 데이터에 접근하기 때문에 배열에 비해 특정 위치 삽입과 삭제 연산이 용이하다. 예를 들어, 배열에서 100번째 위치의 데이터를 삽입하거나 삭제하려면 전체 데이터를 한 번씩 이동시키는 번거로움이 있지만, 연결리스트는 포인터를 조작하여 해당 위치의 노드를 연결 회사만 변경하면 되기 때문에 평균적인 시간 복잡도가 O(1) 또는 O(n)으로 줄어든다.

연결리스트는 단일 연결리스트, 이중 연결리스트, 환형 연결리스트로 구분되며, 각각의 특징과 활용 목적이 다르다. 단일 연결리스트는 각 노드가 다음 노드의 주소만 가지고 있어 구현이 간단하나, 뒤로 돌아가는 탐색이 불가능하다. 반면, 이중 연결리스트는 이전 노드와 다음 노드의 포인터를 갖고 있어 양방향 탐색이 가능하다. 환형 연결리스트는 마지막 노드가 다시 처…