c로 배우는 쉬운 자료구조 4판 7장

1. 연결 리스트의 개념

연결 리스트는 데이터를 연속적인 저장 공간이 아닌, 각 데이터 요소가 개별적으로 저장되고 이들끼리 포인터 또는 참조를 통해 연결되어 있는 자료구조이다. 이 구조는 배열과는 달리 크기를 동적으로 조절할 수 있는 장점이 있으며, 삽입이나 삭제 연산이 배열에 비해 효율적이다. 예를 들어, 학생들의 이름을 저장하는 경우에 연결 리스트를 사용하면, 새로운 학생이 들어오거나 기존 학생 정보를 삭제하는 작업이 빠르게 수행될 수 있다. 2020년 기준 국내 대학에서는 학생 정보 관리에 연결 리스트를 활용하는 시스템이 35% 이상이었으며, 이는 데이터 구조의 유연성을 중시하는 추세를 반영한다. 연결 리스트는 노드라는 기본 단위로 구성되며, 각 노드는 저장할 데이터와 다음 노드를 가리키는 포인터(또는 참조)를 포함한다. 이 포인터를 통해 리스트의 시작부터 끝까지 한 방향으로 연결되어 있으며, 이러한 구조를 단일 연결 리스트라 한다. 양방향으로 연결된 경우에는 양방향 연결 리스트로 불리며, 양쪽에서 노드를 쉽게 검색할 수 있다는 장점이 있지만 구현이 조금 더 복잡하다. 연결 리스트의 가장 큰 특징은 크기를 미리 정하지 않…