지금까지 구조체 배열에서 정보를 저장하고 삭제하는 방법을 알아봤습니다. 그러면 이 방법이 구조체 배열에서 정보를 저장하고 삭제하는 데 과연 효율적이라고 할 수 있을까요?

만약 우리 반 학생 10명이 아니라, 전교생 1000명에 대한 정보가 구조체 배열로 저장되어 있다고 가정해 봅시다. 그런데 만약 두 번째로 저장된 학생이 전학을 가서 그 정보가 더 이상 필요 없다면 998명의 정보를 왼쪽으로 한 칸씩 밀어야 합니다. 더 넓게는, 국가 차원에서 인구 조사를 하는데, 배열의 두 번째에 있는 사람이 이민을 간다면 수천만 명의 정보를 왼쪽으로 이동해야 할 것입니다. 아무리 빠른 컴퓨터라고 하더라도 이 과정을 수행하는 데는 상당한 시간이 걸릴 것입니다.

이 문제를 해결하기 위한 방법은 무엇일까요? 지금부터 자기 참조 구조체 및 이를 사용한 자료 구조(data structure)인 연결 리스트(linked list)에 대해서 소개하겠습니다.